题目
设一棵二叉树[1]的先序序列:ABDFCEGH,中序序列:BFDAGEHC(1)画出这棵二叉树。(2)画出这棵二叉树的后序线索树(3)将这棵二又树转换成对应的树(或森林)。
设一棵二叉树[1]的先序序列:ABDFCEGH,中序序列:BFDAGEHC
(1)画出这棵二叉树。
(2)画出这棵二叉树的后序线索树
(3)将这棵二又树转换成对应的树(或森林)。
题目解答
答案
(1) 画出这棵二叉树:
首先,根据先序序列可以确定根节点为A。然后,根据中序序列,我们可以将中序序列分为左子树和右子树两部分。在中序序列中,根节点A的左侧为左子树的中序序列(BFD),右侧为右子树的中序序列(GEHC)。
根据先序序列,下一个节点是B,因此B是A的左子节点。继续按照该思路构建二叉树:

(2) 画出这棵二叉树的后序线索树:
后序线索树是在二叉树的每个节点上添加线索(指向前驱或后继节点的指针)的二叉树。对于后序线索树,我们需要记录节点的前驱和后继。
首先,我们从根节点开始,按照后序遍历的顺序,先处理左子树,然后处理右子树,最后处理根节点。在遍历过程中,我们将节点的前驱指针指向它的前一个访问的节点,后继指针指向它的后一个访问的节点。
对于给定的二叉树,我们可以得到以下后序线索树:

在后序线索树中,每个节点的右指针指向后继节点,每个节点的左指针指向前驱节点。注意,由于根节点没有后继节点,所以根节点A的后继指针为空。
(3) 将这棵二叉树转换成对应的树(或森林):
根据给定的先序序列和中序序列,可以重构原始的二叉树。首先,根据先序序列确定根节点,在中序序列中找到根节点的位置,将中序序列分为左子树和右子树。然后,递归地构建左子树和右子树。
对于给定的先序序列 "ABDFCEGH" 和中序序列 "BFDAGEHC",我们可以得到以下树的结构:

注意,原始的二叉树中的节点C出现了多次,因此在转换成树的过程中,节点C被复制了多次,每个复制的节点C都成为了独立的节点。这样得到了一个树(或森林)的结构。