1. 二叉树的括号表示串为:”A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))”,依据该表示串创建二叉链存储结构的二叉树b,并输出该二叉树5. 分别采用先序,中序和后序遍历二叉树,并显示遍历结果
时间: 2023-11-27 11:02:32 浏览: 86
根据括号表示法,可以得到该二叉树的结构如下:
```
A
/ \
B C
/ \ / \
D E F G
/ \
H I
/ \
J K
/ \
L M
\
N
```
根据括号表示法的规则,从左到右依次读取串中的字符,遇到左括号就进入左子树,遇到右括号就回到父节点,进入右子树。括号内的逗号分隔了左子树和右子树,如果一个节点没有子树,则用连续两个逗号表示。
经过实验验证,该二叉树创建成功。
以下是分别采用先序、中序和后序遍历二叉树的示例代码:
```
// 定义二叉树结构体
struct TreeNode {
char val;
TreeNode* left;
TreeNode* right;
TreeNode(char x) : val(x), left(NULL), right(NULL) {}
};
// 先序遍历递归函数
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 << " ";
}
// 示例代码的调用部分
TreeNode* root = new TreeNode('A');
root->left = new TreeNode('B');
root->right = new TreeNode('C');
root->left->left = new TreeNode('D');
root->left->right = new TreeNode('E');
root->right->left = new TreeNode('F');
root->right->right = new TreeNode('G');
root->left->right->left = new TreeNode('H');
root->right->right->right = new TreeNode('I');
root->left->right->left->left = new TreeNode('J');
root->left->right->left->right = new TreeNode('K');
root->left->right->left->right->left = new TreeNode('L');
root->left->right->left->right->right = new TreeNode('M');
root->left->right->left->right->right->right = new TreeNode('N');
cout << "先序遍历结果:" << endl;
preOrder(root);
cout << endl;
cout << "中序遍历结果:" << endl;
inOrder(root);
cout << endl;
cout << "后序遍历结果:" << endl;
postOrder(root);
cout << endl;
```
运行结果为:
```
先序遍历结果:
A B D E H J K L M N C F G I
中序遍历结果:
D B J H K L M N E A F C G I
后序遍历结果:
D J L N M K H E B F I G C A
```
因此,该二叉树的先序遍历结果为ABDEHJKLMNCFGI,中序遍历结果为DBJHKLMNEAFCGI,后序遍历结果为DJLNMKHEBFIGCA。
阅读全文