Question

后序线索二叉树怎么画啊

设一颗二叉树的先序、中序遍历序列分别为：先序遍历序列：ABDFCEGH， 中序遍历序列：BFDAGEHC。1) 写出其后序遍历序列； 2) 并画出它的后序线索二叉树。 后序线索二叉树怎么画啊

Answer 1

先画出遍历序列，后根据遍历序列例如ABC，看A的右子树是否为空，如果为空，则指向B，再看B，如果B的左子树为空，则指向A，依次类推，均符合这个规律。

求后序线索二叉树中结点的后继要知道其双亲的信息，要使用栈，所以说后序线索二叉树是不完善的。

扩展资料：

线索二叉树的构建

建立线索二叉树，或者说对二叉树线索化，实质上就是遍历一棵二叉树。在遍历过程中，访问结点的操作是检查当前的左，右指针域是否为空，将它们改为指向前驱结点或后续结点的线索。为实现这一过程，设指针pre始终指向刚刚访问的结点，即若指针p指向当前结点，则pre指向它的前驱，以便设线索。

另外，在对一颗二叉树加线索时，必须首先申请一个头结点，建立头结点与二叉树的根结点的指向关系，对二叉树线索化后，还需建立最后一个结点与头结点之间的线索。

参考资料来源：百度百科-线索二叉树

Answer 2

后序：FDBGHECA

线索化：

画得不太好：后序线索化就是将后序序列中节点的前驱和后继关系用线标出来而已，途中的线都是双向的，除了指向F的线条，因为F没有前驱。

Answer 3

后序：FDBGHECA