数据结构第讲线索树与树和森林

数据结构第讲线索树与树和森林第1页，共46页，2023年，2月20日，星期六6.3.2线索二叉树1.何谓线索二叉树？遍历结果是求得结点的一个线性序列。指向该线性序列“前驱”和“后继”的指针，称“线索”；包含“线索”的存储结构，称为“线索链表”；与其相应的二叉树，称为“线索二叉树”；对二叉树以某种次序遍历，使其变为线索二叉树的过程，称为“线索化”。第2页，共46页，2023年，2月20日，星期六2.线索链表中结点的结构在二叉链表的结点结构中增加两个标志域，并规定：lchildLTagdataRTagrchild其中：LTag=0lchild域指示结点的左孩子1lchild域指示结点的前驱RTag=0rchild域指示结点的右孩子1rchild域指示结点的后继第3页，共46页，2023年，2月20日，星期六二叉树二叉线索存储表示typedefenum{Link,Thread}PointerThr;

//Link==0:指针，Thread==1:线索typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*rchild;

//左右孩子指针

PointerThrLTag,RTag;//左右标志}BiThrNode,*BiThrTree;第4页，共46页，2023年，2月20日，星期六3.线索二叉树图例线索二叉树及其存储结构（a）中序线索二叉树（b）中序线索链表1234567010020131141050161171thrt0

1第5页，共46页，2023年，2月20日，星期六如何在线索树中找结点的后继？结合中序线索树若其右标志为“1”，右链是线索，右链直接指示了结点的后继；若其右标志为“0”，右链是指针，其后继为右子树中最左下的结点。1234567第6页，共46页，2023年，2月20日，星期六如何在线索树中找结点的前驱？结合中序线索树

若其左标志为“1”，左链为线索，直接指示其前驱；若其左标志为“0”，左子树中最右下的结点为其前驱。1234567第7页，共46页，2023年，2月20日，星期六线索链表的中序遍历算法StatusIOTraver_T(BiThrTreeT,Status(*Visit)(TElemTypee)){//T指向头结点，头结点的左链lchild指向根结点，中序遍历

//二叉线索树T的非递归算法，对每个数据元素调用函数Visit。p=T->lchild;//p指向根结点

while(p!=T){//空树或遍历结束时，p==Twhile(p->LTag==Link)p=p->lchild;if(!Visit(p->data))returnERROR;//访问其左子树为空的结点while(p->RTag==Thread&&p->rchild!=T){p=p->rchild;Visit(p->data);}//访问后继结点p=p->rchild;}returnOK;}//IOTraver_T010020131141050161171T011第8页，共46页，2023年，2月20日，星期六4.如何建立线索化链表？由于线索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。第9页，共46页，2023年，2月20日，星期六对二叉链表p进行中序线索化的递归算法(带头结点)StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)步骤：1.生成头结点Thrt，如果树非空，头结点指向树根，否则，回指自身；2.pre=Thrt;调用不带头结点的中序线索化的递归算法;3.最后一个结点线索化（指向头结点）第10页，共46页，2023年，2月20日，星期六voidInThreading(BiThrTreep){

if(p){

InThreading(p->lchild);

//左子树线索化

if(!p->lchild){p->lchild=pre;p->ltag=Thread;}//前驱线索

if(!pre->rchild){pre->rchild=p;pre->rtag=Thread;}//后继线索

pre=p;//保持pre指向p的前驱

InThreading(p->rchild);

//右子树线索化

}}InThreading

对二叉链表p进行中序线索化的递归算法(不带头结点)0100203

4050

6

7

pre0

1p第11页，共46页，2023年，2月20日，星期六StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。

Thrt=(BiThrTree)malloc(sizeof(BiThrNode));if(!Thrt)exit(OVERFLOW);Thrt->ltag=Link;

Thrt->rtag=Thread;//建立头结点

Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//空树，左指针回指自身

else{//二叉树不为空树，进行线索化

Thrt->lchild=T;//头结点的lchild指向二叉链表根

pre=Thrt;//pre指向前驱结点

InThreading(T);

//中序线索化二叉链表Tpre->rchild=Thrt;

pre->rtag=Thread;

//最后一个结点线索化

Thrt->rchild=pre;}returnOK;}第12页，共46页，2023年，2月20日，星期六StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){Thrt=(BiThrTree)malloc(sizeof(BiThrNode));

if(!Thrt)exit(OVERFLOW);Thrt->ltag=Link;Thrt->rtag=Thread;Thrt->rchild=Thrt;if(!T)Thrt->lchild=Thrt;//空树，Thrt回指自身

ThrtLinkThread第13页，共46页，2023年，2月20日，星期六1else{Thrt->lchild=T;//头结点的lchild指向二叉链表根

pre=Thrt;//pre指向前驱结点

InThreading(T);

//中序线索化二叉链表Tpre->rchild=Thrt;

pre->rtag=Thread;

//最后一个结点线索化

Thrt->rchild=pre;

}returnOK;}

ThrtABDCEpre输出：BCAED10111110000preP=nullT第14页，共46页，2023年，2月20日，星期六ABDECFG例：对下图的树按先序、后序、中序线索化第15页，共46页，2023年，2月20日，星期六第6章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林

6.4.1树的存储结构6.4.2森林与二叉树的转换6.4.3树和森林的遍历6.6赫夫曼树及其应用第16页，共46页，2023年，2月20日，星期六6.4.1树的存储结构三种常用的链表结构：双亲表示法孩子表示法孩子兄弟表示法第17页，共46页，2023年，2月20日，星期六1.

