【大学数据结构课件】树和二叉树.ppt

《【大学数据结构课件】树和二叉树.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、内容提要6.1树的定义及基本术语6.2二叉树6.3编历二叉树6.4线索二叉树6.5二叉排序树6.6平衡二叉树6.7树和森林6.8哈夫曼树及应用16.1树的定义及基本术语1、树的定义(1)树的一般定义树是包含n个结点的有限集合，在这个集合上定义了一个唯一的关系，这个关系满足下面的条件：I.存在唯一的一个结点，它没有前驱，称为根II.除了根结点外，其它结点有且仅有一个前驱III.除了根结点外，任何结点ai(0im)，都存在唯一的一个从根到ai的结点序列a0,a1,a2,..,am，其中，a0是根。这个序列称为从根到ai的路

2、径。a0a1a2a3a4a52树的定义及基本术语(cont’d)(2)树的递归定义树是包含n个结点的有限集，在这个集合上定义了唯一的关系，它满足下面的条件：I.有个特定的称为根的结点；II.当n>1时，除了根以外的其余结点根据它们之间的关系可分为m个不相交的有限集T1,T2,..,Tm，其中，每个有限集都是一棵树。这些树称为根的子树。abcdefT1={b,e,f};T2={c};T3={d}3树的定义及基本术语(cont’d)(3)树的基本术语1.根,唯一没有前驱的结点2.度,结点的度是结点的子树数目,树的度是指结点度的

3、最大值3.叶子，度为0的结点，也称终端结点4.分枝结点，叶子之外的结点，也称非终端结点。除了根以外的分枝结点又称内部结点。5.双亲、子女、祖先、子孙，结点子树的根称为结点的子女，该结点就是它子女的双亲；某结点的祖先是指从根到该结点的路径上的全部结点；结点的子树中全部结点都是该结点的子孙。abcdef4树的定义及基本术语(cont’d)(3)树的基本术语6.兄弟、堂兄弟，同一个结点的子女互为兄弟，双亲为兄弟的结点互称堂兄弟。7.结点的层次、树的深度(高度)，根为第1层，结点的层次是其双亲层次加1。树的深度是指结点的最大层数。

4、8.有序树、无序树，如果结点的各子树自左向右是有次序的，则称有序树，否则称无序树9.森林，m棵互不相交的树就构成了森林。abcdefg第1层第2层第3层56.2二叉树1.二叉树的概念每个结点最多有2棵子树，并且子树有左右之分，不能任意颠倒。二叉树有5种形态：①空树②只有一个根③只有左子树④只有右子树⑤有两个子树2.二叉树的性质①在二叉树的第i层上至多有2i－1个结点(i>=1)②深度为k的二叉树至多有2k-1个结点。1234567896二叉树(cont’d)2.二叉树的性质③设二叉树中，叶结点数为n0,度为1的结点数为n1

5、,度为2的结点数为n2,则有：n0=n2+1因为N=n0+n1+n2=1+n1*1+n2*2④具有n个结点的完全二叉树的深度为log2n+1log2n表示log2n取整满二叉树：具有最多结点数的二叉树（即一棵深度为k且有2k-1个结点的二叉树）完全二叉树：将满二叉树从右向左删除叶子的结果，因此,结点数n<=2k-1，并且n>2k-1-11234567897二叉树(cont’d)2.二叉树的性质⑤对于具有n个结点的完全二叉树,将结点按照从上到下从左到右进行编号，则有如下特点：I.i=1则是根，若i>1则它的双亲为i/

6、2II.如果2i>n则i没有左子女，否则它的左子女是2iIII.如果2i+1>n则i没有右子女，否则它的右子女是2i＋1i/2ii+12i2i+12i+22i+38二叉树(cont’d)3.二叉树的存储结构(1)顺序存储，利用数组按照完全二叉树的方式对结点编号，根据编号将结点存放在数组中相应的位置中。#defineN50//二叉树的最大结点数typedefelemtypeSQTREE[N];//顺序存储的二叉树SQTREEbt;ABCEF123456ABCEF01234567899二叉树(cont’d)3.二叉树的存储

7、结构(2)链式存储，利用二叉链表或三叉链表typedefstructtreenode{elemtypedata;//结点数据//指向左右孩子的指针structtreenode*lchild,*rchild/*,*parent*/;}TREENODE,*TREENODEPTR,*BTREEAB^C^E^^F^^DATAPARENTLCHILDRCHILDlchilddatarchildlcjilddataparentrchild10＃defineN50//定义二叉树最大结点数voidcreatetree(BTREE*root

8、){intvalue,front,rear;TREENODEPTRt,q[N];//q是队列，front,rear是队头队尾下标。scanf("%d",&value);//开始创建根结点if(value==0){*root=NULL;return;};//输入0，表示空结点*root=(TREENODE