编程教学线索二叉树

1、线索二叉树J.F. Wang20110418由二叉树的先序序列、中序序列求二叉树的后序序列 先序序列为：ABCDEFG中序序列为：CBEDAFG先序序列为：ABCDEFG中序序列为：CBEDAFG由先序序列知A是根；由中序序列知CBED构成左子树，FG构成右子树。ACBEDFG先序序列为：ABCDEFG中序序列为：CBEDAFGACBEDFG同理对于左子树，由先序序列知B为根；由中序序列知C为左子树，ED为右子树。先序序列为：ABCDEFG中序序列为：CBEDAFGAEDFGBC先序序列为：ABCDEFG中序序列为：CBEDAFGAEDFGBC对于B的右子树，由先序序列知D为根，由中序序列知E

2、为左孩子先序序列为：ABCDEFG中序序列为：CBEDAFGAFGBCDE先序序列为：ABCDEFG中序序列为：CBEDAFGAFGBCDE对于A的右子树，由先序序列知F为根，由中序序列知G为右孩子先序序列为：ABCDEFG中序序列为：CBEDAFGABCDEFG先序序列为：ABCDEFG中序序列为：CBEDAFGABCDEFG则后序序列为：CEDBGFA同理，由后序序列和中序序列，也能够求出先序序列。第二部分 线索二叉树一、几个问题1、n个结点的二叉树中，有多少个空指针？一、几个问题1、n个结点的二叉树中，有多少个空指针？解答：wn个结点共有2n个指针域；w根结点不占有指针，其他n-1个结点

3、各占一个，共占有n-1个；w所以有2n-（n-1）=n+1个空指针域。一、几个问题2、二叉树的中序遍历序列是唯一的且是线性排列的。若想从二叉树中找到某个结点的前驱、后继，怎样写算法？解答：将是很复杂。有兴趣的可以试一下。一、几个问题3、能不能充分利用一下问题所提到的空指针，使得lchild指向前驱，rchild指向后继？那么这样寻找某个结点的前驱和后继将会变得简单。解答：这就是本节要介绍的线索二叉树的思想。其中原来指向左、右孩子的指针还称指针；指向前驱和后继的指针称为线索。二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f二、中序线索二叉树的

4、手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fa的前驱为空，后继为+二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f指针用实线表示；线索用虚线表示。二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f+有左右孩子，故不用考虑线索问题二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fb的前驱为+，后继为*二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fb

5、的前驱为+，后继为*二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f*有左右孩子，故不用考虑线索问题二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fc的前驱为*，后继为-二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fc的前驱为*，后继为-二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f*有左右孩子，故不用考虑线索问题二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的

6、中序遍历序列为：a+b*c-d-e/fd的前驱为-，后继为-二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fc的前驱为-，后继为-二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f-有左右孩子，故不用考虑线索问题二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fe的前驱为-，后继为/二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/fe的前驱为-，后继为/二、中序线索二叉树的手工构造方法-

7、+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f/有左右孩子，故不用考虑线索问题二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/ff的前驱为/，后继为空二、中序线索二叉树的手工构造方法-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/ff的前驱为/，后继为空-+/a*efb-cd该二叉树的中序遍历序列为：a+b*c-d-e/f这就是中序线索二叉树的形态大多数考研试题也是这样考察线索二叉树这个知识点的，即给你一棵二叉树，让你画出它的先序、中序或者后序线索二叉树。我们来考虑线索二叉树的存储问题。首先需要关注的

8、，既然lchild可能是指针也可能是线索，怎么区别呢？改变二叉树结点的存储结构。如下：lchildLTagdataRTagrchild驱为线索，指向结点的前孩子为指针，指向结点的左lchild10lchildLTag继为线索，指向结点的后孩子为指针，指向结点的右rchild10rchildRTag则刚才手工构造的线索二叉树的存储结构如下：0-00+00/01a10*01b10-01c11d11e11f1为方便起见，仿照线性表的存储结构，在二叉树的线索链表上也添加一个头结点。并令头结点的lchild为指针，指向二叉树的根结点；rchild为线索，指向遍历的最后一个结点；令遍历的第一个结点的lch

9、ild为线索，指向头结点；令遍历的最后一个结点的rchild为线索，指向头结点。添加了头结点的中序线索二叉树如下：0-00+00/01a10*01b10-01c11d11e11f110头结点同理大家可以画出二叉树的先序、中序、后序线索链表结构。下面我们讨论线索二叉树的遍历问题。三、线索二叉树的遍历线索二叉树的遍历思想大体上是：从头结点开始，先找到遍历序列上的第一个结点，然后依次找到结点的后继，直至遇到头结点为止。1、中序线索二叉树的遍历（1）寻找遍历序列的第一个结点从头结点开始，沿着lchild找到根，然后沿着沿着根的lchild一直向左到尽头，就是中序遍历的第一个结点。0-00+00/01a

10、10*01b10-01c11d11e11f110头结点0-00+00/01a10*01b10-01c11d11e11f110头结点0-00+00/01a10*01b10-01c11d11e11f110头结点0-00+00/01a10*01b10-01c11d11e11f110头结点0-00+00/01a10*01b10-01c11d11e11f110头结点中序遍历的第一个结点（2）寻找结点p的后继如果RTag=1，则rchild就指向后继；如果RTag=0，则rchild为指针，则p的后继为 rchild所指子树上的中序遍历的第一个结点（求解方法同（1）左子树p右子树（3）寻找结点p的前驱w若

