数据结构-树课件

第五章树本章内容：

*树的定义和基本操作；

*

二叉树的定义及遍历、存储结构；

*树的应用；重点：

*树的定义

*二叉树的定义及遍历序列

内容§5.1树的定义和基本术语§5.2二叉树的定义及存储结构§5.3二叉树的遍历§5.4树的存储§5.5树的应用

§5.1树的定义和基本术语一、树的定义树是由n个结点构成的有限集合。

当n=0时，称为空树。在一棵非空树中（n>0）中，有且仅有一个特定的结点，称根的结点；其余结点可分为m个（m≥0）互不相交的集合T1，T2……Tm，其中，每一个集合本身又是一棵树,且称为根的子树。※

特点：树中至少有一个结点—根,它没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点；树中各子树是互不相交的集合，树中所有结点可以有零个或多个后继结点。有限集合T1，T2……Tm应该“互不相交”，即任意两个集合不能有相重的结点。

※树的各个结点有不同层次关系，这种关系通常用图形表示，但与自然界的树木相反，习惯上将整棵树的根画在最上层，如图5.1所示ABCDEFGHIJKLM有子树的树根子树A只有根结点的树图5.1二、树的相关术语结点(node)——表示树中的元素，包括数据项及若干指向其子树的分支结点的度(degree)——结点拥有的子树个数叶子(leaf)——度为0的结点孩子(child)——结点子树的根称为该结点的孩子双亲(parents)——孩子结点的上层结点叫该结点的~兄弟(sibling)——同一双亲的孩子树的度——一棵树中最大的结点度数※结点的层次(level)——从根结点算起，根为第一层，它的孩子为第二层……※深度(depth)——树中结点的最大层次数※森林(forest)——m(m0)棵互不相交的树的集合※有序树－

树中结点的各子树从左到右是有次序的，否则为无序树。例：

如下图5.2所示，回答问题：ABCDEFGHIJKLM结点A的度：3结点B的度：2结点M的度：0树的度：3结点A的孩子：B，C，D结点B的孩子：E，F结点A的层次：1结点M的层次：4叶子：K，L，F，G，M，I，J结点I的双亲：D结点L的双亲：E结点B，C，D为兄弟结点K，L为兄弟结点F，G为堂兄弟结点A是结点F，G的祖先树的深度：4图5.2三、树的表示方法

1、直观表示法：图5.3表示法

2、文氏图法：hbacgdefijijdfghabe3、嵌套括号法

4、凹入表示法a(b(d,e(i,j),c(g,h)))abdeijfcgh四、树的基本操作

见书上P68§5.2二叉树一、二叉树的定义和基本操作

1、二叉树的定义一个二叉树是n个结点的有限集合（n≥0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。由上述定义可知，二叉树可以是空集，其根可以有空的左子树或右子树，或者左、右子树皆为空。

※特点：

(1)每个结点至多有二棵子树(即不存在度大于2的结点);(2)二叉树的子树有左、右之分，且其次序不能任意颠倒;一般地，二叉树有五种基本形态，如图5.3所示。A只有根结点的二叉树空二叉树AB右子树为空AB左子树为空ABC左、右子树均非空图5.3

2、二叉树的基本操作

见书上P70

3、几种特殊的二叉树

(1)满二叉树：

定义1：在一个二叉树中，若第i层的结点数为2i-1，则称此层的结点数是满的，当树中的每一层都是满的，则称此二叉树为满二叉树。

定义2：如果一个二叉树中，除最下一层的各结点度数为0以外，其它各层结点的度数均等于2，则此二叉树为满二叉树。

特点：每一层上的结点数都是最大结点数。1231145891213671014151234567123114589126710123456满二叉树完全二叉树(2)完全二叉树：

定义：一颗深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号（自左而右）从1至n的结点一一对应时，称为~。

特点：※深度为k的完全二叉树，其前k-1层是一颗满二叉树；※最后第k层的结点都尽量排在靠左的位置上。二、二叉树的性质

1、性质1：证明：用归纳法证明之

i=1时，只有一个根结点，是对的假设对所有j(1j<i)命题成立，即第j层上至多有个结点那么，第i-1层至多有个结点又二叉树每个结点的度至多为2第i层上最大结点数是第i-1层的2倍，即故命题得证2、性质2一颗深度为k的二叉树中，最多有2k-1个结点(k1)证明：由性质1，可得深度为k的二叉树最大结点数是：3、性质3：

