DS06树和二叉树03线索二叉树树和森林

1、DS06树和二叉树03线索二叉树树和森林DBCEFAECBDF二叉链表lchilddatarchildA何谓线索二叉树？Threaded Binary Tree线索二叉树：指加上线索的，原有的空左孩子域指向前驱，原有的空右孩子指向后继的二叉树指向结点“前驱和“后继的指针，称“线索；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化。在二叉链表的结点构造中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：LTag =0 lchild 域指向左孩子1 lchild 域指向前驱RTag =0 rchild 域指向右孩子1 rchild 域指向后继二叉树的二叉线

2、索存储表示/ Link=0:指针，Thread=1:线索typedef enum Link, Thread PointerTag; typedef struct BiThrNode TElemType data; struct BiThrNode *lchild, *rchild; / 左右孩子指针 PointerTag LTag, RTag; / 左右标志 BiThrNode, *BiThrTree; 二叉树的遍历方式有4种，故有4种意义下的前驱和后继，相应的有4种线索二叉树： 前序线索二叉树 中序线索二叉树 后序线索二叉树 层序线索二叉树线索二叉树a中序线索二叉树 b中序线索链表12345

3、670 1 00 2 01 3 11 4 10 5 01 6 11 7 1thrt0 1中序序列：4 2 6 5 7 1 3头指针 头结点添加头结点后，好比为二叉树建立了一个双向线索链表，即可以从第一个结点起顺后继进展遍历，也可以从最后一个结点起顺前驱进展遍历。NULLNULL为使算法设计方便，增加一个头结点。如何在中序线索树中找结点的后继？ 假设其右标志为“1，右链是线索，右链直接指向后继；比方4、6、7 假设其右标志为“0，右链是指针，其后继应为遍历其右子树时第一个访问的结点，即右子树中最左下的结点。比方2的后继为61234567如何在中序线索树中找结点的前驱？ 假设其左标志为“1，左链为

4、线索，直接指向前驱；比方3、6、7 假设其左标志为“0，前驱应为遍历左子树时最后访问的一个结点，即左子树中最右下的结点。比方1的前驱为7、2的前驱为4、5的前驱为61234567如何在后序线索树中找结点的后继或者如何在前序线索树中找结点的前驱？在后序线索树中找结点后继较复杂，P133，需知道结点双亲，即需带指向其双亲结点的指针域的三叉链表作存储构造。同理，在前序线索树中找结点前驱也需知道结点双亲。根据刚刚的分析，可以看出，在中序线索链表上遍历二叉树，要比在二叉链表上中序遍历高效，虽时间还是O (n)，但常数因子比上节的非递归遍历算法小，且不需设栈。 Status InOrderTraver_T

