1)由树的先序遍历序列和中序遍历序列创建一棵二叉树。(2)输出二叉树的后序遍历序列。测试数据:先序遍历序列:ABDGCEF中序遍历序列:DGBAECF
时间: 2023-11-23 08:54:32 浏览: 140
建二叉树并分别用先先序、中序和后序遍历,然后输出各遍历序列
5星 · 资源好评率100%
1. 由树的先序遍历序列和中序遍历序列创建一棵二叉树的步骤:
1.1. 如果先序遍历序列或中序遍历序列为空,则返回空树。
1.2. 取先序遍历序列的第一个元素作为根节点。
1.3. 在中序遍历序列中找到根节点的位置,将中序遍历序列分成左子树和右子树两部分。
1.4. 根据左子树和右子树的长度,在先序遍历序列中分出左子树和右子树的序列。
1.5. 递归地对左子树和右子树进行步骤1-4,分别得到左子树和右子树,将其作为根节点的左右子树。
1.6. 返回根节点。
2. 输出二叉树的后序遍历序列的步骤:
2.1. 如果根节点为空,则返回。
2.2. 递归地输出左子树的后序遍历序列。
2.3. 递归地输出右子树的后序遍历序列。
2.4. 输出根节点的值。
代码如下:
```C++
void CreateTree_HZ(BiTree &T, char hou[], int hl, int hr, char zhong[], int zl, int zr) {
if (hl > hr || zl > zr) { // 先序遍历序列或中序遍历序列为空
T = NULL;
return;
}
T = new BiTNode; // 创建根节点
T->data = hou[hr]; // 取先序遍历序列的最后一个元素作为根节点
int i;
for (i = zl; i <= zr; i++) { // 在中序遍历序列中找到根节点的位置
if (zhong[i] == hou[hr]) {
break;
}
}
int left_len = i - zl; // 左子树的长度
int right_len = zr - i; // 右子树的长度
CreateTree_HZ(T->lchild, hou, hl, hl + left_len - 1, zhong, zl, i - 1); // 递归地对左子树进行步骤1-4
CreateTree_HZ(T->rchild, hou, hl + left_len, hr - 1, zhong, i + 1, zr); // 递归地对右子树进行步骤1-4
}
void postorder(BiTree T) {
if (T == NULL) { // 根节点为空
return;
}
postorder(T->lchild); // 递归地输出左子树的后序遍历序列
postorder(T->rchild); // 递归地输出右子树的后序遍历序列
cout << T->data; // 输出根节点的值
}
```
阅读全文