帮我写一个C++代码,由前序序列和中序序列确定一棵二叉树
时间: 2024-12-15 19:22:08 浏览: 12
在C++中,我们可以使用递归的方式来构建二叉搜索树(BST),给定它的前序遍历(Preorder Traversal)和中序遍历(Inorder Traversal)。这里是一个简单的示例代码:
```cpp
#include <iostream>
using namespace std;
// 定义节点结构体
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 前序遍历函数,根节点 -> 左 -> 右
TreeNode* buildTreeHelper(TreeNode* root, int pre[], int in[], int start, int end) {
if (start > end)
return NULL;
// 找到前序遍历中的根节点
TreeNode* node = new TreeNode(pre[start]);
int i = searchNode(in, start, end, node->val); // 中序位置
// 递归构建左子树和右子树
node->left = buildTreeHelper(root, pre, in, start + 1, i - 1);
node->right = buildTreeHelper(root, pre, in, i + 1, end);
return node;
}
// 中序遍历中查找目标值的位置
int searchNode(int arr[], int low, int high, int target) {
while (low <= high) {
int mid = low + (high - low) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
low = mid + 1;
else
high = mid - 1;
}
return low; // 如果没找到,返回插入位置
}
// 构建二叉搜索树
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
int n = preorder.size();
return buildTreeHelper(NULL, &preorder[0], &inorder[0], 0, n - 1);
}
// 测试代码
int main() {
vector<int> preorder = {1, 2, 4, 5, 3};
vector<int> inorder = {4, 2, 5, 1, 3};
TreeNode* root = buildTree(preorder, inorder);
// ... (你可以添加打印、检查等后续操作)
return 0;
}
```
这个程序首先通过前序遍历找到当前节点,并使用中序遍历来定位该节点应该放在中序数组中的位置,然后递归地构建左右子树。`main`函数中给出了一个例子,你可以根据实际需求修改输入的前序和中序序列。
阅读全文