201447 §6.4线索二叉树 S6.4线索二叉树 。加速作用 (②)找的后序前驱和后序后继《在后序线索树中] 在着通二叉树中，找中序后罐； 中找p的后序前驱高 对于)同样有效 i)若p的ag=1(左子时为空)，则后序前驱为p->child 对于)就必须从操开始油历。 )若p的归g=0(左子树排空)，则后序前坚为p的左孩子或右孩子 有线宗是直禁从线宗找到01。但线宗一般"向上”指向其祖先 :根是在遍历左右子树1L和R之后被访问 而二又中无向上的链，只能从开始道历侧到，环情况0。 .p的前驱必是L和R中量后一个遍历到的结点 计(p的右孩子春空)then 雪找p的中序前里 return p->rchild;∥后序前驱为p的右孩子 :中序是对称序，其方法与(1)亮全对称 else )若p的tag=1,则中序前驱为lchild return p->Ichild::后序前为p的左孩子 少找P的后序后罐建见右图) i)若*p的tag=0,则中序前驱是p的左 若p为根，无后幢，返回NULL 子树中“量右下”的结点。 )若p是其双亲右子，则p的后序后她是夏摩 的左子树 )若p是其双亲左子，但p无右兄弟，则p的 后序后缝亦为双亲 S6.4线家二叉树 S6.4线索二叉树 西找p的后序后接综 (4)遍历线京二叉 w)若p是其双亲左子，但p有右兄弟，则p的 历某次序的线家二叉树， 只要从该次序下的开始结点 后序后键是其右兄第子制中1s后序速历到的结点， 出发，反复找其后继直至终端结点为止。 它是该子制中“章左下的叶特点 中 销论：找后序前驱司 开始坤点（量左下轴点，找当前销点中序后链，真至线填的点 (p->rchild=NULL山)头结点的右指针指向开始点较方 找后序后提瑰，因为 的序 只有p的右子制为空(tag=1)时，p->rchild是线家， 可直旅线到： 找开始结点（根，找当前销点的前序后罐，直至终端结点 (p->rchild=NULL)头结点的右指针指向，端结点较方便 百测，一般须涉及p的限亲，故仅给出p时，须从 操速历， 找终州结点（根），找当前销点的后序前驱，直至开始结点 (3)找p的前序前呢和前序后维 (p>ehid=NULL,物到的是后序序列的逆序列 类似于后序的情况分析 头纳点的右指针指向开始地点较方便 讨论：找前序前驱难（涉及双亲） 时间：仍为0()，但因为非道归，略快于港归的方法 对速历面言 找前序后罐易 前序线拿制中，只需保留右姓素制即可 中序效家制中，保留左、右线康之一均可 后序线索树中，只需保留左战意即可 86.5树和森林 S6.5树和森林 1. 树、森林与二叉树的转换 1.树、森林与二叉树的转换 ①树>二叉制 ②森林=>二叉树 树中每个结点有多个孩子之二叉树只有两个孩子 ·将各树转换为二叉树（根无右兄弟，所以无右子） 长子及右邻兄弟>二叉树的左右孩子 ·将各根作为兄弟互连 节点X的长子是其左子，X的右兄弟是其右子 。每个结点仅保留与长子的连线 。所有兄弟结点间连线 。6g56000o 98999 g9999 Q (41 72014/4/7 7 §6.4 线索二叉树 ② 找* 的中序前驱  加速作用 在普通二叉树中，找*p中序后继： 对于ii）同样有效 对于 i）就必须从根开始遍历。 ∵有线索是直接从线索找到O(1)。但线索一般“向上”指向其祖先， 而二叉树中无向上的链接，只能从根开始遍历得到，最坏情况O(n)。 37 ② 找*p的中序前驱 ∵ 中序是对称序，其方法与(1)完全对称 i） 若*p的ltag = 1，则中序前驱为lchild ii）若*p的ltag = 0，则中序前驱是*p的左 子树中 “最右下”的结点。 §6.4 线索二叉树 (2) 找*p的后序前驱和后序后继(在后序线索树中) ① 找*p的后序前驱(易) i） 若*p的ltag = 1(左子树为空)，则后序前驱为p->lchild ii）若*p的ltag = 0(左子树非空)，则后序前驱为p的左孩子或右孩子 ∵根是在遍历左右子树L和R之后被访问 ∴*p的前驱必是L和R中最后一个遍历到的结点 if (p的右孩子非空) then return p->rchild; // 后序前驱为p的右孩子 38 return p->rchild; // 后序前驱为p的右孩子 else return p->lchild; //后序前驱为p的左孩子 ② 找*p的后序后继(难)(见右图) i） 若*p为根，无后继，返回NULL ii） 若*p是其双亲右子，则*p的后序后继是双亲 iii）若*p是其双亲左子，但*p无右兄弟，则*p的 后序后继亦为双亲 §6.4 线索二叉树 ② 找*p的后序后继(续) iv）若*p是其双亲左子，但*p有右兄弟，则*p的 后序后继是其右兄弟子树中1st后序遍历到的结点， 它是该子树中“最左下的叶结点” 结论：找后序前驱易 找后序后继难，因为： 只有*p的右子树为空(rtag = 1)时，p->rchild是线索， 可直接找到； 39 否则，一般须涉及*p的双亲，故仅给出*p时，须从 根遍历。 (3) 找*p的前序前驱和前序后继 类似于后序的情况分析 讨论：找前序前驱难(涉及双亲) 找前序后继易 §6.4 线索二叉树 (4) 遍历线索二叉树 遍历某次序的线索二叉树，只要从该次序下的开始结点 出发，反复找其后继直至终端结点为止。  中序 找开始结点(最左下结点)，找当前结点中序后继，直至终端结点 (p->rchild = NULL) 头结点的右指针指向开始结点较方便  前序 找开始结点(根)，找当前结点的前序后继，直至终端结点 (p >rchild = NULL) 头结点的右指针指向终端结点较方便 40 ->rchild = NULL) 头结点的右指针指向终端结点较方便  后序 找终端结点(根)，找当前结点的后序前驱，直至开始结点 (p->lchild = NULL)，得到的是后序序列的逆序列 头结点的右指针指向开始结点较方便  时间：仍为O(n)，但因为非递归，略快于递归的方法  对遍历而言 前序线索树中，只需保留右线索树即可 中序线索树中，保留左、右线索之一均可 后序线索树中，只需保留左线索即可 §6.5 树和森林 1. 树、森林与二叉树的转换 ① 树 => 二叉树 树中每个结点有多个孩子 => 二叉树只有两个孩子 长子及右邻兄弟 => 二叉树的左右孩子 节点X的长子是其左子，X的右兄弟是其右子  每个结点仅保留与长子的连线  所有兄弟结点间连线 41 §6.5 树和森林 1. 树、森林与二叉树的转换 ② 森林 => 二叉树  将各树转换为二叉树(根无右兄弟，所以无右子)  将各根作为兄弟互连 42