(1)由树的先序遍历序列和中序遍历序列创建一棵二叉树。(2)输出二叉树的后序遍历序列。测试数据:先序遍历序列:ABDGCEF中序遍历序列:DGBAECF
时间: 2023-11-23 09:54:33 浏览: 190
建二叉树并分别用先先序、中序和后序遍历,然后输出各遍历序列
5星 · 资源好评率100%
(1)根据先序遍历序列和中序遍历序列创建一棵二叉树的步骤如下:
1. 根据先序遍历序列确定根节点,即序列的第一个元素。
2. 在中序遍历序列中找到根节点的位置,根节点左边的元素为左子树的中序遍历序列,右边的元素为右子树的中序遍历序列。
3. 根据左子树的中序遍历序列长度,在先序遍历序列中找到左子树的先序遍历序列,右边的元素为右子树的先序遍历序列。
4. 递归地对左子树和右子树进行步骤1-3,直到序列为空。
具体实现可以参考以下代码:
```
void CreateTree(BiTree &T, char *preorder, char *inorder, int len) {
if (len <= 0) {
T = NULL;
return;
}
T = new BiTNode;
T->data = *preorder;
int rootIndex = 0;
while (rootIndex < len && *(inorder + rootIndex) != *preorder) {
rootIndex++;
}
CreateTree(T->lchild, preorder + 1, inorder, rootIndex);
CreateTree(T->rchild, preorder + rootIndex + 1, inorder + rootIndex + 1, len - rootIndex - 1);
}
```
(2)输出二叉树的后序遍历序列的步骤如下:
1. 后序遍历左子树。
2. 后序遍历右子树。
3. 输出根节点。
具体实现可以参考以下代码:
```
void postorder(BiTree T) {
if (T == NULL) {
return;
}
postorder(T->lchild);
postorder(T->rchild);
cout << T->data;
}
```
阅读全文