《数据结构-C语言描述》第6章：树.ppt

第六章 树和二叉树,树的概念与定义 二 叉 树 二叉树的遍历与线索化 树和森林 哈夫曼树及其应用 树的计数,6.1树的概念与定义,树的定义：树(tree)是n(n0)个结点的有限集T，当n=0时，称为空树；当n0时，满足以下条件：（1）有且仅有一个结点被称为树根（root）结点；（2）当n1时，除根结点以外的其余n-1个结点可以划分成m(m0)个互不相交的有限集T1,T2,，Tm，其中每一个集合本身又是一棵树，称为根的子树(subtree)。,图6.1,结点(node)：表示树中的元素，包括数据项及若干指向其子树的分支。结点的度(degree)：结点拥有的子树的数目。图6.1中结点A的度为3。叶子(leaf)：度为0的结点称为叶子结点，也称为终端结点。图6.1中，叶子结点有：K，L，F，G，M，I，J。分支结点：度不为0的结点称为分支结点，也称为非终端结点。图6.1中，非终端结点有：A，B，C，D等。,孩子结点(child)：结点的子树的根称为该结点的孩子结点。图6.1中，结点A的孩子结点为B，C，D，结点B的孩子结点为E，F。双亲结点(parents)：孩子结点的上层结点称为该结点的双亲结点。图6.1中，结点I的双亲为D，结点L的双亲为E。兄弟结点(sibling)：具有同一双亲结点的孩子结点之间互称为兄弟结点。图6.1中，结点B，C，D互为兄弟，结点K，L互为兄弟。,树的度：树中最大的结点的度数即为树的度。图6.1中的树的度为3。结点的层次(level)：从根结点算起，根为第一层，它的孩子为第二层。若某结点在第l层，则其孩子结点就在第l+1层。图6.1中，结点A的层次为1，结点M的层次为4。树的高度(depth)：树中结点的最大层次数。图6.1中的树的高度为4。森林(forest)：m(m0)棵互不相交的树的集合。,有序树与无序树：树中结点的各子树从左至右是有次序的（不能互换）则称该树为有序树，否则称该树为无序树。,6.2 二叉树,二叉树的定义：二叉树是由n(n0)个结点的有限集T构成，此集合或者为空集，或者由一个根结点及两棵互不相交的左右子树组成，并且左右子树都是二叉树。注意：二叉树的子树有左右之分，因此二叉树是一种有序树。,二叉树的性质：,性质1 在二叉树的第i层上至多有2i-1个结点(i1)。性质2 深度为k的二叉树至多有2k1个结点（k=1）。性质3 对任意一棵二叉树BT，如果其叶子结点数为n0，度为2的结点数为n2，则n0n21。性质4 具有n个结点的完全二叉树的深度为【log2n】1。（符号【x】表示不大于x的最大整数。）,二叉树的性质：,性质5 对于具有n个结点的完全二叉树，如果对其结点按层次编号，则对任一结点i(1in)，有：(1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲是【i/2】(2)如果2in，则结点i无左孩子；如果2in，则其左孩子是2i(3)如果2i+1n，则结点i无右孩子；如果2i+1n，则其右孩子是2i+1,满二叉树：一棵深度为k且有2k-1个结点的二叉树称为满二叉树。完全二叉树：深度为k，有n个结点的二叉树当且仅当其每一个结点都与深度为k的满二叉树中编号从1至n的结点一一对应时，称为完全二叉树。,二叉树的存储结构,顺序存储结构:为了能够反映出结点之间的逻辑关系，必须将它“修补”成完全二叉树，对应该完全二叉树，可以开辟长度为12的数组，对12个数据元素进行存储，原二叉树中空缺的结点在数组中的相应单元必须置空,二叉树的存储结构,链式存储结构:表示二叉树的链表中的结点应该包含3个域：数据域和指向左、右子树的指针域，二叉树的这种存储结构被称为二叉链表。,在n个结点的二叉链表中，有n+1个空指针域,6.3 二叉树的遍历与线索化,二叉树的遍历：是按某条搜索路径访问树中的每一个结点，使得每一个结点均被访问一次，而且仅被访问一次。,先根遍历二叉树（1）访问根结点；（2）先根遍历左子树；（3）先根遍历右子树。,中根遍历二叉树（1）中根遍历左子树；（2）访问根结点；（3）中根遍历右子树。后根遍历二叉树（1）后根遍历左子树；（2）后根遍历右子树；（3）访问根结点。,先根遍历:-+a*bcd/ef中根遍历:a+b*cde/f后根遍历:abcd-*+ef/-,typedef struct Node datatype data;struct Node*Lchild;struct Node*Rchild;BTnode,*Btree;,先根遍历算法void preorder(Btree root)if(root!=NULL)Visit(root-data);preorder(root-Lchild);preorder(root-Rchild);,中根遍历算法void InOrder(Btree root)if(root!=NULL)InOrder(root-Lchild);Visit(root-data);InOrder(root-Rchild);,后根遍历算法void PostOrder(Btree root)if(root!=NULL)PostOrder(root-Lchild);PostOrder(root-Rchild);Visit(root-data);,线索二叉树：利用二插链表剩余的n+1个空指针域来存放遍历过程中结点的前驱和后继的指针，这种附加的指针称为“线索”，加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树。,为了区分结点的指针域是指向其孩子的指针，还是指向其前驱或后继的线索，可在二叉链表的结点中,再增设2个标志域。,0 Lchild域指示结点的左孩子Ltag=1 Lchild域指示结点的遍历前驱,0 Rchild域指示结点的右孩子Rtag=1 Rchild域指示结点的遍历后继,中序线索二叉树,基于遍历的应用与线索二叉树的应用,二叉树的遍历是对二叉树进行各种运算的一个重要基础，对访问（程序中的visit函数）结点可理解为各种对二叉树中结点进行操作。因此，只要将二叉树三种遍历算法中的visit函数具体化，就产生了基于二叉树的不同应用。,输出二叉树中的结点,Void paintnode(Btree root)if(root!=NULL)printf(root-data);paintnode(root-Lchild);paintnode(root-Rchild);,输出二叉树中的叶子结点,Void paintleaf(Btree root)if(root!=NULL)if(root-Lchild=NULL,统计叶子结点数目,Void leafcount(Btree root)if(root!=NULL)leafcount(root-Lchild);leafcount(root-Rchild);if(root-Lchild=NULL,提示：count为全局变量，在主函数中定义。,建立二叉树,图中二叉树的先根遍历序列为：ABDGCEHF，而考虑空子树后的先根遍历序列应为：ABDGCEHF，其中“”代表空子树。,如果已知二叉树的考虑了空子树后的遍历序列，那么建立这棵二叉树的算法如下(假定datatype类型为char)：Void CreateBtree(Btree*bt)char ch;ch=getchar();if(ch=.)*bt=NULL;else*bt=(Btree)malloc(sizeof(BTnode);(*bt)-data=ch;CreateBiTree(,求二叉树的高度,采用递归的方法定义二叉树的高度：（1）若二叉树为空，则高度为0；（2）若二叉树非空，其高度应为其左右子树高度的最大值加1。,int TreeDepth(Btree bt)int hl,hr,max;if(bt!=NULL)hl=TreeDepth(bt-Lchild);hr=TreeDepth(bt-Rchild);,max=(hl，hr);return(max+1);else return(0);,在中根遍历的线索树中查找前驱结点,对于二叉树中任意结点p，要找其前驱结点,当p-Ltag=1时，p-Lchild即为p的前驱结点；当p-Ltag=0时，说明p有左子树，此时p的中根遍历下的前驱结点即为其左子树右链下的最后一个结点。,Void Previous(ThreadTnode*p,ThreadTnode*pre)ThreadTnode*q;if(p-Ltag=1)pre=p-Lchild;else for(q=p-Lchild;q-Rtag=0;q=q-Rchild);pre=q;,在中根遍历的线索树中查找后继结点,二叉树中任意结点p，若要找其后继结点，当p-Rtag=1时，p-Rchild即为p的后继结点；当p-Rtag=0时，说明p有右子树，此时p的中根遍历下的后继结点即为其右子树左链下的最后一个结点。,Void Succedent(ThreadTnode*p,ThreadTnode*succ)ThreadTnode*q;if(p-Rtag=1)succ=p-RChild;else for(q=p-RChild;q-Ltag=0;q=q-LChild);succ=q;,6.4 树和森林,树的存储结构,双亲（链表）表示法,用一组连续的存储空间（数组）来存储树中的结点，每个数组元素中不但包含结点本身的信息，还保存该结点双亲结点在数组中的下标号。数组中每个结点含两个域：数据域：存放结点本身信息 双亲域：指示本结点的双亲结点在数组中位置,在双亲表示法下，树的数据类型定义如下：#define Maxsize 50typedef struct NodeDataType data;int parent;Tnode;Tnode PtreeMaxsize;,1,1,2,2,3,5,5,5,1,6,0,1,2,3,4,5,7,8,data,parent,如何找孩子结点,孩子链表表示法,把每个结点的孩子结点排列起来，构成一个单链表，该单链表就是本结点的孩子链表。具有n个结点的树就形成了n个孩子链表,孩子结点#define Maxsize 50typedef struct ChildNodeint Child;struct ChildNode*next;ChildNode;,表头结点typedef structDataType data;ChildNode*ChildHead;DataNode;孩子链表 DataNode CtreeMaxsize;,孩子兄弟链表表示法,又称为二叉链表表示法，即以二叉链表作为树的存储结构。链表中每个结点设有两个链域，与二叉树的二叉链表表示法所不同的是，这两个链域分别指向该结点的第一个孩子结点和下一个兄弟（右兄弟）。,typedef struct CSNode DataType data;Struct CSNode*FirstChild,*Nextsibling;*CSTree;,对应,结论：树的孩子兄弟链表表示法与对应二叉树的二插链表表示法相同。因此，上图中的树与二叉树之间存在相互转换的关系。,树转换成的二叉树其右子树一定为空,树转换为二叉树,加线：在树中所有相邻的兄弟之间加一连线；抹线：对树中每个结点，除了其左孩子外抹去该结点与其余孩子之间的连线。整理：以树的根结点为轴心，将整树顺时针转45。,森林转换成二叉树 将各棵树分别转换成二叉树 将每棵树的根结点用线相连 以第一棵树根结点为二叉树的根，再以根结点为轴心，顺时针旋转，构成二叉树型结构,二叉树转换成树加线：若p结点是双亲结点的左孩子，则将p的右孩子，右孩子的右孩子，沿分支找到的所有右孩子，都与p的双亲用线连起来抹线：抹掉原二叉树中双亲与右孩子之间的连线调整：将结点按层次排列，形成树结构,二叉树转换成森林 抹线：将二叉树中根结点与其右孩子连线，及沿右分支搜索到的所有右孩子间连线全部抹掉，使之变成孤立的二叉树 还原：将孤立的二叉树还原成树,树和森林的遍历,树的遍历 先根遍历 若树非空，则遍历方法为：a.访问根结点。b.从左到右，依次先根遍历根结点的每一棵子树。后根遍历 若树非空，则遍历方法为：a.从左到右，依次后根遍历根结点的每一棵子树。b.访问根结点。按层次遍历 若树非空，则遍历方法为：先访问第一层上的结点，然后依次遍历第二层，第n 层的结点。,先根遍历：,后根遍历：,层次遍历：,A,B,E,F,I,G,C,D,H,J,K,L,N,O,M,E,I,F,G,B,C,J,K,N,O,L,M,H,D,A,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,森林的遍历,先根遍历若森林非空，则遍历方法为：a.访问森林中第一棵树的根结点。b.先根遍历第一棵树的根结点的子树森林。c.先根遍历除去第一棵树之后剩余的树构成的森林。中根遍历 若森林非空，则遍历方法为：a.中根遍历森林中第一棵树的根结点的子树森林。b.访问第一棵树的根结点。c.中根遍历除去第一棵树之后剩余的树构成的森林。后根遍历 若森林非空，则遍历方法为：a.后根遍历森林中第一棵树的根结点的子树森林。b.后根遍历除去第一棵树之后剩余的树构成的森林。c.访问第一棵树的根结点。,先根遍历：A B C D E F G H I J中根遍历：B C D A F E H J I G后根遍历：D C B F J I H G E A,6.5 哈夫曼树及其应用,与哈夫曼树相关的基本概念 路径和路径长度 路径：从一个结点到另一个结点之间的分支序列。路径长度：是指从一个结点到另一个结点所经过的分支数目。结点的权和带权路径长度 结点的权：在实际的应用中，人们常常给树的每个结点赋予一个具有某种实际意义的数值，我们称该数值为这个结点的权。结点的带权路径长度：从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度。树的带权路径长度 树的带权路径长度是指树中所有叶子结点的带权路径长度之和。,树的带权路径长度 树的带权路径长度是指树中所有叶子结点的带权路径长度之和。,哈夫曼树：是由n个带权叶子结点构成的所有二叉树中带权路径长度WPL最小的二叉树。哈夫曼树又叫最佳判定树。,哈夫曼树,例：有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,构造Huffman树的方法Huffman算法 构造Huffman树步骤根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和在森林中删除这两棵树，同时将新得到的二叉树加入森林中重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树,例 w=5,29,7,8,14,23,3,11,哈夫曼树的应用 最佳判定树 学生成绩的分布呈正态分布即：中等成绩的学生较多，而较好或较差学生均比较少。设其分布规律如下表：,（a）,（b）,若采用图（a）来进行判断，则80%以上的数据要进行三次或三次以上的比较才能得到结果。而如果我们以各分数段人数的占总人数的比例5、15、40、30、10为权值构造哈夫曼树，可得到（b）所示的判定树来进行判断可以使大部分数据经过较少次数的比较得到结果。,哈夫曼编码 哈夫曼树还被广泛的应用在编码技术中。利用哈夫曼树，我们可以得到平均长度最短的编码。,设有一台模型机，共有7种不同的指令，其使用频率如下：,为了充分地利用编码信息和减少程序的总位数，我们考虑采用变长编码。如果对每一条指令指定一条编码，使得这些编码互不相同且最短。若要设计变长的编码，这种编码必须满足这样一个条件：任意一个编码不能成为其它任意编码的前缀。我们把满足这个条件的编码叫做前缀编码。利用哈夫曼算法，可以设计出最优的前缀编码。,以每条指令的使用频率为权值构造哈夫曼树，构造结果如图所示：,哈夫曼编码算法的实现,数据类型的定义如下：typedef struct Nodeint weight;int parent,LChild,RChild;HTNode,*HTree;typedef char*HuffmanCode;创建哈夫曼树并求哈夫曼编码的算法如下：viod CreatHTree(HTree*ht,HuffmanCode*hc,int*w,int n)/*w存放n个权值,构造哈夫曼树ht,并求出哈夫曼编码hc*/int start;m=2*n-1;*ht=(HTree)malloc(m+1)*sizeof(HTNode);,for(i=1;i=n;i+)(*ht)i=wi,0,0,0;for(i=n+1;i=m;i+)(*ht)i=0,0,0,0;/*初始化*/for(i=n+1;i=m;i+)select(ht,i-1,/*哈夫曼树建立完毕*/,/*以下程序是从叶子结点到根，逆向求每个叶子结点对应的哈夫曼编码的过程*/*hc=(HuffmanCode)malloc(n+1)*sizeof(char*);cd=(char*)malloc(n*sizeof(char);cdn-10；for(i=1;i=n;i+)start=n-1;for(c=i,p=(*ht)i.parent;p!=0;c=p,p=(*ht)p.parent)if(*ht)p.LChild=c)cd-start=0;else cd-start=1;(*hc)i=(char*)malloc(n-start)*sizeof(char);strcpy(*hc)i,6.5 树的计数,具有n个结点的树（或二叉树）有多少种不同的形态？这个问题就称之为树的计数问题。掌握了树的计数问题就可以在已知树中结点数的情况下预计树的各种不同的形态。首先考虑n值较小的情况：n0时，b01，是空二叉树；n1时，b11，是只有一个根结点的二叉树；n2时，b22，二叉树形态见图6.26；n3时，b35，二叉树形态见图6.27。,图6.26 n2,图6.27 n3,一般情况下，一棵具有n(n1)个结点的二叉树可以看成是由一个根结点、一棵具有i个结点的左子树、和一棵具有n-i-1个结点的右子树组成的，如图6.28所示，其中0in-1。,由此可得出如下递推公式：,由上式可知：当n3时，b3b0*b2+b1*b1+b2*b0=5 恰好同上面采用观察方法得到的结果相同。,由二叉树的计数可推得树的计数。由“森林与二叉树的转换”中可知一棵树可转换成唯一的一棵没有右子树的二叉树，反之亦然。则具有n个结点有不同形态的树的数目tn 和具有n-1个结点互不相似的二叉树的数目相同。即tn=bn-1。下图展示了具有4个结点的树和具有3个结点的二叉树的关系。,