使用C++语言,按照前序次序建立一棵二叉树。给我完整的代码
时间: 2024-11-22 18:46:05 浏览: 13
在C++中,我们可以使用递归的方式按照前序遍历(根节点 -> 左子树 -> 右子树)构建二叉树。下面是一个简单的模板,假设我们有一个二叉树节点`TreeNode`,包含整数值`val`和两个指向左右孩子的指针`left`和`right`:
```cpp
#include <iostream>
using namespace std;
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
// 前序遍历创建二叉树函数
TreeNode* buildTreePreorder(vector<int>& preorder) {
if (preorder.empty()) return nullptr; // 如果序列为空,返回空树
TreeNode* root = new TreeNode(preorder[0]); // 根据第一个元素创建根节点
int i = 1; // 开始从第二个元素开始找
// 递归处理左子树和右子树
while (i < preorder.size()) {
// 找到左子树的结束位置
int j = i;
while (j < preorder.size() && preorder[j] < preorder[root->val]) {
j++; // 遍历到下一个较大的节点
}
// 创建并设置左子树
if (j != i) {
root->left = buildTreePreorder(preorder.substr(i, j - i));
i = j;
} else {
break; // 没有找到左子树,则进入右子树部分
}
// 创建并设置右子树
if (i < preorder.size()) {
root->right = buildTreePreorder(preorder.substr(i)); // 递归处理剩余部分作为右子树
i++;
}
}
return root;
}
int main() {
vector<int> preorder = {1, 2, 4, 5, 3, 6, 7}; // 假设这是前序遍历序列
TreeNode* tree = buildTreePreorder(preorder);
// 现在你可以打印或进一步操作这棵树了
// ...
return 0;
}
```
在这个例子中,`buildTreePreorder`函数接受一个预序遍历序列,然后根据这个顺序递归地构造二叉树。
阅读全文