数据结构-第6章 树和二叉树.ppt

第6章 树和二叉树,学习要点,理解树的定义和基本术语，重点了解二叉树的定义、性质和存储结构。掌握二叉树遍历的递归算法及它的典型运算。理解线索化二叉树的特性以及寻找某结点的前驱和后继的方法。理解树、森林和二叉树间的相互转换规则。掌握哈夫曼树的实现方法，理解构造哈夫曼编码及带权路径长度的计算。,6.1 树的基本概念,什么是树？树是由 n(n 0)个结点的有限集合。如果 n=0，称为空树；如果 n 0，则 有且仅有一个特定的称之为根(Root)的结点，它只有直接后继，但没有直接前驱；当n 1，除根以外的其它结点划分为 m(m 0)个互不相交的有限集 T1,T2,Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。注1：过去许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。,T=A，B，C，D，E，F，G，H，I，J，K，L A是根，其余结点可以划分为3个互不相交的集合：T1=B，E，F，K，L T2=C，G T3=D，H，I，J，M 这些集合中的每一集合都本身又是一棵树，它们是A的子树。对于T1，B是根，其余结点可以划分为2个互不相交的集合：T11=E，K，L T12=F T11，T12是B的子树。,树的示例,1.树中只有根结点没有前驱；2.除根外，其余结点都有且仅一个前驱；3.树的结点，可以有零个或多个后继；4.除根外的其它结点，都存在唯一条从根到该结点的路径；5.树是一种分支结构(除了一个称为根的结点外)每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。,树的逻辑结构特点,树可表示具有分支结构关系的对象例1.家族族谱 设某家庭有13个成员A、B、C、D、E、F、G、H、I、J、K、L、M，他们之间的关系可如图所示的树表示。例2.单位行政机构的组织关系,树的应用,树是常用的数据组织形式 有些应用中数据元素之间并不存在分支结构关系，但是为了便于管理和使用数据，将它们用树的形式来组织。例3.计算机的文件系统 不论是DOS文件系统还是window文件系统，所有的文件是用树的形式来组织的。,文件夹1,文件夹2,文件1,文件2,文件夹11,文件夹11,文件11,文件12,C,树的应用,树的结点：包含一个数据元素的内容及若干指向子树的分支。孩子结点：结点的子树的根称为该结点的孩子；如E是B的孩子。双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；如B是E的双亲。兄弟结点：同一双亲的孩子结点；如H、I、J互为兄弟。堂兄结点：同一层上结点；如G与E、F、H、I、J互为堂兄。祖先结点：结点的祖先是从根到该结点所经分支上的所有结点；如H的祖先为A、D。子孙结点：以某结点为根的子树中的任一结点称为该结点的子孙；如A的子孙为B、C、D、E、F、G、H、I、J、K、L、M。,6.1.3 基本术语,结点的度：结点子树的个数；如D的度为3。叶子结点：也叫终端结点，是度为0的结点；如K、L、F、G、M、I、J。分支结点：度不为0的结点；如A、B、C、D结点层次：根结点的层定义为1，根的孩子为第二层结点，依此类推。树的高度：树中结点的最大层次；如图所示树的高度为4。树的度：树中各结点的度的最大值；如图所示树的度为3。森林：m(m=0)棵互不相交的树的集合；,基本术语,1.双亲表示法：以一组连续的空间存储树的结点，通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。其类型定义如下：#define MAX_TREEE_SIZE 100typedef struct PTNode ElemType data;int parent;/双亲位置域 PTNode;typedef struct PTNode nodesMAX_TREE_SIZE;int n;/结点数 Ptree;特点：找双亲容易，找孩子难,6.2 树的存储结构,通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。多重链表：每个结点有多个指针域，分别指向其子树的根。结点同构：结点的指针个数相等，为树的度d。结点不同构：结点指针个数不等，为该结点的度d。,6.2.2 孩子表示法,孩子链表：其主体是一个与结点个数一样大小的一维数组，数组的每一个元素有两个域组成，一个域用来存放结点信息，另一个用来存放指针，该指针指向由该结点孩子组成的单链表的首位置。单链表的结构也由两个域组成，一个存放孩子结点在一维数组中的序号，另一个是指针域，指向下一个孩子。每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表。,孩子表示法,0123456789,数组下标,特点：找孩子容易，找双亲难,孩子链表表示法图示,typedef struct CTNode/孩子结点 int child;struct CTNode*next;*ChildPtr;typedef struct ElemType data;ChildPtr firstchild;/孩子链表头指针 CTBox;typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;/结点数和根的位置CTree;,孩子链表表示法类型定义,用二叉链表作树的存储结构，链表中每个结点的两个指针域分别指向其第一个孩子结点和下一个兄弟结点。特点：操作容易，但破坏了树的层次。孩子兄弟表示法类型定义：typedef struct CSNode ElemType data;struct CSNode*firstchild,*nextsibling;CSNode,*CSTree;,6.2.4 孩子兄弟表示法,利用树的孩子兄弟链表这种存储结构便于实现各种树的操作。例如找某结点的第i个孩子，则只要先从左指针域中找到第1个孩子结点上，然后沿着孩子结点的next域连续走i-1步便可找到第i个孩子。如增加一个parent域，则也能方便实现求双亲的操作。,孩子兄弟表示法,6.3.1 二叉树的基本概念 或为空树，或由根及至多两棵互不相交的左子树、右子树构成(即不存在度大于2的结点)，并且左、右子树本身也是二叉树。说明：1.二叉树中每个结点最多有两棵子树，二叉树每个结点度小于等于2；2.左、右子树不能颠倒有序树；3.二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念。,6.3 二叉树,(a)(b)(c)(d)(e)(a)空树(b)只含根结点(c)右子树为空树(d)左右子树均不为空树(e)左子树为空树,L,L,R,R,二叉树的形态,非完全二叉树,完全二叉树,满二叉树,两种特殊的二叉树,满二叉树：深度为k的二叉树，有2k-1个结点则称为满二叉树；完全二叉树：如果深度为k、由n个结点的二叉树中个结点能够与深度为k的顺序编号的满二叉树从1到n标号的结点相对应，则称为完全二叉树。完全二叉树的特点是：1.所有的叶结点都出现在第k层或k1层。2.对任一结点，如果其右子树的最大层次为l，则其左子树的最大层次为 l 或 l 1。,两种特殊的二叉树,性质1 在二叉树的第 i 层上至多有 2i-1个结点。(i 1)证明用归纳法证明：当i=1时，只有根结点，2 i-1=2 0=1。假设对所有j，1ji，命题成立，即第j层上至多有2 j-1 个结点。由归纳假设第i-1 层上至多有 2i-2个结点。由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即22i-2=2 i-1。,6.3.2 二叉树的性质,性质2 深度为 k 的二叉树至多有 2 k-1个结点(k 1)。证明：由性质1可见，深度为k的二叉树的最大结点数为,20+21+2 k-1=2 k-1,二叉树的性质,性质3 对任何一棵二叉树T，如果其叶结点数为 n0，度为2的结点数为 n2，则n0n21。证明：设二叉树中度为1的结点数为n1，二叉树中总结点数为：nn0n1n2 二叉树中的分支数，除根结点外，其余结点都有一个进入分支，设B为二叉树中的分支总数，则有：nB1。由于这些分支都是由度为1和2的结点射出的，所以有：Bn1+2 n2;nB1n12n21得到：n0n21,二叉树的性质,性质 4：具有 n 个结点的完全二叉树的深度为 log2n+1。证明：设完全二叉树的深度为 k，则根据性质2和完全二叉树的定义有2k-1-1 n 2k-1或 2k-1 n 2k取对数 k-1 log2n k，又k是整数，因此有 h=log2n 1,二叉树的性质,性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号(从第1层到第 log2n+1层，每层从左到右)，则对任一结点i(1 i n)，有：1.如果i1，则结点i无双亲，是二叉树的根；如果i1，则其双亲是结点 i/2。2.如果2in，则结点i为叶子结点，无左孩子；否则，其左孩子是结点2i。3.如果2i1n，则结点i无右孩子；否则，其右孩子是结点2i1。,二叉树的性质,顺序存储结构 它是用一组连续的存储单元存储二叉树的数据元素。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法：#define MAX-TREE-SIZE 100 typedef TElemType SqBiTreeMAX-TREE-SIZE;,6.3.3 二叉树的存储结构,通常是按照二叉树结点从上至下、从左到右的顺序存储，但这样结点在存储位置上的前驱后继关系并不一定就是它们在逻辑上的邻接关系，只有通过一些方法确定某结点在逻辑上的前驱结点和后继结点，这种存储才有意义。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。,顺序存储结构,例如：bt3的双亲为3/2=1，即在bt1中；其左孩子在bt2i=bt6中；其右孩子在bt2i+1=bt7中。,完全二叉树的顺序表示,一般二叉树也按完全二叉树形式存储，只有增添一些并不存在的空结点(用表示，表示该处没有元素存在，仅仅为了好理解)，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。,例如对于B结点而言：bt2的双亲为1/2=1，即在bt1中(为A)；其左孩子在bt2i=bt4中(为D)；其右孩子在bt2i+1=bt5中(为)。,一般二叉树的顺序表示,这种存储结构适合于完全二叉树，既不浪费存储空间，又能很快确定结点的存放位置、以及结点的双亲和左右孩子的存放位置，但对一般二叉树，可能造成存储空间的浪费。例如，深度为k，且只有k个结点的右单枝树(每个非叶结点只有右孩子)，也需2k-1个单元，即有(2k-1)-k个单元被浪费。,顺序存储的优缺点,所谓链式存储是指，用链表来表示一棵二叉树，即用链来指示着元素的逻辑关系。通常采用二叉链表来存储。链表中每个结点由三个域组成，除了数据域外，还有两个指针域，分别用来给出该结点左右孩子所在的结点的存储地址。其定义如下：typedef struct BiTNode ElemType data;struct BiTNode*lchild,*rchild;BiTNode,*BiTree;,链式存储结构,B,T,lchild,data,rchild,结点结构,二叉链表,A,B,D,G,三叉链表图示,三叉链表,6.4 二叉树的遍历和线索,6.4.1 二叉树的遍历定义：所谓遍历二叉树，就是遵从某种次序，访问二叉树中的所有结点，使得每个结点仅被访问一次。这里所提的“访问”的含义很广，可以是查询、修改、输出某元素的值，以及对元素作某种运算等等。但要求这种访问不破坏它原来的数据结构。遍历一个线性结构很简单，只须从开始结点出发，顺序扫描每个结点即可。但对二叉树这样的非线性结构，每个结点可能有两个后继结点，因此需要寻找一种规律来系统访问树中的各结点。,由二叉树的定义是递归的，它是由三个基本单元组成，即根结点、左子树和右子树。因此，遍历一棵非空二叉树的问题可以分解为三个子问题：访问根结点、遍历左子树、遍历右子树，只要依次遍历这三部分，就可以遍历整个二叉树。由于实际问题一般都是要求左子树较右子树先遍历，分别称为先序遍历、中序遍历和后序遍历。令L，R，D分别代表二叉树的左子树、右子树、根结点，则有DLR、LDR、LRD三种遍历规则。,递归实现方法,若二叉树非空，则：1.访问根结点 2.先序遍历左子树 3.先序遍历右子树,D L R,得到的序列为：A B D C,先序遍历二叉树,Status PreOrderTraverse(BiTree T)/采用二叉链表存贮二叉树 if(T)/若二叉树不为空 Visit(T-data)；/访问根结点 PreOrderTraverse(T-lchild);/先序遍历T的左子树 PreOrderTraverse(T-rchild);/先序遍历T的右子树/PreOrderTraverse,先序遍历二叉树算法实现,若二叉树非空，则：1.中序遍历左子树 2.访问根结点 3.中序遍历右子树,L D R,得到的序列为：B D A C,中序遍历二叉树,若二叉树非空，则：1.后序遍历左子树 2.访问根结点 3.后序遍历右子树,L R D,得到的序列为：D B C A,后序遍历二叉树,void leaf(BiTree T)/采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点个数，本算法在先序遍历二叉树的过程中，统计叶子结点的个数，初始化n=0if(T)if(T-lchild=NULL/if/leaf,例 编写求二叉树的叶子结点个数的算法,输入：二叉树的先序序列结果：二叉树的二叉链表问题：遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入在空子树处添加字符的二叉树的按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点链接。,在空子树处添加的二叉树的先序序列：A B D F E C,例 建立二叉链表,Status CreateBiTree(BiTree/CreateBiTree,例 建立二叉链表,遍历是二叉树最基本最常用的操作。1.对二叉树所有结点做某种处理可在遍历过程中实现；2.查找二叉树某个结点，可通过遍历实现；与线性表相比，对二叉树的遍历存在如下问题：1.遍历算法要复杂的多，费时的多；2.为查找二叉树中某结点在某种遍历下的后继，必须从根开始遍历，直到找到该结点及后继；如果能将二叉树线性化，就可以减化遍历算法，提高遍历速度。,6.4.2 线索二叉树,定义：当以二叉链表作为存储结构时，只能找到结点的左右孩子的信息，而不能直接得到结点的任一序列的前驱与后继信息，这种信息只有在遍历的动态过程中才能得到，为了能保存所需的信息，可增加标志域。0 lchild 域指示结点的左孩子 1 lchild 域指示结点的前驱 0 rchild 域指示结点的右孩子 1 rchild 域指示结点的后继 以这种结构构成的二叉链表作为二叉树的存储结构，叫做线索链表，其中指向结点前驱与后继的指针叫做线索。加上线索的二叉树称之为线索二叉树。,线索二叉树定义,利用现有的空指针域，每个n个结点的二叉链表，有n+1个空指针域，故可利用这些的空指针域存放结点的前趋和后继指针。(n个结点共有2n个链域，而每个结点(除根结点外)都有一个分支指向，则共有n-1个分支，其中每个分支占有一个链域，所以空链域为2n-(n-1)=n+1。)若结点有左子树，则左指针lchild指示其左孩子(LTag=0)；否则，令左指针指示其前驱(LTag=1)；若结点有右子树，则右指针rchild指示其右孩子(RTag=0)；否则，令右指针指示其后继(RTag=1)。,如何保存遍历过程中得到的信息？,typedef enum PointerTeg Link,Thread;/Link=0:指针，Thread=1:线索typedef struct BiThrNod TElemType data;struct BiThrNode*lchild,*rchild;/左右指针 PointerTeg LTag,RTag;/左右标志 BiThrNode,*BiThrTree;,线索链表的类型描述,(以中序遍历为例)查找任意结点的前驱结点 如果该结点的左标志为1，那么其左指针域所指向的结点便是它的前驱结点；如果该结点的左标志为0，表明该结点有左孩子，根据中序遍历的定义，它的前驱结点是以该结点的左孩子为根结点的子树的最右结点，即沿着其左子树的右指针链向下查找，当某结点的右标志为1时，它就是所要找的前驱结点。,中序线索二叉树中序：DBGJEACHLKFI,如何找结点的前驱和后继,中序线索二叉树中序：DBGJEACHLKFI,如何找结点的前驱和后继,(以中序遍历为例)查找任意结点的后继结点 对任意结点p，若右标志为1，则rchild指向该结点的后继；若右标志为0，则rchild指向该结点的右孩子，此时，应从右孩子开始，沿左指针前进，直到找到没有左孩子的结点s(Ltag=1)，则s就是p的后继，即后继是中序遍历右子树时，访问的第一个结点。,按不同的方式遍历二叉树所得到的线索二叉树是不相同的。,遍历线索二叉树,遍历线索二叉树,带头结点的线索二叉树 在存储线索二叉树时往往增设一头结点，其数据域不存放信息，其左指针域指向二叉树的根结点，右指针域指向某种遍历时访问的最后一个结点。而原二叉树在某序遍历下的第一个结点的前驱线索和最后一个结点的后继线索都指向该头结点。,找遍历的第一个结点 左子树上处于“最左下”(没有左子树)的结点。不断地找遍历到的结点的后继结点，直到树中各结点都遍历到为止，结束 若无右子树，则为后继线索所指结点；否则为对其右子树进行中序遍历时访问的第一个结点。,遍历线索二叉树步骤,void InOrderTraverse_Thr(BiThrTree T)p=T-lchild;while(p!=T)while(p-LTag=0)p=p-lchild;Visit(p-data);while(p-RTag=1/InOrderTraverse_Thr,中序线索二叉树中序：DBGJEACHLKFI,中序遍历线索二叉树算法实现,6.5.1 树转变为二叉树 加线：在兄弟之间加一连线；抹线：对每个结点，除了其左孩子外，去除其与其余孩子之间的关系；旋转：以树的根结点为轴心，将整树顺时针转45。,6.5 树、森林与二叉树,由上面的转换可以看出，在二叉树中，左分支上的各结点在原来的树中是父子关系，而右分支上的各结点在原来的树中是兄弟关系。由于树的根结点没有兄弟，所以变换后的二叉树的根结点的右孩子必为空。,树转变为二叉树实现过程,由森林的概念可知，森林是若干棵树的集合，只要将森林中各棵树的根视为兄弟，每棵树又可以用二叉树表示，这样，森林也同样可以用二叉树表示。具体的方法如下：将各棵树分别转换成二叉树；将每棵树的根结点用线相连；以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构。,6.5.2 森林转换成二叉树,森林转变为二叉树实现过程,加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩 子的右孩子，沿分支找到的所有右孩子，都与p 的双亲用线连起来；抹线：抹掉原二叉树中双亲与右孩子之间的连线；调整：将结点按层次排列，形成树结构。,注：该二叉树的右子树为空,6.5.3 二叉树转换成树和森林,抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树。还原：将孤立的二叉树还原成树。,注：该二叉树的右子树一定不为空,二叉树转换成森林,在树和森林中，一个结点可能有两棵以上的子树，所以不宜讨论它们的中序遍历，即树和森林只有先序遍历和后序遍历。1.树的先序遍历若树非空，则先访问根结点，然后依次先序遍历各子树。,2.树的后序遍历若树非空，则依次后序遍历各子树，最后访问根结点。,6.5.4 树和森林的遍历,3.森林的先序遍历若森林非空，则先访问森林中第一棵树的根结点，再先序遍历第一棵树各子树，接着先序遍历第二棵树、第三棵树、直到最后一棵树。遍历结果：ABCDEFGHIJ,4.森林的后序遍历按顺序后序遍历森林中的每一棵树。遍历结果：BCDAFEHJIG,树和森林的遍历,一、基本概念 路径和路径长度：在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。通路中分支的数目称为路径长度。若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。结点的权及带权路径长度：若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。从根结点到该结点之间的路径长度与该结点的权的乘积称为结点的带权路径长度。,6.6 哈夫曼树,树的带权路径长度：树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为其中n 为叶子结点数目，wi为第i 个叶子结点的权值，li 为第i 个叶子结点的路径长度。哈夫曼树：在一棵二叉树中，若树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。,哈夫曼树的基本概念,例 有4个结点，权值分别为7，5，2，4，构造有4个叶子结点的二叉树。,WPL=7*2+5*2+2*2+4*2=36,WPL=7*3+5*3+2*1+4*2=46,WPL=7*1+5*2+2*3+4*3=35,例 编制一个将百分制转成五级分制的程序。,哈夫曼树的应用,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,N,N,N,N,Y,Y,Y,Y,WPL=0.10*1+0.15*2+0.25*3+0.35*4+0.15*4=3.15,流程图1：,0.10,0.15,0.25,0.35,0.15,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,N,N,N,N,Y,Y,Y,Y,WPL=0.10*3+0.15*3+0.25*2+0.35*2+0.15*2=2.25,流程图2：,步骤如下：1.由给定的 n 个权值w1,w2,wn构成n棵二叉树的集合(即森林)F=T1,T2,Tn，其中每棵二叉树 Ti 中只有一个带权为 wi 的根结点，其左右子树均空。2.在F 中选取两棵根结点的权值最小的树做为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。3.在F 中删去这两棵树，同时将新得到的二叉树加入 F中。4.重复2和3，直到 F 只含一棵树为止。这棵树便是哈夫曼树。,6.6.2 Huffman树的构造方法,例 w=5,29,7,8,14,23,3,11,例 w=5,29,7,8,14,23,3,11,通信中，可以采用0、1的不同排列来表示不同的字符，称为二进制编码。若每个字符出现的频率不同，可以采用不等长的二进编码，频率较大的采用位数较少的编码，频率较小的字符采用位数较多的编码，这样可以使字符的整体编码长度最小，这就是最小冗余编码的问题。而赫夫曼编码就是一种不等长的二进制编码，且赫夫曼树是一种最优二叉树，它的编码也是一种最优编码。,6.6.3 赫夫曼树编码,设需要编码的字符集合为D=d1，d2，dn，它们在电文中出现的次数或频率集合为w1，w2，wn，以d1，d2，dn作为叶结点，w1，w2，wn作为它们的权值，构造一棵赫夫曼树，规定赫夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为赫夫曼编码。,编码方法,例 要传输的字符集 D=C，A，S，T，;，字符出现频率 w=2，4，2，3，3。,每个字符的编码分别为：C：110A：10S：111T：00;：01,如果设计出的A、B、C、D的编码分别是0、00、1和01，假设有一电文为000011010，它译出的电文是怎样的？,在建立不等长编码时，必须使任何一个字符的编码都不是另一个字符编码的前缀，这样才能保证译码的唯一性。在赫夫曼树中，每个字符结点都是叶结点，它们不可能在根结点到其它字符结点的路径上，所以一个字符的赫夫曼编码不可能是另一个字符的赫夫曼编码的前缀，从而保证了译码的非二义性。,存在问题,从Huffman树根开始，从待译码电文中逐位取码。若编码是“0”，则向左走；若编码是“1”，则向右走，一旦到达叶子结点，则译出一个字符；再重新从根出发，直到整个电文结束。,例：电文为“110100001”译文只能是：,CAT；,译码方法,