用前序遍历方法创建一棵二叉树,编写算法,输出二叉树的三种遍历序列。
时间: 2024-05-16 19:15:42 浏览: 98
二叉树的三种遍历的推导关系 问题描述: 给定二叉树的前序和中序序列,设计算法输出它的后序序列。 算法设计: 给定二叉树的前序和中序序列,输出它的后序序列。 数据输入: 由文件input.txt 提供输入数据。第1行是二叉树的前序序列,第2行是中序序列(序列的字符与字符之间无空格)。 结果输出: 将计算出的后序序列输出到文件output.txt中。
5星 · 资源好评率100%
好的,我来为您解答。
首先,前序遍历的方法是指先遍历根节点,再遍历左子树,最后遍历右子树。而创建一棵二叉树的方法有很多种,这里我给出一个简单的示例代码:
```c++
#include <iostream>
using namespace std;
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
void createTree(TreeNode*& root) {
int val;
cin >> val;
if (val == -1) {
root = NULL;
return;
}
root = new TreeNode(val);
createTree(root->left);
createTree(root->right);
}
void preOrder(TreeNode* root) {
if (root == NULL) {
return;
}
cout << root->val << " ";
preOrder(root->left);
preOrder(root->right);
}
void inOrder(TreeNode* root) {
if (root == NULL) {
return;
}
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
void postOrder(TreeNode* root) {
if (root == NULL) {
return;
}
postOrder(root->left);
postOrder(root->right);
cout << root->val << " ";
}
int main() {
TreeNode* root;
createTree(root);
cout << "Preorder traversal: ";
preOrder(root);
cout << endl;
cout << "Inorder traversal: ";
inOrder(root);
cout << endl;
cout << "Postorder traversal: ";
postOrder(root);
cout << endl;
return 0;
}
```
在这个示例代码中,我们采用了递归的方式创建了一棵二叉树,并分别实现了输出前序遍历、中序遍历、后序遍历的函数。其中,在输出遍历序列时,我们采用了空格隔开的方式,便于观察结果。
希望这个示例代码能够帮助您解决问题。如果您有任何疑问,欢迎随时向我提出。
阅读全文