数据结构之树和二叉树(ppt 92页)

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,第6章 树和二叉树,6.1,树的定义和基本术语,6.2,二叉树,6.3,遍历二叉树,6.4,线索二叉树,6.5,树和森林,6.6,哈夫曼树,教学目的、,要,要求,1领会树,和,和二叉树的,类,类型定义，,理,理解树和二,叉,叉树的结构,差,差别。,2熟记,二,二叉树的,主,主要特性,，,，并掌握,它,它们的证,明,明方法。,3熟练,掌,掌握二叉,树,树的各种,遍,遍历算法,，,，并能灵,活,活运用遍,历,历算法实,现,现二叉树,的,的其它操,作,作。,4理解,二,二叉树的,线,线索化过,程,程以及在,中,中序线索,化,化树上找,给,给定结点,的,的前驱和,后,后继的方,法,法。,5熟练,掌,掌握二叉,树,树和树的,各,各种存储,结,结构及其,建,建立的算,法,法。,6学会,编,编写实现,树,树的各种,操,操作的算,法,法。,7了解,最,最优树的,特,特性，掌,握,握建立最,优,优树和赫,夫,夫曼编码,的,的方法。,6.1,树,树的定义,和,和基本术,语,语,6.1.1树的定,义,义,树是由n,（,（n0,）,）个结点,组,组成的有,限,限集合。,若,若n=0,，,，称为空,树,树；若n0，则,：,：,有一个,特,特定的称,为,为根（root）,的,的结点。,它,它只有直,接,接后继，,但,但没有直,接,接前驱；,除根结,点,点以外的,其,其它结点,可,可以划分,为,为m（m,0）个,互,互不相交,的,的有限集,合,合T,0,，T,1,，T,m-1,，每个集,合,合T,i,（i=0,1,m-1,）,）又是一,棵,棵树，称,为,为根的子,树,树，每棵,子,子树的根,结,结点有且,仅,仅有一个,直,直接前驱,，,，但可以,有,有0个或,多,多个直接,后,后继。,由此可知,，,，树的定,义,义是一个,递,递归的定,义,义，即树,的,的定义中,又,又用到了,树,树的概念,。,。,树的结构,参,参见下图,：,：,图6.1,树,树的结构,在图6.1(c),中,中，树的,根,根结点为A，该树,还,还可以分,为,为三个互,不,不相交子,集,集T,0,，T,1,，T,2,，其中T,0,=B，E，F，J，K，L，T,1,=C，G，T,2,=D，H，I，M，其,中,中的T,0,，T,1,，T,2,都是树，,称,称为图6,.,1(C),中,中树的子,树,树，而T,0,，T,1,，T,2,又可以分,解,解成若干,棵,棵不相交,子,子树。如T,0,可以分解,成,成T,00,，T,01,两个不相,交,交子集，T,00,=E，J，K，L，T,01,=F,，,，而T,00,又可以分,为,为三个不,相,相交子集T,000,，T,001,，T,002,，其中，T,000,=J,，,，T,001,=K,，,，T,002,=L,。,。,树的抽象,数,数据类型,定,定义见教,材,材P118-119,6.1.2 基本,术,术语,1. 结,点,点,指树中的,一,一个数据,元,元素，一,般,般用一个,字,字母表示,。,。,2. 度,一个结点,包,包含子树,的,的数目，,称,称为该结,点,点的度。,3. 树,叶,叶（叶子,）,）,度为0的,结,结点，称,为,为叶子结,点,点或树叶,，,，也叫终,端,端结点。,4. 孩,子,子结点,若结点X,有,有子树，,则,则子树的,根,根结点为X的孩子,结,结点，也,称,称为孩子,，,，儿子，,子,子女等。,如,如图6.1（c）,中,中A的孩,子,子为B，C，D。,5. 双,亲,亲结点,若结点X,有,有子女Y,，,，则X为Y的双亲,结,结点。,6. 祖,先,先结点,从根结点,到,到该结点,所,所经过分,枝,枝上的所,有,有结点为,该,该结点的,祖,祖先，如,图,图6-1,（,（c）中M的祖先,有,有A，D,，,，H,。,。,7. 子孙结,点,点,某一结点的子,女,女及子女的子,女,女都为该结点,子,子孙。,8. 兄弟结,点,点,具有同一个双,亲,亲的结点，称,为,为兄弟结点。,9. 分枝结,点,点,除叶子结点外,的,的所有结点，,为,为分枝结点，,也,也叫非终端结,点,点。,10. 层数,根结点的层数,为,为1，其它结,点,点的层数为从,根,根结点到该结,点,点所经过的分,支,支数目再加1,。,。,11. 树的,深,深度（高度）,树中结点所处,的,的最大层数称,为,为树的高度，,如,如空树的高度,为,为0，只有一,个,个根结点的树,高,高度为1。,12. 树的,度,度,树中结点度的,最,最大值称为树,的,的度。,13. 有序,树,树,若一棵树中所,有,有子树从左到,右,右的排序是有,顺,顺序的，不能,颠,颠倒次序。称,该,该树为有序树,。,。,14. 无序,树,树,若一棵树中所,有,有子树的次序,无,无关紧要，则,称,称为无序树。,15森林,若干棵互不相,交,交的树组成的,集,集合为森林。,一,一棵树可以看,成,成是一个特殊,的,的森林。,6.1.3,树,树的表示,1. 树形结,构,构表示法,2. 凹入法,表,表示法,图6.1（c,）,）的树的凹入,法,法表示,3. 嵌套集,合,合表示法,图6.1（c,）,）的嵌套集合,表,表示,4. 广义表,表,表示法,对图6-1（c）的树结构,，,，广义表表示,法,法可表示为：,（A（B（E,（,（J，K，L,）,），F），C,（,（G），D（H（M），I,）,）,6.1.4,树,树的性质,性质1 树,中,中的结点数等,于,于所有结点的,度,度加1。,证明：根据树,的,的定义，在一,棵,棵树中，除根,结,结点以外，每,个,个结点有且仅,有,有一个直接前,驱,驱，也就是说,，,，每个结点与,指,指向它的一个,分,分支一一对应,，,，所以，除根,结,结点以外的结,点,点数等于所有,结,结点的分支数,（,（即度数），,而,而根结点无直,接,接前驱，因此,，,，树中的结点,数,数等于所有结,点,点的度数加1,。,。,性质2 度,为,为k的树中第i层上最多有k,i-1,个结点（i1）。,下面用数学归,纳,纳法证明：,对于i=1，,显,显然成立，假,设,设对于i-1,层,层，上述条件,成,成立，即第i-1层最多有k,i-2,个结点，,对于第i层，,结,结点数最多为,第,第i-1层结,点,点数的k倍（,因,因为度为k）,，,，故第i层的,结,结点数为k,i-2,*k= k,i-1,。,性质3 深度,为,为h的 k叉,树,树最多有,个,个结,点,点。,证明：,由性质2可知,，,，若每一层的,结,结点数最多，,则,则整个k叉树,结,结点数最多，,共,共有,当一棵K叉树,上,上的结点数达,到,到,时,时，称为满K,叉,叉树。,性质4 具有n个结点的k,叉,叉树的最小深,度,度为,。,。,（ 表示取不,小,小于x的最小,整,整数）,证明：设具有n个结点的k,叉,叉树的深度为h，在该树的,前,前面h-1层,都,都是满的，即,每,每一层的结点,数,数等于k,i-1,个(1ih-1)，第h层（即最后,一,一层）的结点,数,数可能满，也,可,可能不满，这,时,时，该树具有,最,最小的深度。,由性质3知道,，,，结点数n应,满,满足下面条件,：,：,通过转换为：k,h-1,n(k-1)+1k,h,，再取以k为,底,底的对数后，,可,可以得到：,h-1log,k,(n(k-1)+1)h,即有：log,k,(n(k-1)+1)hn,，,，则结点i无,左,左孩子，否则i的左孩子为2i。即满足2in的结,点,点为叶子结点,；,；,若2i+1n，则结点i无右孩子，,否,否则i的右孩,子,子为2i+1,；,；,若结点i为,奇,奇数且不等于1，则它的左,兄,兄弟为i-1,；,；,若结点i为,偶,偶数且不等于n，它的右兄,弟,弟为i+1；,结点i所在,层,层数(层次),为,为,；,；,6.2.3,二,二叉,树,树的,存,存贮,结,结构,1.,顺,顺,序,序存,贮,贮结,构,构,按二,叉,叉树,的,的结,点,点自上,而,而下,、,、从,左,左至,右,右编,号,号，,用,用一,组,组连,续,续的,存,存储,单,单元,存,存储,。,。,若该,二,二叉,树,树为,非,非完,全,全二,叉,叉树,，,，则,必,必须,将,将相,应,应位,置,置空,出,出来,，,，使,存,存放,的,的结,果,果符,合,合完,全,全二,叉,叉树,形,形状,。,。,图6.7,二,二,叉,叉树,的,的顺,序,序存,储,储,对于,一,一棵,二,二叉,树,树，,若,若采,用,用顺,序,序存,贮,贮时,，,，当,它,它为,完,完全,二,二叉,树,树时,，,，比,较,较方,便,便,若,若为,非,非完,全,全二,叉,叉树,，,，将,会,会浪,费,费大,量,量存,贮,贮存,贮,贮单,元,元。,最,最坏,的,的非,完,完全,二,二叉,树,树是,全,全部,只,只有,右,右分,支,支，,设,设高,度,度为K，,则,则需,占,占用2,K-1,个存,贮,贮单,元,元，,2.,二,二,叉,叉链,表,表存,贮,贮结,构,构,二,二叉,链,链表,表,表示,将一,个,个结,点,点分,成,成三,部,部分,，,，一,部,部分,存,存放,结,结点,本,本身,信,信息,，,，另,外,外两,部,部分,为,为指,针,针，,分,分别,存,存放,左,左、,右,右孩,子,子的,地,地址,。,。,注：,如,如果,需,需要,倒,倒查,某,某结,点,点的,双,双亲,，,，可,以,以再,增,增加,一,一个,双,双亲,域,域（,直,直接,前,前趋,）,）指,针,针，,将,将二,叉,叉链,表,表变,成,成三,叉,叉链,表,表。,lchild,data,rchild,对于图6.7所,示,示二叉树，用二,叉,叉链表形式描述,。,。,图6.8 二叉,树,树的二叉链表表,示,示, 二叉链表的,数,数据类型,bitree.h,/二叉链表定,义,义,#include ,using namespace std;,typedefchar TElemType;,structBiTNode,TElemType data;,BiTNode*lchild,*rchild;,;,typedefBiTNode *BiTree;,void initBiTree(BiTree ,void createBiTree(BiTree ,/递归前序遍,历,历,void preOrderTraverse(BiTreeT,void(*visit)(TElemType);,/非递归前序,遍,遍历,void preOrderTraverse1(BiTree T,void (*visit)(TElemType);,/递归中序遍,历,历,void inOrderTraverse(BiTreeT,void(*visit)(TElemType);,/递归后序遍,历,历,void postOrderTraverse(BiTree T,void (*visit)(TElemType);, 二叉链表的,建,建立,为了后面遍历二,叉,叉树方便，先介,绍,绍建立二叉链表,的,的算法（假设ElemType,为,为char型,）,）。,/按先序次序,输,输入二叉树中结,点,点的值（#,表,表示空格），,/构造二叉链,表,表表示的二叉树T。,void createBiTree(BiTree &T),TElemType ch;,cinch;,if(ch=#) /,空,空,T=NULL;,else,T=new BiTNode;,if(!T),exit(1);,T-data=ch; /,生,生成根结点,createBiTree(T-lchild); /,构,构造左子树,createBiTree(T-rchild); /,构,构造右子树,6.3 遍历二,叉,叉树,遍历是树结构插,入,入、删除、修改,、,、查找和排序运,算,算的前提，是二,叉,叉树一切运算的,基,基础和核心。,所谓遍历二叉树，就是遵从某种,次,次序，访问二叉,树,树中的所有结点,，,，使得每个结点,仅,仅被访问一次。,这里提到的访,问,问是指对结点,施,施行某种操作，,操,操作可以是输出,结,结点信息，修改,结,结点的数据值等,，,，但要求这种访,问,问不破坏它原来,的,的数据结构。在,本,本书中，我们规,定,定访问是输出结,点,点信息data,，,，且以二叉链表,作,作为二叉树的存,贮,贮结构。,由于二叉树是一,种,种非线性结构，,每,每个结点可能有,一,一个以上的直接,后,后继，因此，必,须,须规定遍历的规则，并按此规则遍,历,历二叉树，最后,得,得到二叉树所有,结,结点的一个线性,序,序列。,令L、R、D分,别,别代表二叉树的,左,左子树、右子树,、,、根结点，则遍,历,历二叉树有6种,规,规则：DLR、DRL、LDR,、,、LRD、RDL、RKD。若规定二叉树中必,须,须先左后右(左右顺序不能,颠,颠倒)，则只有DLR、LDR,、,、LRD三种遍,历,历规则。DLR称为前根遍历(,或,或前序遍历、先,序,序遍历、先根遍,历,历)，LDR称为中根遍历(,或,或中序遍历)，LRD称为后根遍历(,或,或后序遍历)。,6.3.1 前,序,序遍历,所谓前序遍历，,就,就是根结点最先,遍,遍历，其次左子,树,树，最后右子树,。,。,1. 递归遍历,前序遍历二叉树,的,的递归遍历算法,描,描述为：,若二叉树为空，,则,则算法结束；,否则,输出根结点；,前根遍历左子,树,树;,前根遍历右子,树,树。,/ 先序递归,遍,遍历T，对每个,结,结点调用函数Visit一次且,仅,仅一次,void preOrderTraverse(BiTreeT,void(*visit)(TElemType),if(T)/ T不空,visit(T-data); / 先访,问,问根结点,preOrderTraverse(T-lchild,visit);/ 再先序遍,历,历左子树,preOrderTraverse(T-rchild,visit);/ 最后先序,遍,遍历右子树,2. 非递归遍,历,历,利用一个一维数,组,组作栈，来存贮,二,二叉链表中结点,，,，算法思想为：,从二叉树根结点,开,开始，沿左子树,一,一直走到末端(,左,左孩子为空)为,止,止，在走的过程,中,中，访问所遇结,点,点，并依次把所,遇,遇结点进栈，当,左,左子树为空时，,从,从栈顶退出某结,点,点，并将指针指,向,向该结点的右孩,子,子。如此重复，,直,直到栈为空或指,针,针为空止。,/前序遍历二,叉,叉树T的非递归,算,算法(利用栈),，,，对每个数据元,素,素调用函数Visit,void preOrderTraverse1(BiTree T,void (*visit)(TElemType),BiTrees100;,int top=0; /top为栈顶指,针,针,while(T!=NULL)|(top0),while(T!=NULL),visit(T-data);,stop+=T;,T=T-lchild;,T=s-top;,T=T-rchild;,6.3.2 中,序,序遍历,所谓中序遍历，,就,就是根在中间，,先,先左子树，然后,根,根结点，最后右,子,子树。,中序遍历二叉树,的,的递归遍历算法,描,描述为：,若二叉树为空，,则,则算法结束；,否则,中根遍历左子,树,树;,输出根结点;,中根遍历右子,树,树。,/中序递归遍,历,历T,对每个结,点,点调用函数Visit一次且仅,一,一次,void inOrderTraverse(BiTreeT,void(*visit)(TElemType),if(T),inOrderTraverse(T-lchild,visit); / 先中序遍历,左,左子树,visit(T-data); / 再访,问,问根结点,inOrderTraverse(T-rchild,visit); / 最后中序遍,历,历右子树,6.3.3 后,序,序遍历,所谓后序遍历，,就,就是根在最后，,即,即先左子树，然,后,后右子树，最后,根,根结点。,后序遍历二叉树,的,的递归遍历算法,描,描述为：,若二叉树为空，,则,则算法结束；,否则,后根遍历左子,树,树:,后根遍历历子,树,树;,访问根结点。,/后序递归遍,历,历T，对每个结,点,点调用函数Visit一次且仅,一,一次,void postOrderTraverse(BiTree T,void (*visit)(TElemType),if(T),inOrderTraverse(T-lchild,visit); / 后序遍历左,子,子树,inOrderTraverse(T-rchild,visit); / 再后序遍历,右,右子树,visit(T-data); / 最后,访,访问根结点,6.3.4,按,按层次,遍,遍历,对于一,棵,棵二叉,树,树，若,规,规定遍,历,历顺序,为,为从上,到,到下(,上,上层遍,历,历完才,进,进入下,层,层)，,从,从左到,右,右(同,一,一层从,左,左到右,进,进行，,这,这样的,遍,遍历称,为,为按层,次,次遍历,。,。,下面用,一,一个一,维,维数组,来,来模拟,队,队列，,实,实现二,叉,叉树的,层,层次遍,历,历。,/层,序,序遍历T(利,用,用队列),对,每,每个结,点,点调用,函,函数Visit一次,且,且仅一,次,次,void levelOrderTraverse(BiTreeT,void (*visit)(TElemType),BiTreeq100,p;,intf,r;/f,r类似,于,于头尾,指,指针,q0=T;,f=0;,r=1;,while(fdata);,if(p-lchild!=NULL),qr+=p-lchild;/,入,入队,if(p-rchild!=NULL),qr+=p-rchild;/,入,入队,6.4,线,线索,二,二叉树,6.4.1,线,线索的,概,概念,通过前,面,面介绍,的,的二叉,树,树可知,，,，遍历,二,二叉树,实,实际上,就,就是将,树,树中所,有,有结点,排,排成一,个,个线性序,列,列（即非,线,线性结,构,构线性,化,化），,在,在这样,的,的线性,序,序列中,，,，很容,易,易求得,某,某个结,点,点在某,种,种遍历,下,下的直,接,接前驱,和,和后继,。,。然而,，,，有时,我,我们希,望,望不进,行,行遍历,就,就能快,速,速找到,某,某个结,点,点在某,种,种遍历,下,下的直,接,接前驱,和,和后继,，,，这样,，,，就应,该,该把每,个,个结点,的,的直接,前,前驱和,直,直接后,继,继记录,下,下来。,为了做,到,到这一,点,点，可,以,以在原,来,来的二,叉,叉链表,结,结点中,，,，再增,加,加两个,指,指针域,，,，一个,指,指向前,驱,驱，一,个,个指向,后,后继，,但,但这样,做,做将会,浪,浪费大,量,量存贮,单,单元，,存,存贮空,间,间的利,用,用率相,当,当低(,一,一个结,点,点中有4个指,针,针，1,个,个指左,孩,孩子，1个指,右,右孩子,，,，1个,指,指前驱,，,，1个,指,指后继)，而,原,原来的,左,左、右,孩,孩子域,有,有许多,空,空指针,又,又没有,利,利用起,来,来（在,有,有n个,结,结点的,二,二叉链,表,表中必,定,定存在n+1,个,个空链,域,域）。,为了不,浪,浪费存,存,存贮空,间,间，我,们,们利用,原,原有的,孩,孩子指,针,针为空,时,时来存,放,放直接,前,前驱和,后,后继，,这,这样的,指,指针称,为,为线索，加,线,线索的,过,过程称,为,为线索,化,化，加,了,了线索,的,的二叉,树,树，称,为,为线索二,叉,叉树，对应,的,的二叉,链,链表称,为,为线索二,叉,叉链表。,在线索,二,二叉树,中,中，由,于,于有了,线,线索，,无,无需遍,历,历二叉,树,树就可,以,以得到,任,任一结,点,点在某,种,种遍历,下,下的直,接,接前驱,和,和后继,。,。但是,，,，我们,怎,怎样来,区,区分孩,子,子指针,域,域中存,放,放的是,左,左、右,孩,孩子信,息,息还是,直,直接前,驱,驱或直,接,接后继,信,信息呢?为此,，,，在二,叉,叉链表,结,结点中,，,，还必,须,须增加,两,两个标,志,志域ltag,、,、rtag。,ltag和rtag,定,定义如,下,下：,这样，,二,二叉链,表,表中每,个,个结点,还,还是有5个域,，,，但其,中,中只有2个指,针,针，较,原,原来的4个指,针,针要方,便,便。增,加,加线索,后,后的二,叉,叉链表,结,结点结,构,构可描,述,述如下,：,：,lchild,ltag,data,rtag,rchild,前序序,列,列为：ABCD。,图 前,序,序线索,中序序,列,列为：BADC。,图 中,序,序线索,后序序,列,列为：BDCA。,图 后,序,序线索,6.4.3,线,线索的,算,算法实,现,现,在此，,仅,仅介绍,中,中序线,索,索二叉,树,树的算,法,法实现,。,。,为方便,起,起见，,依,依照线,性,性表的,存,存储结,构,构，在,二,二叉树,的,的线索,链,链表上,也,也添加,一,一个头,结,结点，,并,并令其lchild,域,域的指,针,针指向,二,二叉树,的,的根结,点,点，其rchild,域,域的指,针,针指向,中,中序遍,历,历时访,问,问的最,后,后一个,结,结点，,并,并令二,叉,叉树中,序,序序列,中,中的第,一,一个结,点,点的lchild域,指,指针和,最,最后一,个,个结点,的,的rchild域的,指,指针均,指,指向头,结,结点。,图 中,序,序线索,链,链表（,中,中序序,列,列为：BADC）,由于线,索,索化的,实,实质是,将,将二叉,链,链表中,的,的空指,针,针改为,指,指向前,驱,驱或后,继,继的线,索,索，而,前,前驱或,后,后继的,信,信息只,有,有在遍,历,历时才,能,能得到,，,，因此,线,线索化,的,的过程,即,即为在,遍,遍历的,过,过程中,修,修改空,指,指针的,过,过程。,为了记,下,下遍历,过,过程中,访,访问结,点,点的先,后,后关系,，,，需附,设,设一个,指,指针pre始终指,向,向刚刚,访,访问过,的,的结点,。,。,1.,线,线索链,表,表类型,定,定义,inthreading.h,#include,usingnamespacestd;,typedef charTElemType;,enum PointerTagLink,Thread;/Link=0:指针,，,，Thread=1:线,索,索,structBiThrNode,TElemTypedata;,BiThrNode*lchild,*rchild;,PointerTag ltag,rtag;,;,typedef BiThrNode*BiThrTree;,void createBiThrTree(BiThrTree,void preOrderTraverse(BiThrTree T,void(*visit)(TElemType);,BiThrNode* inOrderThreading(BiThrTree T);,void inTraverseThr(BiThrTree T,void(*visit)(TElemType);,2.,实,实现,inthreading.cpp,#includeinthreading.h,/按,先,先序次,序,序输入,二,二叉树,中,中结点,的,的值（#,表,表示空,格,格），,构,构造二,叉,叉线索,树,树T,void createBiThrTree(BiThrTree&T),TElemTypech;,cinch;,if(ch=#)/,空,空,T=NULL;,else,T=newBiThrNode;,if(!T),exit(1);,T-data=ch;/,生,生成根,结,结点,createBiThrTree(T-lchild);/,构,构造,左,左子树,if(T-lchild) / 有,左,左孩子,T-ltag=Link;,createBiThrTree(T-rchild);/,构,构造,右,右子树,if(T-rchild) / 有,右,右孩子,T-rtag=Link;,/,先,先序递,归,归遍历T,对,每,每个结,点,点调用,函,函数Visit一次,且,且仅一,次,次,void preOrderTraverse(BiThrTree T,void(*visit)(TElemType),if(T)/T不,空,空,visit(T-data);/,先,先访,问,问根结,点,点,preOrderTraverse(T-lchild,visit); / 再,先,先序遍,历,历左子,树,树,preOrderTraverse(T-rchild,visit); / 最,后,后先序,遍,遍历右,子,子树,BiThrTreepre;/,全,全局变,量,量,始,终,终指向,刚,刚刚访,问,问过的,结,结点,void inThreading(BiThrTreep)/,中,中序,遍,遍历进,行,行中序,线,线索化,if(p),inThreading(p-lchild);/,左,左子树,线,线索化,if(!p-lchild)/ 没有,左,左孩子,p-ltag=Thread;/ 前,驱,驱线索,p-lchild=pre; / 左孩,子,子指针指,向,向前驱,if(!pre-rchild) /,前,前驱没,有,有右孩子,pre-rtag=Thread; /,后,后继线,索,索,pre-rchild=p;,/ 前,驱,驱右孩子,指,指针指向,后,后继(当,前,前结点p),pre=p; / 保持pre始,终,终指向刚,刚,刚访问过,的,的结点,inThreading(p-rchild);/ 右,子,子树线索,化,化,/中序,遍,遍历二叉,树,树T,并,将,将其中序,线,线索化,BiThrNode* inOrderThreading(BiThrTree T),BiThrNode* Thrt=newBiThrNode;/Thrt指向,头,头结点,Thrt-ltag=Link;,Thrt-rtag=Thread;,Thrt-rchild=Thrt;/右指,针,针回指,if(!T)/若,二,二叉树空,，,，则左指,针,针回指,Thrt-lchild=Thrt;,else,Thrt-lchild=T;,pre=Thrt;,inThreading(T);/中,序,序遍历进,行,行中序线,索,索化,pre-rtag=Thread; /,最,最后一个,结,结点线索,化,化,pre-rchild=Thrt;,Thrt-rchild=pre;,return Thrt;,/中序,遍,遍历二叉,线,线索树T(头结点)的非递,归,归算法,voidinTraverseThr(BiThrTreeT,void(*visit)(TElemType),BiThrTree p;,p=T-lchild;/p指,向,向根结点,while(p!=T)/空树,或,或遍历结,束,束时,p=T,while(p-ltag=Link),p=p-lchild;,visit(p-data);/访,问,问左子树,为,为空的结,点,点,while(p-rtag=Thread&p-rchild!=T),p=p-rchild;,visit(p-data);/访问,后,后继结点,p=p-rchild;,6.5,树,树和森林,6.5.1 树的,存,存储结构1.,双,双亲表示,法,法,它是以一,组,组连续的,存,存储单元,来,来存放树,中,中的结点,，,，每个结,点,点有两个,域,域：一个,是,是data域，存,放,放结点信,息,息，另一,个,个是parent,域,域，用来,存,存放双亲,的,的位置(,指,指针)。,树的双亲,表,表示法,2. 孩,子,子表示法,将一个结,点,点所有孩,子,子链接成,一,一个单链,表,表形，而,树,树中有若,干,干个结点,，,，故有若,干,干个单链,表,表，每个,单,单链表有,一,一个表头,结,结点，所,有,有表头结,点,点用一个,数,数组来描,述,述。,树的孩子,表,表示法,3. 双,亲,亲孩子表,示,示法,将第1、2两种方,法,法结合起,来,来，则得,到,到双亲孩,子,子表示法,。,。,双亲孩子,表,表示法,4. 孩,子,子兄弟表,示,示法,类似于二,叉,叉链表，,但,但第一根,链,链指向第,一,一个孩子,，,，第二根,链,链指向下,一,一个兄弟,。,。,孩子兄弟,表,表示法,6.5.2 树、,森,森林和二,叉,叉树的转,换,换,1. 树,转,转换成二,叉,叉树（孩,子,子-兄,弟,弟表示法,）,）,可以分为,三,三步：,加线,将树中同,一,一结点的,兄,兄弟相连;,抹线,保留结点,的,的最左孩,子,子连线，,删,删除其它,孩,孩子连线,；,；,旋转,将同一孩,子,子的连线,绕,绕左孩子,旋,旋转45,度,度角。,讨论：二,叉,叉树怎样,还,还原为树,？,？,要点：逆,操,操作，把,所,所有右孩,子,子变为兄,弟,弟！,树转换成,二,二叉树,2. 森,林,林转换成,二,二叉树,将森林,中,中每一棵,树,树分别转,换,换成二叉,树,树；,合并：,使,使第n棵,树,树接入到,第,第n-1,棵,棵的右边,并,并成为它,的,的右子树,，,，第 n-1 棵,二,二叉树接,入,入到第n-2 棵,的,的右边并,成,成为它的,右,右子树，,，第2,棵,棵二叉树,接,接入到第1棵的右,边,边并成为,它,它的右子,树,树，直到,最,最后剩下,一,一棵二叉,树,树为止。,森林转换,成,成二叉树,3. 二,叉,叉树还原,成,成树或森,林,林,右链断,开,开,将二叉树,的,的根结点,的,的右链及,右,右链的右,链,链等全部,断,断开，得,到,到若干棵,无,无右子树,的,的二叉树,。,。,二叉树,还,还原成树,将中得,到,到的每一,棵,棵二叉树,都,都还原成,树,树（与树,转,转换成二,叉,叉树的步,骤,骤刚好相,反,反）。,二叉树还,原,原成森林,的,的过程,6.5.3 树和,森,森林的遍,历,历,在树和森,林,林中，一,个,个结点可,能,能有两棵,以,以上的子,树,树，所以,不,不宜讨论,它,它们的中,序,序遍历，,即,即树和,森,森林只有先序,遍,遍历和后,序,序遍历。,1. 先,序,序遍历, 树的,先,先序遍历,若树非空,，,，则先访,问,问根结点,，,，然后依,次,次先序遍,历,历各子树,。,。, 森林,的,的先序遍,历,历,若森林非,空,空，则先,访,访问森林,中,中第一棵,树,树的根结,点,点，再先,序,序遍历第,一,一棵树各,子,子树，接,着,着先序遍,历,历第二棵,树,树、第三,棵,棵树、,、,、直到最,后,后一棵树,。,。,2. 后,序,序遍历, 树的,后,后序遍历,若树非空,，,，则依次,后,后序遍历,各,各子树，,最,最后访问,根,根结点。, 森林,的,的后序遍,历,历,按顺序后,序,序遍历森,林,林中的每,一,一棵树。,另外，请,注,注意，树,和,和森林的,先,先序遍历,等,等价于它,转,转换成的,二,二叉树的,先,先序遍历,，,，树和森,林,林的后序,遍,遍历等价,于,于它转换,成,成的二叉,树,树的中序,遍,遍历。,6.6,哈,哈夫曼树,6.6.1 基本,术,术语,1. 路,径,径和路径,长,长度,在一棵树,中,中，从一,个,个结点往,下,下可以达,到,到的孩子,或,或子孙结,点,点之间的,通,通路，称,为,为路径。通路中,分,分支的数,目,目称为路径长度。,若规定根,结,结点的层,数,数为1，,则,则从根结,点,点到第L,层,层结点的,路,路径长度,为,为L-1,。,。,2. 结点的,权,权及带权路径,长,长度,若将树中结点,赋,赋给一个有着,某,某种含义的数,值,值，则这个数,值,值称为该结点,的,的权。,结点的带权路,径,径长度为：从,根,根结点到该结,点,点之间的路径,长,长度与该结点,的,的权的乘积。,3. 树的带,权,权路径长度,树的带权路径长度规定为所有叶,子,子结点的带权,路,路径长度之和,，,，记为,其中n 为叶,子,子结点数目，w,k,为第k个叶子,结,结点的权值，l,k,为第k个叶子,结,结点的路径长,度,度。,4. 哈夫曼,树,树,在一棵二叉树,中,中，若带权路,径,径长度达到最,小,小，称这样的,二,二叉树为最优二叉树，也称为哈夫,曼,曼树(Huffman tree)。,例如，给定叶,子,子结点的权分,别,别为1,3,5,7，则可,以,以得到如下图,所,所示的不同二,叉,叉树。,具有不同带权,路,路径长度的二,叉,叉树,在哈夫曼树中,，,，权值大的结,点,点离根最近。,6.6.2,哈,哈夫曼树构造,假设有n个权,值,值，则构造出,的,的哈夫曼树有n个叶子结点,。,。 n个权值,分,分别设为 w,1,w,2,w,n,，则哈夫曼树,的,的构造规则为,：,：,将w,1,w,2,w,n,看成是有n,棵,棵树的森林(,每,每棵树仅有一,个,个结点)；,在森林中选,出,出两个根结点,的,的权值最小的,树,树合并，作为,一,一棵新树的左,、,、右子树，且,新,新树的根结点,权,权值为其左、,右,右子树根结点,权,权值之和；,从森林中删,除,除选取的两棵,树,树，并将新树,加,加入森林；,重复、,步,步，直到森林,中,中只剩一棵树,为,为止，该树即,为,为我们所求得,的,的哈夫曼树。,下面给出哈夫,曼,曼树的构造过,程,程，假设给定,的,的叶子结点的,权,权分别为1,5,7,3，,则,则构造哈夫曼,树,树过程如图所,示,示。,哈夫曼树构造,的,的过程,从上图可知，n 个权值构,造,造哈夫曼树需n-1次合并,，,，每次合并，,森,森林中的树数,目,目减1，最后,森,森林中只剩下,一,一棵树，即为,我,我们求得的哈,夫,夫曼树。,6.6.3,哈,哈夫曼树的应,用,用,1. 哈夫曼,编,编码,通信中，可以,采,采用0、1的,不,不同排列来表,示,示不同的字符,，,，称为二进制编码。而哈夫曼树,在,在数据编码中,的,的应用，是数,据,据的最小冗余,编,编码问题，它,是,是数据压缩学,的,的基础。若每,个,个字符出现的,频,频率相同，则,可,可以采用等长,的,的二进制编码,，,，若频率不同,，,，则可以采用,不,不等长的二进,编,编码，频率较,大,大的采用位数,较,较少的编码，,频,频率较小的字,符,符采用位数较,多,多的编码，这,样,样可以使字符,的,的整体编码长度,最,最小，这就是最小,冗,冗余编码的问,题,题。,而哈夫曼编码,就,就是一种不等长的二进,制,制编码，且哈夫曼树,是,是一种最优二,叉,叉树，它的编,码,码也是一种最,优,优编码，在哈,夫,夫曼树中，规,定,定往左编码为0，往右编码,为,为1，则得到,叶,叶子结点编码,为,为从根结点到,叶,叶子结点中所,有,有路径中0和1的顺序排列,。,。,例如，给定权1,5,7,3，得到,的,的哈夫曼树及,编,编码见下图(假定权值就,代,代表该字符名,字,字)。,哈夫曼编码,2. 哈夫曼,译,译码,在通信中，若,将,将字符用哈夫,曼,曼编码形式发,送,送出去，对方,接,接收到编码后,，,，将编码还原,成,成字符的过程,，,，称为哈夫曼,译,译码。,