6.3.2 线索二叉树

nullnull6.3.2 线索二叉树null一、几个讨论问题 1、n个结点的二叉树中，二叉链表有多少个空指针？null 1、n个结点的二叉树中，二叉链表有多少个空指针？ 解答： n个结点共有2n个指针域； 根结点不占有指针，其他n-1个结点各占一 个，共占有n-1个； 所以有2n-（n-1）=n+1个空指针域。null 2、二叉树的中序遍历序列是唯一的且是线性排列的。若想从二叉树中找到某个结点的前驱、后继，怎样写算法？ 解答：将是很复杂。有兴趣的可以试一下。 null3、能不能充分利用一下问题1所提到的空指针，使得前驱指针（lchild）指向前驱，后继指针（rchild）指向后继？那么这样寻找某个结点的前驱和后继将会变得简单。 解答：这就是本节要介绍的线索二叉树的思想。 其中原来指向左、右孩子的指针还称指针；指向前驱和后继的指针称为线索。 null二、中序线索二叉树的手工构造 方法 快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载 -+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fnull二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fa的前驱为空，后继为+null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/f指针用实线表示；线索用虚线表示。null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/f+有左右孩子，故不用考虑线索问题 null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fb的前驱为+，后继为*null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fb的前驱为+，后继为*null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/f*有左右孩子，故不用考虑线索问题null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fc的前驱为*，后继为-null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fc的前驱为*，后继为-null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/f-有左右孩子，故不用考虑线索问题null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fd的前驱为-，后继为-null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fd的前驱为-，后继为-null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/f-有左右孩子，故不用考虑线索问题null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fe的前驱为-，后继为/null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/fe的前驱为-，后继为/null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/f/有左右孩子，故不用考虑线索问题null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/ff的前驱为/，后继为空null二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/ff的前驱为/，后继为空null-+/a*efb-cd该二叉树的中序遍历序列为： a+b*c-d-e/f这就是中序线索二叉树的形态null 大多数考研 试题 中考模拟试题doc幼小衔接 数学试题 下载云南高中历年会考数学试题下载N4真题下载党史题库下载 也是这样考察线索二叉树这个 知识点 高中化学知识点免费下载体育概论知识点下载名人传知识点免费下载线性代数知识点汇总下载高中化学知识点免费下载 的，即给你一棵二叉树，让你画出它的先序、中序或者后序线索二叉树。null 我们来考虑线索二叉树的存储问题。 首先需要关注的，既然lchild可能是指针也可能是线索，怎么区别呢？ 改变二叉树结点的存储结构。增加标志如下：null则刚才手工构造的线索二叉树的存储结构如下：null 为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点。并令头结点的前驱指针lchild为指针，指向二叉树的根结点；后继指针rchild为线索，指向遍历的最后一个结点；令遍历的第一个结点的lchild为线索，指向头结点；令遍历的最后一个结点的rchild为线索，指向头结点。 添加了头结点的中序线索二叉树如下：null头结点null 同理大家可以画出二叉树的先序、后序线索链表结构。 下面我们讨论线索二叉树的遍历问题。null三、线索二叉树的遍历 线索二叉树的遍历思想大体上是：从头结点开始，先找到遍历序列上的第一个结点，然后依次找到结点的后继，直至遇到头结点为止。null1、中序线索二叉树的遍历 （1）寻找遍历序列的第一个结点 从头结点开始，沿着lchild找到根，然后沿着根的lchild一直向左到尽头（找到第一个LTag=1的结点为止）， 就是中序遍历的第一个结点。null头结点null头结点null头结点null头结点null头结点中序遍历的第一个结点null（2）寻找结点p的后继 如果RTag==1，则rchild就指向后继； 如果RTag==0，则rchild为指针，则p的后继为 rchild所指右子树上的中序遍历的第一个结点（即沿着p的右子树的根一直向左走，直到最后一个结点。 ）左子树p右子树null（3）寻找结点p的前驱 若LTag==1,则lchild所指就是前驱； 若LTag==0，则lchild是指针，则p的前驱是 中序遍历其左子树的最后一个结点（即沿 着p的左子树的根一直向右走，直到最后一 个结点。）。左子树p右子树null1235647890求结点2中序遍历的前驱null1235647890求结点2的前驱null1235647890求结点2的前驱null1235647890求结点2的前驱null1235647890求结点2的前驱结点2的前驱null 从上面分析过程可以看出，遍历中序线索二叉树可以不用递归的方法，也可以不采用“栈”，因此在时间上要比一般二叉树的遍历算法要简单得多。null2、后序遍历线索二叉树 （1）寻找后序遍历的第一个结点 ①如果二叉树的根有左孩子，则第一个结点是后序遍历左子树的第一个结点（即左子树上最左下方那一个叶子结点）。左子树根右子树null123564789求二叉树后序遍历的第一个结点： 根结点1的左子树上最左下那一个结点5。 大家后序遍历一下看是不是。0null2、后序遍历线索二叉树 （1）寻找后序遍历的第一个结点 ②如果二叉树的根没有左孩子，但有右孩子，则第一个结点是后序遍历右子树的第一个结点（即右子树上最左下方那一个叶子结点）。左子树根右子树null123564789求二叉树后序遍历的第一个结点： 根结点1的右子树上最左下那一个结点5。 大家后序遍历一下看是不是。0null2、后序遍历线索二叉树 （1）寻找后序遍历的第一个结点 ③如果二叉树的根没有左孩子，也没有右孩子，则第一个结点是根左子树根右子树null（2）寻找结点p的后继 ①若RTag==1，则rchild指的就是后继； ②若RTag==0（即rchild为指针），且p是其双亲a的左孩子，且右孩子为空，则p的后继是其双亲a。apP 左 子树P 右 子树apP 左 子树P 右 子树null（2）寻找结点p的后继 ③若RTag==0（即rchild为指针），且p是其双亲的左孩子，且右孩子不为空，则p的后继是后序遍历其双亲结点的右子树的第一个结点（求解同（1））。apa 右 子树apa 右 子树null（2）寻找结点p的后继 ④若RTag==0（即rchild为指针），且p是其双亲的右孩子，则p的后继其双亲结点。aa 左 子树apa 左 子树pP 左 子树P 右 子树P 左 子树P 右 子树null（3）寻找结点p的前驱 ①如果LTag==1，则lchild指向前驱； ②如果LTag==0（即lchild为指针），且p有右孩子，则p的前驱为后序遍历其右子树的最后一个结点，即右孩子。pp 左 子树pap 左 子树aa 左 子树a 右 子树a 左 子树a 右 子树null（3）寻找结点p的前驱 ③如果LTag==0（即lchild为指针），且p没有右孩子，则p的前驱为后序遍历其左子树的最后一个结点，即左孩子。ppaaa 左 子树a 右 子树a 左 子树a 右 子树null 从上面过程可以看出，遍历后序线索二叉树时，在求某个结点的前驱时比较方便；求某个结点的后继结点时，需要知道双亲的信息，对于三叉链表比较方便。null 例题：由二叉树的先序序列、中序序列求二叉树的后序序列 先序序列为：ABCDEFG 中序序列为：CBEDAFGnull先序序列为：ABCDEFG 中序序列为：CBEDAFG 由先序序列知A是根； 由中序序列知CBED构成左子树，FG构成右子树。ACBEDFGnull先序序列为：ABCDEFG 中序序列为：CBEDAFGACBEDFG同理对于左子树，由先序序列知B为根； 由中序序列知C为左子树，ED为右子树。null先序序列为：ABCDEFG 中序序列为：CBEDAFGAEDFGBCnull先序序列为：ABCDEFG 中序序列为：CBEDAFGAEDFGBC对于B的右子树，由先序序列知D为根， 由中序序列知E为左孩子null先序序列为：ABCDEFG 中序序列为：CBEDAFGAFGBCDEnull先序序列为：ABCDEFG 中序序列为：CBEDAFGAFGBCDE对于A的右子树，由先序序列知F为根， 由中序序列知G为右孩子null先序序列为：ABCDEFG 中序序列为：CBEDAFGABCDEFGnull先序序列为：ABCDEFG 中序序列为：CBEDAFGABCDEFG则后序序列为：CEDBGFAnull 同理，由后序序列和中序序列，也能够求出先序序列。练习：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。null分析： 1、由后序遍历特征，根结点必在后序序列尾部（即A）； 2、由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树的子孙（即BDCE），其右部必全部是右子树的子孙（即FHG）； 3、继而，根据后序中的DECB子树可确定B为A的左孩子，根据后序中的HGF子串可确定F为A的右孩子； 4、由中序中的BDCE可知DCE为B的右子树，再由后序中的DEC可知C为D、E的双亲，D为左孩子，E为右孩子； 5、由中序中的FHG可知HG为F的右子树，再由后序中的HG可知G为H的双亲；由中序中的HG可知H为G的左孩子。 null已知中序遍历：B D C E A F H G 已知后序遍历：D E C B H G F A（B D C E）（ F H G） （D C E）A