11、LTag=1,则lchild所指就是前驱；w若LTag=0，则lchild是指针，则p的前驱是中序遍历其左子树的最后一个结点（即沿着p的左子树的根一直向右走，直到最后一个结点。）。左子树p右子树1235647890求结点2中序遍历的前驱1235647890求结点2的前驱1235647890求结点4的前驱1235647890求结点2的前驱1235647890求结点2的前驱结点2的前驱从上面分析过程可以看出，遍历中序线索二叉树可以不用递归的方法，也可以不采用“栈”，因此在时间上要比一般二叉树的遍历算法要简单得多。2、先序线索二叉树的遍历（1）寻找先序遍历的第一个结点就是二叉树的根。（2）寻找结点p

12、的后继如果RTag=1,则rchild所指就是p的后继；如果RTag=0，且lchild不为空，则p的后继是左子树的根；如果RTag=0，且lchild为空，则p的后继是右子树的根；左子树p右子树（3）寻找结点p的前驱若LTag=1，则lchild就是指向前驱；若LTag=0，且p是其双亲a的左孩子，则p的前驱是 其双亲a；apP左子树P右子树a右子树apP左子树P右子树a右子树（3）寻找结点p的前驱若LTag=0，且p是其双亲a的右孩子，且其双亲a无左孩子，则p的前驱是其双亲a；apP左子树P右子树apP左子树P右子树（3）寻找结点p的前驱若LTag=0，且p是其双亲a的右孩子，且其双亲a有

13、左孩子，则p的前驱是先序遍历其双亲a的左子树的最后一个结点（即左子树的最右下的叶子结点）。apP左子树P右子树apP左子树P右子树A左子树a左子树123564789求结点4先序遍历的前驱：结点4的双亲的左子树的最右下的叶子结点，即结点9。大家先序遍历一下看是不是。0从上面遍历先序线索二叉树的过程可以看出，找某个结点的后继比较方便，不用使用栈；在寻找某个结点的前驱时，由于涉及到双亲结点，所以对于二叉链表不方便，对于三叉链表比较方便。3、遍历后序线索二叉树（1）寻找后序遍历的第一个结点如果二叉树的根有左孩子，则第一个结点是后序遍历左子树的第一个结点（即左子树上最左下方那一个叶子结点）。左子树根右子

14、树123564789求二叉树后序遍历的第一个结点：根结点1的左子树上最左下那一个结点5。大家先序遍历一下看是不是。03、遍历后序线索二叉树（1）寻找后序遍历的第一个结点如果二叉树的根没有左孩子，但有右孩子，则第一个结点是后序遍历右子树的第一个结点（即右子树上最左下方那一个叶子结点）。左子树根右子树123564789求二叉树后序遍历的第一个结点：根结点1的右子树上最左下那一个结点5。大家先序遍历一下看是不是。03、遍历后序线索二叉树（1）寻找后序遍历的第一个结点如果二叉树的根没有左孩子，也没有右孩子，则第一个结点是根左子树根右子树（2）寻找结点p的后继若RTag=1，则rchild指的就是后继；

15、若RTag=0（即rchild为指针），且p是其双亲a的左孩子，且右孩子为空，则p的后继是其双亲a。apP左子树P右子树apP左子树P右子树（2）寻找结点p的后继若RTag=0（即rchild为指针），且p是其双亲的左孩子，且右孩子不为空，则p的后继是后序遍历其双亲结点的右子树的第一个结点（求解同（1）。apa右子树apa右子树（2）寻找结点p的后继若RTag=0（即rchild为指针），且p是其双亲的右孩子，则p的后继其双亲结点。aa左子树apa左子树pP左子树P右子树P左子树P右子树（3）寻找结点p的前驱如果LTag=1，则lchild指向前驱；如果LTag=0（即lchild为指针），且

16、p有右孩子，则p的前驱为后序遍历其右子树的最后一个结点，即右孩子。pp左子树pap左子树aa左子树a右子树a左子树a右子树（3）寻找结点p的前驱如果LTag=0（即lchild为指针），且p没有右孩子，则p的前驱为后序遍历其左子树的最后一个结点，即左孩子。ppaaa左子树a右子树a左子树a右子树从上面过程可以看出，遍历后序线索二叉树时，在求某个结点的前驱时比较方便；求某个结点的后继结点时，需要知道双亲的信息，对于三叉链表比较方便。四、二叉树的线索化前面，我们手工构造了一棵线索二叉树，并且对线索二叉树进行了遍历。那么怎样编写程序来把一棵二叉树构造成线索二叉树呢？我们以中序线索二叉树的线索化为例。

17、由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。为了几下遍历过程中访问结点的先后关系，附设一个全局指针变量pre始终指向刚刚访问过的结点，即若指针p指向当前访问的结点，则pre指向他的前驱。中序遍历建立中序线索二叉树的算法描述如下：void InThreading（p）/对以p为根的二叉树中序线索化如果p为空，return；InThreading（p-lchild);/中序线索化p的左子树左子树线索化后，pre恰好指向最后访问的结点，即p的前驱，现在把pre和p链起来。If（p的左孩子为空），则p的lchild为线索，且指向pre；If（pre的右孩子为空），则pre的rchild为线索，且指向p；Pre后移，指向p；InThreading（p-rchild);怎样处理头结点与遍历序列的关系。void InOrderThreading（thrt，t）/