设一棵二叉树的中序序列是:BDEAFGCKH,后序序列是:EDBGFKHCA,画出该二叉树的中序线索二叉树。
时间: 2023-10-30 10:34:50 浏览: 73
好的,根据题目给出的中序序列和后序序列,重构二叉树,得到的二叉树如下所示:
```
C
/ \
/ \
/ \
/ \
B A
\ / \
D K G
\ /
E F
\
H
```
然后,我们来画出该二叉树的中序线索二叉树。中序序列为BDEAFGCKH,按照中序遍历的顺序,对每个节点进行线索化,指向其在中序遍历中的前驱和后继。线索化后的中序线索二叉树如下所示:
```
B
|
+----+----+
| |
D E
| |
+---+---+ +---+---+
| | | |
G F C K
|
+---+---+
| |
H A
```
其中,B的后继为D,D的后继为G,G的后继为F,F的后继为E,E的后继为A,A的前驱为E,E的前驱为F,F的前驱为G,G的前驱为D,D的前驱为B,B的前驱为空。K的前驱为C,C的后继为K,H的后继为A,A的前驱为H。