怎么利用中序与后序遍历把树建立起来C++代码
时间: 2024-09-23 21:05:53 浏览: 35
在C++中,我们可以使用中序遍历(Inorder Traversal)和后序遍历(Postorder Traversal)构建二叉树。这两个序列对于二叉搜索树(BST)来说特别有用,因为它们的顺序可以用来确定每个节点的位置。
首先,我们需要创建一个二叉树节点结构:
```cpp
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
然后,我们可以借助递归的方式来实现这个过程。下面是一个基本的例子,它假设我们已经有了两个函数 `inOrder` 和 `postOrder` 分别用于中序遍历和后序遍历的结果:
```cpp
// 中序遍历生成数组
vector<int> inOrderTraversal(TreeNode* root) {
vector<int> result;
if (root) {
result = inOrderTraversal(root->left);
result.push_back(root->val);
result = result + inOrderTraversal(root->right);
}
return result;
}
// 后序遍历生成数组
vector<int> postOrderTraversal(TreeNode* root) {
vector<int> result;
if (root) {
result = postOrderTraversal(root->left);
result = result + postOrderTraversal(root->right);
result.push_back(root->val);
}
return result;
}
// 根据中序和后序遍历重建树
TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
if (inorder.empty() || postorder.empty()) return nullptr;
int root_val = postorder.back();
size_t root_idx = find(inorder.begin(), inorder.end(), root_val) - inorder.begin();
TreeNode* root = new TreeNode(root_val);
// 将右子树插入到中序序列对应位置之后
root->right = buildTree(inorder.begin() + root_idx + 1, postorder.begin() - 1);
// 然后将左子树插入根之前
root->left = buildTree(inorder.begin(), inorder.begin() + root_idx);
return root;
}
```
在这个例子中,`buildTree` 函数接收中序和后序遍历的数组作为输入,通过查找后序序列的最后一个元素找到根节点,再根据左右子树在中序序列中的相对位置递归地构造出整个二叉树。