数据结构二叉树的线索本.pptVIP

本讲内容 为什么引入线索的概念 线索的定义 线索二叉树 线索链表 线索链表类型C描述 线索化 中序线索化举例 线索二叉树的应用 例1：中序线索二叉树的遍历算法 中序线索树的遍历算法实现 例2：二叉树的前序线索化 二叉树的前序线索化算法实现 例3:二叉树的中序线索化算法实现 例4：求出给定值x的后继结点 例4:求给定值x的后继结点 例5：求后序线索树中给定结点的直接前驱 * 第六章 线索二叉树 1.线索的定义 2.线索二叉树 3.线索链表 4.线索化 5.线索二叉树的应用 遍历二叉树是以一定规则将二叉树中结点排列成一个线性序列。 先序序列 中序序列 后序序列 遍历二叉树实质上对一个非线性结构进行线性化操作，使每一个结点（除第一个和最后一个外）在这些线性序列中有且仅有一个直接前驱和直接后继。 当以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到结点在任一遍历序列中的直接前驱和直接后继信息，这种信息只有在遍历的动态过程中才能得到。 为了解决上述问题，二叉树采用二叉树链表作为存储结构时，为了不降低存储密度，可以利用二叉链表中存储的空指针域来存放结点的直接前驱或直接后继信息，即指向直接前驱或直接后继。 结点没有左孩子 lchild指向直接前驱 前驱线索 结点没有右孩子 rchild指向直接后继 后继线索 加上线索的二叉树称之为线索二叉树。为了区分方便，在线索二叉树中，指针用实线表示，线索用虚线表示。 A B C D E G F H NULL NULL 中序线索二叉树 二叉树的另一种链式存储结构。 约定结点 在二叉链表的结点中增加两个标志域，并作如下规定： 若该结点的左子树不空，则lchild域的指针指向其左子树，且左标志域的值为“指针ltag=0”； 否则，lchild域的指针指向其“前驱”，且左标志的值为“线索ltag=1”。 若该结点的右子树不空，则rchild域的指针指向其右子树，且右标志域的值为 “指针rtag=0”；否则，rchild域的指针指向其“后继”,且右标志的值为“线索rtag=1”。 typedef struct BiThrNode { ElemType data; struct BiThrNode *lchild, *rchild; //指针或线索 int ltag, rtag; //标志域，等于0为指针，等于1为线索 } BiThrNode, *BiThrTree; lchild ltag data rtag rchild 0/1 0/1 为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域的指针指向遍历时访问的最后一个结点；反之，令二叉树遍历序列的第一个结点的lchild域的指针和最后一个结点的rchild域的指针均指向头结点。 0 1 0 A 0 thrt 0 C 1 1 F 0 1 H 1 0 0 B 1 E 0 G 1 D 1 1 1 对二叉树以某种次序遍历使其变为线索二叉树的过程叫做线索化。 线索化的实质就是将二叉链表中的空指针改为指向直接前驱或直接后继的线索。 线索化的过程即为在遍历的过程中修改空指针的过程，即在“访问根结点”处进行加线索的改造，就可实现前序、中序和后序的线索化。 线索化分类 前序线索化 中序线索化 后序线索化 A B D E G C F H 中序遍历序列：DBEGAFHC NULL NULL 方法：在遍历过程中修改空指针或先写出遍历序列，标出空指针，对照再画出线索。 例1：中序线索二叉树的遍历算法 例2:编写算法实现对二叉树的前序线索化 例3:编写算法实现对二叉树的中序线索化 例4:求中序线索树中给定值为x的结点之后继结点 例5:求后序线索树中给定结点p的直接前驱q ※ 如何寻找中序遍历中的第一个结点？ ※ 如何在中序线索二叉树中寻找结点的后继？ 若无右子树，则为后继线索所指结点； 否则为对其右子树进行中序遍历时访问的第一个结点。 左子树上处于“最左下”（没有左子树）的结点。 不借助辅助堆栈实现中序遍历，而是利用线索树来完成。 void InOrder(BiThrTree T ,void (*Visit)(TElemType e)){ p = T-lchild; // p指向根结点 while (p != T) { // 空树或遍历结束时，p==T while ( p-ltag==0 ) p = p-lchild; // 第一个结点为最左下没有左子树的结点 visit(p-data) ; while ( p-rt