C++用先序遍历创建二叉树
时间: 2024-12-15 17:27:28 浏览: 36
在C++中,使用先序遍历(Preorder Traversal)创建二叉树通常涉及到递归过程。先序遍历的顺序是:根节点 -> 左子树 -> 右子树。以下是使用结构体表示二叉树节点和递归函数来实现的简单示例:
```cpp
// 定义二叉树节点
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历创建二叉树函数
TreeNode* createTreeFromPreorder(int* preorder, int n) {
if (n == 0) return nullptr; // 遍历结束条件
TreeNode* root = new TreeNode(preorder[0]); // 根据第一个元素创建根节点
int i = 1; // 预处理索引,跳过根节点
// 对左子树递归调用,直到遇到空值
root->left = createTreeFromPreorder(&preorder[i], n);
i++; // 移动到下一个节点位置
// 对右子树递归调用,如果还有剩余元素
if (i < n)
root->right = createTreeFromPreorder(&preorder[i], n);
return root;
}
```
这个函数接受一个整数数组`preorder`,它是预序遍历的结果,并返回构建出的二叉搜索树的根节点。通过不断将当前遍历到的元素作为根节点,然后对左右子树进行同样的操作,可以构造整个二叉树。
阅读全文
相关推荐

















