数据结构-树与二叉树.

本章主要内容：1．二叉树的定义、性质和存储结构。2．二叉树的遍历和线索化以及遍历算法的各种描述形式。3．树和森林的定义、存储结构与二叉树的转换、遍历。4．树的应用。本章学习重点：1．掌握二叉树的存储结构及其各种操作。2．掌握树和森林与二叉树的转换关系。第六章树和二叉树第六章树和二叉树6.1树的定义和基本术语6.2二叉树6.3遍历二叉树和线索二叉树6.4树和森林6.5赫夫曼树及其应用第六章树和二叉树树型结构是结点之间有分支、层次关系的结构，用它们能很好地描述有分支和层次特性的数据集合。它类似于自然界中的树。树型结构是一种非常重要的非线性结构。树型结构在现实世界中广泛存在，如各种社会组织机构的组织关系图就可用树型结构来表示。在计算机领域中有着广泛应用，在许多算法中，常用树型结构描述问题的求解过程或表示求解的对策等。6.1树的定义和基本术语一、树的定义二、树的表示方法三、基本术语四、抽象数据类型树的定义一、树的定义6.1树的定义和基本术语1．定义树(Tree)是n(n≥0)个结点的有穷集合T。且在T中：(1)有且仅有一个称为根的结点T0，T0没有前驱；(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，…，Tm，其中每一个Ti(1≤i≤m)本身都是一棵树。称树T1，T2，…，Tm为T0的子树。(3)n=0，T是一棵空树。一、树的定义图1树的一般形式返回6.1树的定义和基本术语一、树的定义2.特点(1)树的定义是一个递归定义。由图看出，A是由三个子树构成的，这三棵子树又分别以B，C，D为根，在以B为根的子树中，又由两棵子树构成，根分别为E，F；C，D以此类推。(2)树的根结点没有前驱结点，其他结点有且仅有一个前驱结点；(3)树中的任何一个结点，可以有零个或多个后继结点。6.1树的定义和基本术语3.树型结构的例子(1)家族的血缘关系一、树的定义6.1树的定义和基本术语(2)计算机磁盘目录一、树的定义6.1树的定义和基本术语1．图形表示法：以图1中的树为例。二、树的表示方法6.1树的定义和基本术语2.形式化表示对于一个T的形式化表示为：T=(D，R)D为T中结点的集合；R为T中结点之间关系的集合。以上图为例。D={A,B,C,D,E,F,G,H,I,J,K,L,M}R={A,B,A,C,A,D,B,E,B,F,C,G,D,H,D,I,D,J,E,K,E,L,H,M}二、树的表示方法6.1树的定义和基本术语1．结点：包含一个数据元素及若干指向其子树的分支。图1所示的树有13个结点。2．结点的度(degree)：结点拥有的子树数。A结点的度为3。3．叶子或终端结点(leaf)：度为0的结点。K,L,F,G,M,I,J皆为叶子。4．分支结点或非终端结点：度不为0的结点。5．树的度：树内各结点的度的最大值。图1所示的树的度为3。6．双亲结点(parent)：结点的前驱结点。A是B,C,D的双亲。三、基本术语见图16.1树的定义和基本术语三、基本术语7.孩子结点(child)：结点的后继结点。B，C，D是A的孩子。8.兄弟结点(sibling)：同一双亲的孩子。B，C，D是兄弟。9.祖先：从根到某结点所经分支上的所有结点，皆为该结点的祖先。G的祖先是A，C；K的祖先是A，B，E。10.子孙：以某结点为根的子树中的任一结点都为该结点的子孙。E，F，K，L皆为B的子孙。11．结点的层次(level)：从根开始定义起，根为第1层，根的孩子为第2层。若某结点在第L层，则其子树的层在L+1层。12．堂兄弟：其双亲在同一层的结点互为堂兄弟。G，与E，F，H，I，J互为堂兄弟。见图16.1树的定义和基本术语13．树的深度(depth)或高度：树中结点的最大层次。上图所示树的深度为4。14．有序树和无序树：树中结点的各子树从左至右排列，不可对换，称这种树为有序树，且把各子树分别称为第一子树，第二子树，最左边的子树为第一孩子，最右边子树为最后一个孩子。否则称为无序树。15．森林(forest)：是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。如图，若删除A，就得到三棵子树构成的森林。三、基本术语6.1树的定义和基本术语可以用森林和树相互递归的定义来描述树。树的逻辑结构采用二元组形式：T=(root,F)root:根结点，数据元素F:m棵数的森林，F=（T1，T2，…，Tm）Ti=（ri，Fi）是第i棵子树树根和子树之间的关系：RF={root,ri|i=1,2,…,m,m0}三、基本术语6.1树的定义和基本术语6.2二叉树一、二叉树的定义二、二叉树的性质三、二叉树的存储结构一、二叉树的定义6.2二叉树1．定义二叉树(BinaryTree)是n(n≥0)个结点的集合，这个集合可以是空集，或者是由一个根结点和两棵称为左子树和右子树的互不相交的二叉树组成。（由此看出二叉树定义是递归的）2．特点(1)每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点）；(2)可以是空树，即不含任何结点；(3)二叉树是有序树，子树有左右之分，次序不能任意颠倒；允许某些结点只有右子树，或者只有左子树。1．抽象数据类型二叉树的定义ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系R：若D=Φ，则R=Φ，称BinaryTree为空二叉树；若DΦ，则R={H}，H是如下二元关系集：(1)在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2)若D-{root}Φ，则存在D-{root}={Dl，Dr}，且Dl∩Dr=Φ；一、二叉树的定义6.2二叉树(3)若DlΦ，则Dl中存在唯一的元素xl,root,xlH，且存在Dl上的关系H1H；若DrΦ，则Dr中存在唯一的元素xr,root,xrH,且存在Dr上的关系HrH；H={root,xl，root,xr,Hl,Hr}；(4)(Dl，{Hl})是一棵符合本定义的二叉树，称为根的左子树，(Dr，{Hr})是一棵符合本定义的二叉树，称为根的右子树。基本操作P：略。}ADTBinaryTree一、二叉树的定义6.2二叉树4.二叉树的五种基本形态一、二叉树的定义6.2二叉树5.特殊的二叉树(1)满二叉树如果二叉树的叶子结点都在同一层，且其它各层的结点都包含左、右子树，则称该二叉树为满二叉树。对二叉树从第1层的根结点开始连续编号，编号顺序是自上而下、自左而右，则该编号方法给出了满二叉树的顺序表示法。一、二叉树的定义6.2二叉树(2)完全二叉树如果一棵深度为k的有i(1≤i≤n)个结点的二叉树，对树中的结点自上而下、自左而右连续编号，若编号为i的结点与满二叉树中编号为i的结点的位置相同，则称此二叉树为完全二叉树。特点：a.叶子结点只可能在层数最大的两层上出现；b.对任一结点，若其右分支下的子孙的最大层次为L，则其左分支下的子孙的最大层次为L或L+1。完全二叉树非完全二叉树一、二叉树的定义6.2二叉树性质1在二叉树的第i(i≥1)层上至多有2i-1个结点。用数学归纳法就可以证明。满二叉树的第i层上共有2i-1个结点。深度为k的完全二叉树，除了第k层外，其余各层也均有2i-1个结点(1≤Ik)。性质2深度为k的二叉树最多有2k-1个结点。证明：最多结点数为各层结点个数相加，即1+2+4+…+2k-1=2k-1二、二叉树的性质6.2二叉树性质3对任意二叉树T，如果其终端结点数为n0(度数为0的结点数),n1,n2分别表示度数为1,2的结点个数，则n0=n2+1。证明：设n为二叉树T的结点总数，则有：n=n0+n1+n2设除根结点外的结点数为B，则B=n-1。又B=n1+2*n2所以，n-1=n1+2*n2n0+n1+n2=n1+2*n2+1求得：n0=n2+1性质4具有n个结点的完全二叉树的深度为log2n+1。设所求深度为K.∵2k-1-1＜n≤2k-1即2k-1≤n＜2k∴k-1≤log2n＜k因为K为整数∴k=log2n+1不大于log2n的最大整数6.2二叉树二、二叉树的性质性质5对于一个具有n个结点的完全二叉树，其结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1≤i≤n)，有(1)若i=1，则结点i是二叉树的根，无双亲；若i1，则其双亲结点parent(i)是结点i/2。(2)若2in，则结点i无左子树；若2i≤n，则其左子树lchild(i)是结点2i。(3)若2i+1n，则结点i无右子树；若2i+1≤n，则其右子树rchild(i)是结点2i+1。6.2二叉树二、二叉树的性质1．顺序存储结构略。2.链式存储结构所谓二叉树的链式存储，是指二叉树诸结点被随机存放在内存空间中，结点之间的关系用指针说明。设计不同的结点结构可构成不同形式的链式存储结构。三、二叉树的存储结构6.2二叉树(1)二叉链表一个结点包含三个域：数据域、左、右指针域分别指向左子树和右子树。(2)三叉链表为了便于找到双亲结点，在二叉链表的基础上，增加一个指向双亲结点的指针域，构成三叉链表。lchilddatarchildlchilddataparentrchild三、二叉树的存储结构6.2二叉树(3)线索链表在含有n个结点的二叉链表中有n+1个空链域。如图所示。利用这些空链域存储其他有用信息，即可得到另一种链式存储结构——线索链表。三、二叉树的存储结构6.2二叉树3.二叉树的二叉链表存储表示：typedefstruct{TelemTypedata;StructBiTNode*lchild,*rchild;}BiTNode,*BiTree;三、二叉树的存储结构6.2二叉树6.3遍历二叉树和线索二叉树一、遍历二叉树二、线索二叉树(穿线树)所谓遍历就是按某指定规则访问数据结构中的所有结点，且每个结点只访问一次。各种数据结构包括线性表也有遍历运算。这里“访问”的含义很广，可以对结点作各种处理，如输出结点信息、求结点个数等。对于线性结构，遍历的运算比较简单。而对二叉树这种非线性结构，每个结点都可能有两棵子树，需要寻找一种规律，以便使二叉树上的结点能排列在一个线性队列上，从而便于遍历。一、遍历二叉树6.3遍历二叉树和线索二叉树1．遍历规则二叉树是由三个基本单元组成：根结点、左子树和右子树。所谓遍历规则是指在遍历时是先访问根结点还是先访问子树，是先访问左子树还是先访问右子树。不同的遍历规则会产生不同的遍历结果。以D、L、R表示访问根结点、左子树、右子树,有6种遍历方式：DLR、LDR、LRD、DRL、RDL、RLD一般规定，在二叉树遍历中，按先访问左子树，后访问右子树的顺序进行遍历。一、遍历二叉树6.3遍历二叉树和线索二叉树有四种遍历：先(根)序遍历(DLR)124895101136127中(根)序遍历(LDR)849210511112637后(根)序遍历(LRD)894101152126731层次遍历：先从上到下，再从左到右的顺序遍历123456789101112一、遍历二叉树6.3遍历二叉树和线索二叉树2.遍历算法的基本思想由二叉树是递归定义得出遍历二叉树也要采用递归算法遍历整个二叉树。3.遍历算法(1)先(根)序遍历(前序遍历)基本思想：若二叉树非空，则按以下顺序遍历，否则结束。a.访问根结点；b.先序遍历左子树；c.先序遍历右子树。算法：voidpreorder(BiTNode*root){if(root!=NULL){visit(root-data);preorder(root-lchild);preorder(root-rchild);}}一、遍历二叉树6.3遍历二叉树和线索二叉树(2)中(根)序遍历基本思想：若二叉树非空，则按以下顺序遍历，否则结束。a.中序遍历左子树；b.访问根结点；c.中序遍历右子树。算法：voidinorder(BiTNode*root){if(root!=NULL){inorder(root-lchild);