建立二叉树,并通过调用函数,,输出先序遍历、中序遍历与后序遍历的结果。
时间: 2024-05-05 19:18:22 浏览: 10
好的,这是一道关于数据结构的问题。建立二叉树可以用递归或堆栈实现。代码如下:
```cpp
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
TreeNode *buildTree(int pre[], int in[], int preStart, int preEnd, int inStart, int inEnd) {
if (preStart > preEnd || inStart > inEnd)
return nullptr;
int rootVal = pre[preStart];
int i = 0;
for (i = inStart; i <= inEnd; ++i) {
if (in[i] == rootVal)
break;
}
TreeNode *root = new TreeNode(rootVal);
root->left = buildTree(pre, in, preStart + 1, preStart + i - inStart, inStart, i - 1);
root->right = buildTree(pre, in, preStart + i - inStart + 1, preEnd, i + 1, inEnd);
return root;
}
void preOrder(TreeNode *root) {
if (root == nullptr)
return;
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
void inOrder(TreeNode *root) {
if (root == nullptr)
return;
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
void postOrder(TreeNode *root) {
if (root == nullptr)
return;
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
int main() {
int pre[] = {1, 2, 4, 5, 3, 6};
int in[] = {4, 2, 5, 1, 3, 6};
TreeNode *root = buildTree(pre, in, 0, 5, 0, 5);
cout << "PreOrder traversal: ";
preOrder(root);
cout << endl;
cout << "InOrder traversal: ";
inOrder(root);
cout << endl;
cout << "PostOrder traversal: ";
postOrder(root);
cout << endl;
return 0;
}
```
预期输出结果是:
```
PreOrder traversal: 1 2 4 5 3 6
InOrder traversal: 4 2 5 1 3 6
PostOrder traversal: 4 5 2 6 3 1
```
希望这个答案能对你有所帮助!
相关推荐
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_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)