(1)绘制出图形表示的这棵二叉树,并写出后序序列; 一颗二叉树的先序序列是ABDGCEFH,中序序列是DGBAECHF。 (2)画出这颗树的双亲表示法示意图。
时间: 2024-09-19 12:16:56 浏览: 46
建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数
(1) 根据给定的先序序列(ABDGCEFH)和中序序列(DGBAECHF),我们可以逐步构建这棵二叉树。首先,先序序列的第一个元素通常作为根节点,所以根节点A的左子树的前序是BDG,右子树是CEFH。然后,根据中序序列,我们知道D是根节点A的左子树的根,所以我们在左子树里找到G,它是D的左子树,接着是B;在右子树里,E是F的左子树,H在其右边。所以这棵树的结构应该是这样的:
```
A
/ \
B D
/ \ / \
G C E H
后序序列的顺序通常是左子树、右子树、根节点,即DCBGHEFA。
(2) 对于这棵二叉树的双亲表示法,我们标记每个节点与其直接父节点的关系。根节点A没有双亲,B的双亲是A,D的双亲也是A,以此类推,得到的双亲表示法示意图为:
```
null
/ \
A D
/ \ / \
B C G E
/ \ / \
G H F
/ \
null null
在这个图中,每个非叶节点都有指向其父节点的箭头,而叶子节点(如G、E、H和nulls)没有箭头。
阅读全文