用 C++写出输出一颗二叉树的先序和中序遍历,输出其后序遍历的算法
时间: 2024-03-21 20:37:37 浏览: 60
二叉树的先序、中序、后序、分层遍历C++实现
4星 · 用户满意度95%
以下是用 C++ 实现输出一颗二叉树的先序和中序遍历,输出其后序遍历的算法:
```cpp
#include <iostream>
using namespace std;
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, int p_start, int p_end, int i_start, int i_end) {
if (p_start > p_end) return NULL;
int root_val = preorder[p_start];
int root_index;
for (int i = i_start; i <= i_end; i++) {
if (inorder[i] == root_val) {
root_index = i;
break;
}
}
int left_size = root_index - i_start;
TreeNode* root = new TreeNode(root_val);
root->left = buildTree(preorder, inorder, p_start + 1, p_start + left_size, i_start, root_index - 1);
root->right = buildTree(preorder, inorder, p_start + left_size + 1, p_end, root_index + 1, i_end);
return root;
}
void postorderTraversal(TreeNode* root) {
if (!root) return;
postorderTraversal(root->left);
postorderTraversal(root->right);
cout << root->val << " ";
}
int main() {
vector<int> preorder = {1, 2, 4, 5, 3, 6, 7};
vector<int> inorder = {4, 2, 5, 1, 6, 3, 7};
TreeNode* root = buildTree(preorder, inorder, 0, preorder.size() - 1, 0, inorder.size() - 1);
cout << "The postorder traversal of the tree is: ";
postorderTraversal(root);
cout << endl;
return 0;
}
```
其中,`buildTree` 函数用来构建二叉树,`postorderTraversal` 函数用来输出二叉树的后序遍历。在 `main` 函数中,我们先定义二叉树的先序遍历和中序遍历序列,然后调用 `buildTree` 函数构建二叉树,并最终输出二叉树的后序遍历。
以上代码的输出结果为:
```
The postorder traversal of the tree is: 4 5 2 6 7 3 1
```
即该二叉树的后序遍历序列为 `4 5 2 6 7 3 1`。
阅读全文