对任何一棵二叉树，如果其叶子结点数为n0，度为2的结点数为n2，则n0=n2+1证明：n1为二叉树T中度为1的结点数因为：二叉树中所有结点的度均小于或等于2所以：其结点总数n=n0+n1+n2

又二叉树中，除根结点外，其余结点都只有一个分支进入设B为分支总数，则n=B+1

又：分支由度为1和度为2的结点射出，B=n1+2n2

于是，n=B+1=n1+2n2+1=n0+n1+n2n0=n2+14、性质4：5、性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号，则对任一结点i(1in)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是i/2(2)如果2in，则其左孩子是2i；如果2i>n，则结点i无左孩子；(3)如果2i+1n，则其右孩子是2i+1；如果2i+1>n，则结点i无右孩子；作业1:书上P871、4、5三、二叉树的存储结构

1、顺序存储结构实现：按满二叉树的结点层次编号（从上至下，从左至右），依次存放二叉树中的数据元素，即将编号为i的结点存入一维数组的第i个单元。例如：一般二叉树的存储abcdefgabcde^^^^fg1234567891011特点：结点间关系蕴含在其存储位置中,即这种次序应能反映结点间的逻辑关系;浪费空间，适于存储满二叉树和完全二叉树.●应用：

◆由二叉树，画出此二叉树的存储结构

◆由二叉树的存储结构画出此二叉树Exercise1:Key:Exercise2:12345678910111213abc^de^^^f^^gabcedfgKey:

2、链式存储结构对于非完全二叉树，可以采用链式，链表的头指针均指向根结点。●二叉链表

结点结构：

通常每个结点中设置三个域,即数据（值）域、左指针域和右指针域，其结点结构如下：typedefstructnode{datatypedata;

structnode*lchild,*rchild;}JD;结点定义：ABCDEFG在n个结点的二叉链表中，有n+1个空指针域lchilddatarchild

A^B^C^

D^E^F^^G^例如：●三叉链表结点结构：lchilddataparentrchildABCDEFG

A^^

B

C^

D

E^F^^G^

§5.3二叉树的遍历一、遍历的概念1、遍历(Traversal)是指按一定的规律访问树的每个结点，且每个结点只被访问一次的过程，即找一个完整而有规律的走法，将非线性结构的树中的结点排列成一个线性序列的过程。2、遍历的常用方法：先根（序）遍历：先访问树的根结点，然后依次先根遍历根的每棵子树；后根（序）遍历：先依次遍历每棵子树，然后访问根结点；●中序遍历：先依次访问树的左子树，根结点，然后访问树的右子树；按层次遍历：先访问第一层上的结点，然后依次遍历第二层，……第n层的结点。二、二叉树的遍历

一个非空的二叉树由根结点及左、右子树这三个基本部分组成，因此若能依次遍历这三部分，便是遍历了整个二叉树。可以按某种次序执行三个操作：访问结点本身，遍历该结点左子树，遍历该结点右子树，操作排列次序：①左、根、右；③

根、左、右；⑤

左、右、根；②右、根、左；④

根、右、左；⑥

右、左、根；

◆由于实际问题一般都是要求左子树较右子树先遍历，故只采用其中①、③、⑤三种遍历次序，分别称为中序遍历、先序遍历和后序遍历。

◆对于用顺序法表示的二叉树，各结点在数组中的编号很有规律，其遍历较容易进行，但对于用链式存储结构表示的二叉树，进行遍历就复杂一些。

◆三种遍历次序以递归的形式定义：1、先序（Preorder）遍历若遍历的二叉树不为空，则依次执行下列操作：访问根结点；先序遍历左子树；先序遍历右子树。

2、中序（Inorder）遍历若遍历的二叉树不为空，则依次执行下列操作：中序遍历左子树；访问根结点；中序遍历右子树。

3、后序（Postorder）遍历若遍历的二叉树为空，执行空操作；否则依次执行下列操作：后序遍历左子树；后序遍历右子树；访问根结点。例：按不同的遍历方法，写出二叉树遍历所得到的结点序列。ADBC>>DDLRADLRDLR>B>>CDLR◆先序遍历:◆先序遍历序列：ABDC◆中序遍历:◆中序遍历序列：BDACLDRBLDRLDR>A>>D>>CLDRADBCADBC◆后序遍历:◆后序遍历序列：DBCA

