ch62遍历二叉树和线索二叉树资料.pptVIP

* 1. 有关线索二叉树的几个术语： 线索链表： 线 索： 线索二叉树： 线 索 化： 用含Tag的结点样式所构成的二叉链表。 指向结点前驱和后继的指针。 加上线索的二叉树。 对二叉树以某种次序遍历使其变为线索二叉树的过程。 线索化过程就是在遍历过程中修改空指针的过程： 将空的lchild改为结点的直接前驱； 将空的rchild改为结点的直接后继。 非空指针呢？仍然指向孩子结点（称为“正常情况”） * data A G E I D J H C F B Ltag 0 0 1 1 1 1 0 1 0 1 Rtag 0 0 0 1 0 1 0 1 1 1 A G E I D J H C F B 例1：带了两个标志的某先序遍历结果如下表所示，请画出对应的二叉树。 A Tag=1表示线索: Ltag=1表示前驱 Rtag=1表示后继 * A B C G E I D H F root 悬空？ NIL 悬空？ NIL 解：对该二叉树中序遍历的结果为: H, D, I, B, E, A, F, C, G 所以添加线索应当按如下路径进行： 为避免悬空态，应增设一个头结点 例2：画出以下二叉树对应的中序线索二叉树。 2. 线索二叉树的生成——线索化（线索二叉树的重点） * 0 0 A 0 0 C 0 0 B 1 1 E 1 1 F 1 1 G 0 0 D 1 1 I 1 1 H 注：此图中序遍历结果为: H, D, I, B, E, A, F, C, G 对应的中序线索二叉树存储结构如图所示： root * 例3：已知一棵二叉树的中序序列为cbedahgijf,后序序列为cedbhjigfa,画出该二叉树的先序线索二叉树。 线索二叉树的生成算法（递归算法见教材P134-135，自学） 目的：在遍历二叉树的过程中修改空指针，添加前驱或后继的线索，使之成为线索二叉树。 为了记下遍历过程中访问结点的先后次序，需要设置两个指针： p指针→当前结点之指针； pre指针→当前结点的前趋结点指针。 * 设计技巧：依某种顺序遍历二叉树，对每个结点p，判断其左指针是否为空，以及其前驱结点的右指针是否为空。 每次只修改前驱结点的右指针（后继）和本结点的左指针（前驱），参见P135算法6.7。 若p-lchild＝NULL,则{ p-LTag=1; p-lchild＝pre;} //p的前驱线索应存p结点的左边 若pre-rchild＝NULL, 则{ pre-RTag＝1; pre-rchild=p;} //pre的后继线索应存pre结点的右边 * 难点：在线索化二叉树中，并不是每个结点都能直接找到其后继的，当标志为0时，则需要通过一定运算才能找到它的后继。 以中序线索二叉树为例： 当RTag=1时，直接后继指针就在其rchild域内； 当RTag=0时，直接后继是遍历当前结点的右子树时访问的第一个结点，即右子树中最左下方的结点； 请注意中序遍历规则是LDR，先左再根再右 3. 线索二叉树的遍历（无需堆栈 自学） 对于线索二叉树的遍历，只要找到序列中的第一个结点，然后依次访问结点的后继直到后继为空为止。 （因为建立线索时已遍历一次，相当于线性化了！） * 5）当RTag=0时（表示有右孩子） ，此时应当从该结点的右孩子开始(p=p-rchild）查找左下角的子孙结点；即重复2） 1）设置一个有哪些信誉好的足球投注网站指针p； 2）先寻找中序遍历之首结点（即最左下角结点），方 法是：当LTag=0时（表示有左孩子），p=p-lchild; 直到LTag=1（无左孩子，已到最左下角）；首先访问p-data； 3）接着进入该结点的右子树，检查RTag 和p-rchild ； 4）若该结点的RTag=1(表示有后继线索)，则p=p- rchild ；访问p-data ;并重复4） ，直到后 继结点的RTag=0； 附：中序线索二叉树遍历步骤 （算法6.5）： 有后继找后继，无后继找右子树的最左子孙 * 有后继找后继 算法流程： return OK; p=T-lchild; p!=T p-LTag==0 p=p-lchild; visit(p-data); p-rchild!=T p-RTag==1 p=p-rchild;visit(p-data); p=p-rchild; Y N Y N Y N 先找最左子孙 找到最左子孙 无后继找右子树的最左子孙 * 第6章 树和二叉树（Tree Binary Tree） 6.1 树的基本概念 6.2 二叉树 6.3 遍历二叉树和线索二叉树 6.4