双亲表示法即以一组连续空间存储树的结点，同时在每个结点中附设一个指示器指示其双亲结点在链表中的位置。DACREBFHGK双亲结点下标9876543210666311000-1KHGFEDCBAR第18页，共46页，2023年，2月20日，星期六树的双亲表存储表示#defineMAX_TREE_SIZE100typedefstructPTNode{//结点结构

Elemdata;intparent;//双亲位置域}PTNode;typedefstruct{//树结构

PTNodenodes[MAX_TREE_SIZE];intr,n;//根结点的位置和结点个数}PTree;第19页，共46页，2023年，2月20日，星期六分析：这种存储结构利用每个结点（除根结点）只有唯一双亲的性质，Parent(T,x）操作可在常量时间内实现。反复调用Parent操作，直到遇见无双亲的结点时，便找到了树的根。但在这种表示方式中，求结点的孩子时需遍历整个结构。第20页，共46页，2023年，2月20日，星期六2.孩子表示法由于树中每个结点可能有多棵子树，则考虑用多重链表，即结点有多个指针域，其中每个指针指向一棵子树的根结点，此时链表中的结点可以有如下两种结点格式：datadegreechild1child2…childdydatachild1child2…childdx第21页，共46页，2023年，2月20日，星期六采用第一种格式多重链表中的结点是同构的，其中dx为树的度。由于树中很多结点的度小于dx，所以链表中有很多空链域，造成空间浪费。datachild1child2…childdx第22页，共46页，2023年，2月20日，星期六采用第二种格式

多重链表中的结点是不同构的，其中

dy为结点的度，drgee

域的值同dy，此时可以节省存储空间，但操作不方便。datadegreechild1child2…childdy第23页，共46页，2023年，2月20日，星期六有没有既能节省空间又操作方便的办法呢？第24页，共46页，2023年，2月20日，星期六另一种方式把每个结点的孩子结点排列起来，看成是一个线性表，且以单链表作存储结构，则n个结点有n个孩子链表（叶子的孩子链表为空)。而n个头指针又组成一个线性表，为便于查找，采用顺序存储结构。第25页，共46页，2023年，2月20日，星期六3^6^51^2078^9^K^H^G^EFR^DC^BA0123456789DACREBFHGK第26页，共46页，2023年，2月20日，星期六树的孩子链表存储表示typedefstructCTNode

{//孩子结点intchild;structCTNode*next;}*ChildPtr;typedefstruct{//双亲结点结构Elemdata;

ChildPtrfirstchild;//孩子链的头指针}CTBox;typedefstruct{//树结构:

CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根结点的位置}CTree;第27页，共46页，2023年，2月20日，星期六分析：与双亲表示法相反，孩子表示法便于涉及孩子的操作实现，却不适用于Parent(T，x)操作。可根据某种需要，将二者结合起来，即带双亲的孩子链表。第28页，共46页，2023年，2月20日，星期六3.孩子兄弟表示法或称二叉树表示法，或称二叉链表表示法。即以二叉链表作树的存储结构。链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点。第29页，共46页，2023年，2月20日，星期六^R^E^^K^^C^FAB^G^H^D^DACREBFHGK3.孩子兄弟表示法例：第30页，共46页，2023年，2月20日，星期六树的二叉链表（孩子-兄弟）存储表示typedefstructCSNode{Elemdata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;第31页，共46页，2023年，2月20日，星期六分析：这种存储结构便于实现各种树的操作。首先易于实现找结点孩子等的操作。如果为每个结点增设一个(parent)域，则同样能方便地实现Parent(T,x)操作。第32页，共46页，2023年，2月20日，星期六6.4.2森林和二叉树的转换1.树和二叉树的对应关系由于二叉树和树都可用二叉链表作为存储结构，则以二叉链表作为媒介可导出树与二叉树之间的一个对应关系。第33页，共46页，2023年，2月20日，星期六第34页，共46页，2023年，2月20日，星期六树转换为二叉树方法：1）对每个孩子进行从左到右的排序；2）在兄弟之间加一条连线；3）对每个结点，除了左孩子外，去除其与其余孩子之间的联系；4）以根结点为轴心，将整个树顺时针转45°。第35页，共46页，2023年，2月20日，星期六ABCDEGHFIaABCDEGHFIbABCDEGHFIcABCDEGHFId第36页，共46页，2023年，2月20日，星期六2.森林和二叉树的对应关系从树的二叉链表表示的定义可知，任何一棵和树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则同样可导出森林和二叉树的对应关系。第37页，共46页，2023年，2月20日，星期六第38页，共46页，2023年，2月20日，星期六BCDEGHFIaBCDEGHFIbBCDEGHFIcBCDEGHFId第39页，共46页，2023年，2月20日，星期六已知条件：森林和二叉树的对应关系设森林F=(T1,T2,…,Tn);T1=(root，t11,t12,…,t1m);

二叉树B=(LBT,Node(root),RBT);由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ;否则，由Root(T1)对应得到Node(root);

由(t11,t12,…,t1m)对应得到LBT;

由(T2,T3,…,Tn)对应得到RBT。由二叉树转换为森林的转换规则为:若B=Φ,则F=Φ;否则，由Node(root)对应得到Root(T1);

由LBT对应得到(t11,t12,…，t1m);T1除根以外所构成的森林由RBT对应得到(T2,T3,…,Tn)；除T1之外的森林第40页，共46页，2023年，2月20日，星期六6.4.3树和森林的遍历1.树的遍历：有三条搜索路径先根(序)遍历：若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根(序)遍历：若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历：若树不空，则自上而下自左至右访问树中每个结点。第41页，共46页，2023年，2月20日，星期六例对树进行先根遍历，获得的先根序列是：对树进行后根遍历，获得的后根序列是：ABCDEGHFIABEFCDG