LRDLRDLRDA>>D>>CLRDExercise1:-+/a*b-efcdKey:

先序：-+a*b-cd/ef

中序：a+b*c-d-e/f

后序：abcd-*+ef/-写出下列二叉树的三种序列。Exercise2:书上，P87Exercise3:

已知一个二叉树的前序和中序分别为ABCDEFGH和BDCEAFHG，请画出此二叉树。Key3:三、二叉树遍历的算法typedefstructnode{datatypedata;

structnode*left,*right;}btree;链式存储结构的结点定义如下：◆先序遍历递归算法：voidpreorder(JD*bt){if(bt!=NULL){printf("%d\t",bt->data);preorder(bt->lchild);preorder(bt->rchild);}}返回pre(TR);返回T>右是空返回返回返回返回pre(TR);T>左是空返回T>左是空返回TDprintf(D);pre(TL);Dpre(TR);TBprintf(B);pre(TL);BTCprintf(C);pre(TL);C主程序Pre(T)TAprintf(A);pre(TL);AT>左是空返回T>右是空返回pre(TR);先序序列：ABDC◆中序遍历递归算法：voidinorder(btree*p){if(p！=NULL){

inorder(p->left);

printf("%d",p->data);

inorder(p->right);}}作业2:

1、有一颗二叉树如下图，分别写出其先序、中序、后序遍历序列。abcdehifg2、书上，P87

33、有一颗二叉树如下图，分别写出其先序、中序、后序遍历序列。4、采用顺序存储方法和链式存储方法分别画出如下图所示二叉树的存储结构。Key1:

先序：abdehcfgi

中序：dbheafcig

后序：dhebfIgcaKey3:中序遍历序列：H，D，I，B，E，A，F，C，G先序遍历序列：A，B，D，H，I，E，C，F，G后序遍历序列：H，I，D，E，B，F，G，C，AKey4:§5.4树的存储一、树的存储方式1、双亲表示法实现：定义一组连续的结构数组存放树的结点，每个结点含两个域：数据域：存放结点本身信息双亲域：指示本结点的双亲结点在数组中的位置typedefstructnode{datatypedata;

intparent;}JD;JDt[M];◆结点定义如下：特点：找双亲容易，找孩子难abcdefhgiacdefghib012235551096012345789dataparent0号单元不用或存结点个数如何找孩子结点例：2、孩子表示法多重链表：每个结点有多个指针域，分别指向其子树的根定长结点的多重链表：取树的度D作为每个结点的指针域个数，即结点的指针个数相等；不定长结点的多重链表：树中每个结点都取它自己的度d作为指针域的个数，而终端结点不设指针域。datachild1child2……….childDdatadegreechild1child2……….childd孩子结点：typedefstructnode{intchild;/*该结点在表头数组中下标*/

structnode*next;/*指向下一孩子结点*/

}JD;表头结点：typedefstructtnode

{datatypedata;/*数据域*/

structnode*fc;/*指向第一个孩子结点*/}TD;TDt[M];/*t[0]不用*/●孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表.例1:见P76abcdefhgi6012345789acdefghibdatafc23^45^978^6^如何找双亲结点例2：

3、带双亲的孩子表示法abcdefhgi612345789acdefghibdatafc23459786^^^^^^^^^012235551parent4、孩子兄弟表示法实现：用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点特点操作容易破坏了树的层次typedefstructnode{datatypedata;

structnode*fch,*nsib;}JD;abcdefhgi例：

a^b

c^^d

e^

f^^g

h

i^二、普通树与二叉树的转换

普通树可用链式存储结构来表示，每个结点包括数据域以及指向它各个儿子结点的指针域。若同一树的各结点有相同数据结构，则只能按结点度数最大值（该树的度数）给每个结点设置指针。这样较浪费存储空间。按照一定的原则将普通树用二叉树来表示，是较好的表示方法。

将所有兄弟结点之间加一连线；对每个结点，保留与其左儿子结点的连线，去掉该结点与其它儿子结点的连线；将树向顺时针方向旋转45°

把普通树转换成相应的二叉树，具体方法如下：例1：把普通树转换成相应的二叉树书上P77

图5.18例2：树经过变换，可得下面的形式：得到的已是一棵二叉树，若按顺时针方向将它旋转就更清楚地变为下面所示的二叉树。由于树根没有兄弟，所以树转换为二叉树后，二叉树的根结点的右子树必为空。Exercise:

