树怎么写
写树可以分为两种方式,一种是手写实现二叉树等数据结构,另一种是利用现成的数据结构库。
手写二叉树
二叉树是一种常见的数据结构,它的每个节点最多只能有两个子节点,分别为左节点和右节点。手写二叉树需要先定义节点结构,通常包括节点值、左子节点和右子节点等信息。然后可以通过递归实现节点插入、查找、删除等操作。
例如,下面是一个简单的二叉树节点结构和插入操作的示例代码:
```
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void insert(TreeNode*& root, int val) {
if (!root) {
root = new TreeNode(val);
return;
}
if (val < root->val) insert(root->left, val);
else insert(root->right, val);
}
```
使用数据结构库
现有的数据结构库可以大大简化树的实现过程,例如STL库中提供了set和map两种容器,它们都是基于红黑树实现的。
set是一种集合容器,内部元素不重复且自动排序。map则是一种映射容器,可以将一个键值对映射到另一个值。它们都可以通过插入、删除、查找等操作实现树的功能。
例如,下面是一个使用set容器实现二叉搜索树的示例代码:
```
#include
#include
using namespace std;
int main() {
set
for (int i = 0; i < 10; i++) s.insert(i);
for (auto it = s.begin(); it != s.end(); it++) cout << *it << " ";
return 0;
}
```
最后的总结
树是一种常用的数据结构,在算法和程序设计中都有广泛应用。手写实现二叉树可以深入理解树的结构和操作,使用现成的数据结构库可以大大提高开发效率。选择哪种方式取决于具体的需求和开发场景。