《【精品数据结构】线索二叉树.PPT.PPT》由会员分享，可在线阅读，更多相关《【精品数据结构】线索二叉树.PPT.PPT（24页珍藏版）》请在三一文库上搜索。
数据结构,第六章(中),6.3.2 线索二叉树,在二叉树的先序、中序或后序遍历序列中两个相邻的结点互称为前驱与后继。 指向前驱或后继结点的指针称为线索。 加上线索的二叉链表表示的二叉树叫线索二叉树。 对二叉树按某种遍历次序使其变为线索二叉树的过程叫线索化。,实现：在有n个结点的二叉链表中必定有n+1个空链域。在线索二叉树的结点中增加两个标志域： LTag :若 LTag=0, lchild域指向左孩子； 若 LTag=1, lchild域指向其前驱。 RTag :若 RTag=0, rchild域指向右孩子； 若 RTag=1, rchild域指向其后继。,0,0,0,0,1,1,1,1,1,1,线索链表的类型定义参见P133,0,0,0,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,1,1,按中序线索化二叉树,算法参见P134算法,1,P-C,P-C,1,1,P-D,P-D,P-E,P-D,P-E,P-D,1,P-D,1,1,遍历中序线索二叉树,算法参见P134,