编写具体函数实现二叉树的创建,前序、中序、后序遍历等基本操作,
时间: 2024-05-05 18:19:03 浏览: 4
好的,这是一个计算机科学相关的问题,可以回答。下面是二叉树的创建、前序、中序、后序遍历的基本实现:
二叉树的创建:
二叉树的每个节点最多有两个子节点,左边的节点比右边节点小。首先创建二叉树节点的结构体:
```
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
```
然后递归创建二叉树,先输入二叉树的根节点的值,如果节点数大于1,递归创建左、右子树。递归输入左子树时,左子树的节点数为整棵树的一半,右子树节点数则为剩下的节点数。
```
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
unordered_map<int, int> m;
for (int i = 0; i < inorder.size(); ++i) {
m[inorder[i]] = i;
}
return buildTree(preorder, inorder, m, 0, preorder.size()-1, 0, inorder.size()-1);
}
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder, unordered_map<int, int>& m, int pre_left, int pre_right, int in_left, int in_right) {
if (pre_left > pre_right || in_left > in_right) {
return nullptr;
}
int root_val = preorder[pre_left];
TreeNode* root = new TreeNode(root_val);
int index = m[root_val];
int left_size = index - in_left;
root->left = buildTree(preorder, inorder, m, pre_left+1, pre_left+left_size, in_left, index-1);
root->right = buildTree(preorder, inorder, m, pre_left+left_size+1, pre_right, index+1, in_right);
return root;
}
```
先序遍历:
先序遍历拥有以下规则:
1. 访问根节点。
2. 前序遍历左子树。
3. 前序遍历右子树。
实现先序遍历的函数:
```
void preOrder(TreeNode* root) {
if (root) {
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
}
```
中序遍历:
中序遍历拥有以下规则:
1. 中序遍历左子树。
2. 访问根节点。
3. 中序遍历右子树。
实现中序遍历的函数:
```
void inOrder(TreeNode* root) {
if (root) {
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
}
```
后序遍历:
后序遍历拥有以下规则:
1. 后序遍历左子树。
2. 后序遍历右子树。
3. 访问根节点。
实现后序遍历的函数:
```
void postOrder(TreeNode* root) {
if (root) {
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
}
```