二叉树的构建c++
时间: 2023-08-06 21:06:55 浏览: 48
二叉树的构建可以使用C++的面向对象编程思想来实现。下面是一个简单的二叉树的实现示例:
```cpp
// 定义二叉树结点类
class TreeNode {
public:
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 构建二叉树的函数
TreeNode* buildTree(int* preorder, int* inorder, int preorder_len, int inorder_len) {
if (preorder_len == 0 || inorder_len == 0) {
return NULL;
}
// 在前序遍历序列中找到根结点
int root_val = preorder[0];
TreeNode* root = new TreeNode(root_val);
// 在中序遍历序列中找到根结点的位置
int root_pos = 0;
for (int i = 0; i < inorder_len; i++) {
if (inorder[i] == root_val) {
root_pos = i;
break;
}
}
// 构建左子树
root->left = buildTree(preorder + 1, inorder, root_pos, root_pos);
// 构建右子树
root->right = buildTree(preorder + root_pos + 1, inorder + root_pos + 1, preorder_len - root_pos - 1, inorder_len - root_pos - 1);
return root;
}
```
这个二叉树的构建函数使用了前序遍历序列和中序遍历序列来构建二叉树。其中,前序遍历序列中的第一个结点为根结点,在中序遍历序列中找到根结点位置,就可以划分出左子树和右子树的遍历序列,然后递归构建左子树和右子树。