把普通树转换成相应的二叉树1、2、abcdabcedf§5.5树的应用一、二叉排序树1、二叉排序树的定义所谓排序，就是将一组杂乱无序的数据按一定的规律顺序排列起来。对一个二叉树若规定：任一结点如果有左子树，其左子树各结点的数据必须小于该结点的数据；任一结点如果有右子树，其右子树各结点的数据必须等于或大于该结点的数据，按这样规定构成的二叉树叫做二叉排序树。在一个二叉排序树中，其结点是按左子树、根和右子树的次序有序的，故对二叉排序树进行中序遍历得到的结点序列是一个有序序列。以整数类型的数据排列为例，设要求将一批正整数按递增的次序排列，若有相同的数据，则按先后次序列出。按二叉排序树要求可将这批正整数构成一个二叉排序树，每个参加排序的数据对应二叉树的一个结点，然后，对这种树进行一次中序遍历，按访问各结点的顺序输出所有结点的数据，这些数据就是按排序所要求的次序排列的。中序遍历序列：1，2，3，4，5，6，7，8，9，10，112、二叉排序树的生成设已知一组待排序的数据，若要构造出对应的二叉排序树，一般是采取从空树开始，陆续插入一系列结点的办法，逐步生成对应的二叉排序树。即首先以第一个数据构成根结点，以后对应每个数据插入一个结点，在插入过程中，原有的结点位置均不再变动，只是将新数据结点作为一个端结点插入到合适的位置处，使树中任何结点与其左、右子树结点数据之间的关系都符合二叉排序树的要求例：待排序的数据为一组正整数：10,15,20,5,10,30,9,7下图二叉排序树生成过程假设一组待排序的数据均为正整数，并以－1为结束输入的标志，生成二叉排序树函数如下：

voidcreat(btree*b){

intx;b=NULL;do{

scanf("%d",&x);/*读入一个整数*/

insert(x,b);/*插入该结点*/}while(x!=-1);}生成二叉排序树算法:二、哈夫曼树Huffman1、哈夫曼树基本术语：

1)路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。2)路径长度：路径上的分支数称为这两点之间的路径长度。3)树的路径长度：树的路径长度是从树的根到每一结点的路径长度之和，一般记作pl。在结点数目相同的二叉树中，完全二叉树或满二叉树的路径长度最短。

4)结点的权：在许多实际应用中，常常将树中结点赋予一个有某种意义的实数，称为该结点的权。5)带权路径长度：从树的根结点到该结点之间的路径长度与该结点上权的乘积，称为该结点的带权路径长度。树的带权路径长度：是树中所有叶子结点的带权路径长度之和，通常记为：

其中n表示叶子结点个数，wi和li分别表示叶子结点ki的权值和根到ki之间的路径长度。给定一组n个实数，以它们作为各个叶子结点的权，可构成不同的有n个叶子结点的二叉树，这些二叉树的带权路径长度wpl可能不同。P832、哈夫曼树哈夫曼树又称为最优二叉树，它是这样定义的：设有n个权值{w1，w2，…，wn}，以这些权值为各个叶子结点的权所构成的二叉树中，带权路径长度WPL最小的二叉树叫做哈夫曼树。哈夫曼(Huffman)于1952年提出了得到这种树的算法，因此相应的算法称为哈夫曼算法。将n个权值{w1，w2，…，wn}按递增次序排列，设其顺序为w1，w2，…，wn，取出最小的两个w1和w2，分别作为根结点的左、右儿子结点的权组成一个二叉树，并认为其根结点的权w12=w1+w2；将w12按其数值大小插入到w3至wn之间，使数值仍保持为递增的次序；3、哈夫曼算法再取出最小的两个作为根的左、右儿子的权组成二叉树，也令根的权等于此两数值之和，并同样将此根结点按权值大小插入到剩下的数据中，保持数值的递增次序。如此重复进行下去，直到构成一个二叉树为止，即得到哈夫曼树。如下图：

哈夫曼算法过程例：给定4个数：7，5，2，4Exercise:

1、给定一组权值5个数：9，1，8，5，3构造一个哈夫曼树。4、哈夫曼编码哈夫曼编码（Haffmancoding）是一种应用广泛且非常有效的数据压缩技术，该技术一般可将数据压缩20%至90%，其压缩效率取决于被压缩数据的特征。通常我们将压