假设二叉树的结点值是字符,根据输入的一棵二叉树的完整先序遍历序列建立一棵以二叉链表表示的二叉树。对二叉树进行先序、中序和后序遍历操作,并输出遍历序列,观察输出的序列是否与逻辑上的序列一致。主程序中要求设计一个菜单,允许用户通过菜单来多次选择执行哪一种遍历操作。
时间: 2024-05-16 22:14:17 浏览: 102
二叉树的几种操作,包括递归先序建立二叉树、先序遍历、中序遍历、后序遍历、非递归的各种遍历
好的,这是一道关于二叉树遍历算法的问题。我可以给出一份C++代码示例,可以帮助你理解如何实现该算法。
```cpp
#include <iostream>
#include <cstring>
using namespace std;
struct TreeNode {
char val;
TreeNode *left;
TreeNode *right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 根据先序遍历序列构建二叉树
TreeNode* buildTree(string& preorder, int& pos) {
if(pos >= preorder.size() || preorder[pos] == '#') {
pos++;
return NULL;
}
TreeNode* root = new TreeNode(preorder[pos++]);
root->left = buildTree(preorder, pos);
root->right = buildTree(preorder, pos);
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 << " ";
}
int main() {
string preorder; // 输入的先序遍历序列
cout << "请输入二叉树的完整先序遍历序列(#表示为空结点):" << endl;
cin >> preorder;
int pos = 0;
TreeNode* root = buildTree(preorder, pos);
int choice = 0;
while(choice != 4) {
cout << "请选择遍历方式:" << endl;
cout << "1. 先序遍历" << endl;
cout << "2. 中序遍历" << endl;
cout << "3. 后序遍历" << endl;
cout << "4. 退出" << endl;
cin >> choice;
switch(choice) {
case 1:
cout << "先序遍历序列为:";
preOrder(root);
cout << endl;
break;
case 2:
cout << "中序遍历序列为:";
inOrder(root);
cout << endl;
break;
case 3:
cout << "后序遍历序列为:";
postOrder(root);
cout << endl;
break;
case 4:
cout << "程序已退出。" << endl;
break;
default:
cout << "输入有误,请重新选择。" << endl;
}
}
return 0;
}
```
这份代码中,`buildTree`函数用于构建二叉树,`preOrder`、`inOrder`和`postOrder`函数分别用于实现先序、中序和后序遍历。在主函数中,我们先根据输入的先序遍历序列构建二叉树,然后通过一个菜单让用户选择遍历方式,根据用户选择的方式输出对应的遍历序列。
阅读全文