.编写程序实现二叉树的建树、先序递归遍历、中序递归遍历、后序递归遍历4个基本操作;(必须完成)
时间: 2024-01-31 11:04:02 浏览: 29
好的,下面是答案:
二叉树建树的实现:
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
if (preorder.empty() || inorder.empty()) return NULL;
int root_val = preorder[0];
TreeNode* root = new TreeNode(root_val);
auto it = find(inorder.begin(), inorder.end(), root_val);
int left_size = distance(inorder.begin(), it);
vector<int> left_pre(preorder.begin() + 1, preorder.begin() + 1 + left_size);
vector<int> left_in(inorder.begin(), it);
root->left = buildTree(left_pre, left_in);
vector<int> right_pre(preorder.begin() + 1 + left_size, preorder.end());
vector<int> right_in(it + 1, inorder.end());
root->right = buildTree(right_pre, right_in);
return root;
}
二叉树先序递归遍历的实现:
void preorder(TreeNode* root) {
if (!root) return;
cout << root->val << " ";
preorder(root->left);
preorder(root->right);
}
二叉树中序递归遍历的实现:
void inorder(TreeNode* root) {
if (!root) return;
inorder(root->left);
cout << root->val << " ";
inorder(root->right);
}
二叉树后序递归遍历的实现:
void postorder(TreeNode* root) {
if (!root) return;
postorder(root->left);
postorder(root->right);
cout << root->val << " ";
}
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)