5、hr( BiThrTree T,Status (*Visit)(TElemType e) ) / 中序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit。/ T指向头结点，头结点的左链lchild指向根结点， p = T-lchild; /p指向根结点 while (p != T) /空树或遍历完毕时，p = = T while (p-LTag=Link) p = p-lchild; / p指向最左下结点， /即中序遍历的第一个结点 if (!Visit(p-data) return ERROR; /访问第一个结点 while (p-RTag=Thread & p-rchild!=

6、T) p = p-rchild; Visit(p-data); /顺线索访问后继结点 p = p-rchild; return OK; 0 1 00 2 01 3 11 4 10 5 01 6 11 7 1T0 1 1 Thrt空树01分析：建立线索链表，本质上就是在遍历的过程中将二叉链表中的空指针改为指向前驱或后继的线索。4.如何建立线索化链表？对二叉链表T进展中序线索化的递归算法(带头结点)Status InOrderThreading(BiThrTree &Thrt, BiThrTree T)步骤：1. 生成头结点Thrt，假设树非空，左孩子指向树根，否那么，回指自身；2. pre =

7、Thrt; 调用不带头结点的中序线索化的递归算法;3. 最后一个结点线索化指向头结点1 A B D C E111110000T/中序遍历二叉链表T，并将其中序线索化，Thrt指向头结点。Status InOrderThreading(BiThrTree &Thrt, BiThrTree T) / 建立头结点Thrt = (BiThrTree)malloc(sizeof(BiThrNode); if (!Thrt) exit(OVERFLOW); Thrt-ltag = Link; Thrt-rtag = Thread; Thrt-rchild = Thrt; / 右指针回指 if (!T) /

8、空树，左指针回指Thrt-lchild = Thrt; ThrtLinkThread011else / 非空树，进展线索化 Thrt-lchild = T;/ 头结点的lchild指向二叉链表根 pre = Thrt; / pre指向T的前驱 InThreading(T);/ 中序线索化二叉链表T pre-rchild = Thrt; / 最后一个结点线索化pre-rtag = Thread; Thrt-rchild = pre; return OK; Thrt A B D C Epre输出：B C A E D10111110000preTvoid InThreading(BiThrTree

9、p)if (p)InThreading(p-lchild); /左子树线索化 / 此时p所指结点的左子树不存在或已线索化if (!p-lchild) /左孩子为空，建立p所指结点的前驱线索 p-lchild=pre; p-ltag=Thread; if (!pre-rchild) /右孩子为空，建立pre所指结点的后继线索 pre-rchild=p;pre-rtag=Thread; pre = p; /保持pre指向p的前驱 InThreading(p-rchild); /右子树线索化 对二叉链表p进展中序线索化的递归算法(不带头结点)1 Thrt A B D C Epre1011111000

10、0prepABDECFG例：对以以下图的树按先序、后序、中序线索化第6章 树和二叉树6.1 树的定义和根本术语6.2 二叉树6.3 遍历二叉树和线索二叉树6.4 树和森林 6.4.1 树的存储构造 6.4.2 森林与二叉树的转换 6.4.3 树和森林的遍历6.6 赫夫曼树及其应用6.4.1 树的存储构造三种常用的链表构造：双亲表示法孩子表示法孩子兄弟表示法1. 双亲表示法即以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲的下标。DACREBFHGK双亲结点下标9876543210666311000-1KHGFEDCBAR树的双亲表存储表示#define MAX_TREE_S

11、IZE 100 typedef struct PTNode / 结点构造 TElemType data; int parent; / 双亲位置域 PTNode;typedef struct /树构造 PTNode nodesMAX_TREE_SIZE; int r, n; / 根结点的位置和结点个数 PTree;分析： 这种存储构造利用每个结点除根结点只有唯一双亲的性质，parent(T,x操作可在常量时间内实现。反复调用parent操作，直到遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个构造。2. 孩子表示法 多重链表+孩子链表 多重链表 由于树中每个结点可

12、能有多棵子树，那么考虑用多重链表，即结点有多个指针域，其中每个指针指向一个孩子，此时有两种结点格式：datadegreechild1child2childddatachild1child2childd采用第一种格式：指针域的个数等于树的度 多重链表中的结点是同构的，其中 d 为树的度。由于树中很多结点的度小于 d，所以链表中有很多空链域，造成空间浪费。datachild1child2childdn个结点度为k的树中必有n*(k-1)+1个空链域。采用第二种格式：指针域的个数等于结点的度 结点是不同构的，其中 d 为结点的度，degree 域的值同 d ，此时可以节省存储空间，但结点构造不一致，

13、操作不方便。datadegreechild1child2childdA 2B 3C 2E 1I 0G 0H 0F 0D 0ACBHFEDGI有没有既能节省空间又操作方便的方法呢？另一种方式：孩子链表表示法把每个结点的孩子结点用一个单链表表示。那么 n个结点有 n 个孩子链表叶子的孩子链表为空)。而 n 个头指针又组成一个线性表，为便于查找，采用顺序存储构造。365120789KHGEFRDCBA0123456789DACREBFHGK表结点孩子结点树的孩子链表存储表示typedef struct CTNode / 孩子结点int child; / 孩子对应表结点的下标 struct CTNod

14、e *next;/ 指向下一个孩子结点的指针CTNode，*ChildPtr;typedef struct / 表结点 TElemType data; ChildPtr firstchild;/ 孩子链的头指针，指向第一个孩子结点CTBox;typedef struct / 树构造 CTBox nodesMAX_TREE_SIZE; int n, r; / 结点数和根结点的位置 CTree;分析： 与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于parent(T，x)操作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。3. 孩子兄弟表示法或称二叉链表表示法。即以二叉链表作树

15、的存储构造。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。树的二叉链表孩子 - 兄弟存储表示typedef struct CSNode TElemType data; struct CSNode *firstchild , *nextsibling; CSNode, *CSTree;结点构造 firstchild data nextsiblingREKCFABGHDDACREBFHGK二叉链表孩子兄弟表示法例：分析： 这种存储构造便于实现各种树的操作。首先易于实现找结点孩子等的操作。假设为每个结点增设一个(parent)域，那么同样能方便地实现parent(T,x)操作。

16、6.4.2 森林和二叉树的转换 树、森林与二叉树之间可以互相进展转换， 即任何一个森林或一棵树都可以唯一地对应一棵二叉树，而任何一棵二叉树也能唯一地对应到一个森林或一棵树上。 正是由于这样的一一对应关系，可以把树的处理问题转化为二叉树的处理问题，从而把问题简化。 下面介绍树、森林与二叉树的互相转换。1. 树和二叉树的对应关系加线.树转换为二叉树方法ABCDEFG2.保存双亲与第一孩子连线,删去与其他孩子的连线.转动45oGDABECFABCDEGHFI(a)ABCDEGHFI(b)ABCDEGHFI(c)ABCDEGHFI(d)例：2. 森林和二叉树的对应关系 从树的二叉链表表示的定义可知，任

17、何一棵和树对应的二叉树，其右子树必空。 那么，假设把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，那么同样可导出森林和二叉树的对应关系。1森林转换成二叉树假设F=T1，T2，Tm是森林，那么可以按如下规那么转换成一棵二叉树B=ROOT，LB，RB1 假设F为空，即m=0，那么B为空二叉树。2 假设F非空，即m0，那么B的根ROOT即为森林中第一棵树的根ROOTT1，B的左子树LB是从第一棵树T1的子树森林F1=T11，T12，T1m1转换而成的二叉树；其右子树RB是从其余树的森林F=T2，T3，Tm转换而成的二叉树。转换方法： 将森林中的每棵树转换成二叉树； 从第二棵二叉树开场，依次把后

18、一棵二叉树的根结点作为前一棵二叉树根结点的右孩子，当所有二叉树连起来后，此时所得到的二叉树就是由森林转换得到的二叉树。 12BCDEGHFI（a）BCDEGHFI（b）BCDEGHFI（c）BCDEGHFI（d）二叉树转换成森林、树 假设B=ROOT，LB，RB是一棵二叉树，那么可以按如下原那么转换成森林F=T1，T2，Tm1 假设B为空，那么F为空；2 假设B非空，那么F中第一棵树T1的根ROOTT1为二叉树B的根ROOT；第一棵树T1的子树森林F1是由B的左子树LB转换而成的森林；F中除了T1之外的其余树组成的森林F=T2，T3，Tm是由B的右子树RB转换而成的森林。转换方法： 加线假设某结点x是其双亲y的左孩子，那么把结点x的右孩子、右孩子的右孩子、，都与结点y用线连起来； 去线删去原二叉树中所有的双亲结点与右孩子结点的连线； 层次调整 FHGEAICDBFHGDCEBAIFEDCBAHGI加线去线层次调整IHGBCDAFE6.4.3 树和森林的遍历1. 树的遍历：有两种次序先根(序)遍历：假设树不空，那么先访问根结点，然后依次先根遍历各棵子树。后根(序)遍历：假设树不空，那么先依次后根遍历各棵子树，然后访问根结点。例：对树进展先根遍历，获得的先根序列是：对树进展后根遍历，获得的后根序列是：ABCDEGHFIA B E