Question

数据结构线索二叉树怎么画 ?

已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树（我求得后序为FEKGJIHDCBA） 答案 如图：（最后个F为I）

Answer 1

1、首先第一步若节点右左子树，则左链域lchild指示其左孩子（ltag=0）,否则，令左链域指示其前驱（ltag=1）。若结点有右子树，则右链域rchild指示其右孩子（rtag=0）,否则，令右链域指示其后继（rtag=1）。

2、然后击亅实现这一过程，设指针p指向当前结点，pre始终指向刚刚访问过的结点，即p的前驱，以便于修改pre的后继线索和p的前驱线索。在线索化算法中访问当前结点p来进行处理。

3、最后几是结点p的左指针域为空，则将其标志位置为1，并使p->lchild指向中序前驱结点pre（即左线索化）；结点pre的右指针域为空，则将其标志位置为1，并使pre->rchild指向中序后继结点p（即右线索化）；将pre指向刚刚访问过的结点p（即pre=p），线索化p的右子树。

Answer 2

线索二叉树：二叉树的结点上加上线索的二叉树

Answer 3

画出此二叉树，并画出它的后序序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树

Answer 4

你求得后序排列应该错了吧
应该是FEGKJIHDCBA
画法嘛，首先从前序遍历得知根是A，所以从中序遍历中知道左分支是EF，右分支是GBCHKIJD,
而前序遍历和中序遍历中E都在F之前，所以F是E的右孩子，所以可得到左分支
剩下的是前序BGCDHIKJ中序GBCHKIJD
以右分支作为一棵树看，则按照上面步骤得知B是根结点，G是左分支，剩下的右分支前序CDHIKJ中序CHKIJD……一直这样下去就能画出完整的二叉树了
然后照着树图写出后序遍历就可以了

追问

你 理解错了 我的意思是 怎么画那虚线（线索二叉树） 二叉树我会画。还有为什么是GK不是KG啊 ？

追答

后序遍历，左右根，先左，所以G要先于C，然后再从C取下去取K
后序线索二叉树的画法就是：
首先由最先的那个点，画一条虚线指向NULL（因为没有左孩子），然后看有没有右孩子，没有的话则画一条曲线指向其双亲结点，有的话就画一条曲线指向其右孩子；然后由其返回其双亲结点，如果双亲结点左右孩子都有就不画曲线，要是没有右孩子就画一条曲线指向其双亲结点……其顺序按后序遍历的顺序来画
也就是说，要是一个结点左右孩子都有，则没有从该结点出发的线索；没有左孩子或右孩子的，就有一条从该结点出发的线索；左右孩子都没的，有两条从该结点出发的线索；最先开始的那个结点（肯定没左孩子），一条线索指向NULL。