树的结构定义和基本术语(精)课件

第第6 6章章 树树6.1 6.1 树的结构定义和基本术语树的结构定义和基本术语6.2 6.2 二叉树二叉树 6.2.1 二叉树的定义 6.2.2 6.2.2 二叉树的性质 6.2.3 6.2.3 二叉树的存储结构6.3 6.3 遍历二叉树和线索二叉树遍历二叉树和线索二叉树 6.3.1 遍历二叉树 6.3.2 线索二叉树6.4 树和森林的遍历树和森林的遍历6.5 6.5 哈夫曼树及其应用哈夫曼树及其应用 5.5.1 最优二叉树(哈夫曼树)5.5.2 哈夫曼编码定义定义：树(Tree)是n(n=0)个结点的有限集。在任意一棵非空树中：(1)(1)存在唯一的称为存在唯一的称为根根的结点的结点root,root,(2)(2)当当n1n1时，其余结点可分为时，其余结点可分为m(m0)m(m0)个个互不相交的互不相交的有有限集限集T1,T2,Tm,T1,T2,Tm,其中每一个集合本身又是一棵符合本其中每一个集合本身又是一棵符合本定义的树，并且称为定义的树，并且称为根的子树根的子树。A(B (E (K,L),F),C (G),D (H (M),I,J)T1T3T2树根(b)(a)上面是图的广义表表示形式图的嵌套形式表示和凹入表示法见图6.2 例如：例如：结点结点:结点的度结点的度:树的度树的度:叶子结点叶子结点:分支结点分支结点:数据元素+若干指向子树的链接分支的个数树中所有结点的度的最大值度为零的结点度大于零的结点D DH HI IJ JM M基本术语基本术语路径：路径：孩子孩子结点、双亲双亲结点、兄弟兄弟结点、堂兄弟祖先祖先结点、子孙子孙结点由从根根到该结点所经分支和结点构成A AB BC CD DE EF FG GH HI IJ JM MK KL L结点的层次结点的层次:假设根结点的层次为1,第l 层的结点的子树根结点 的层次为l+1树的深度树的深度：树中叶子结点所在的最大层次森林：是m（m0）棵互不相交的树的集合任何一棵非空树是一个二元组 Tree=Tree=（rootroot，F F）其中：root 被称为根结点，F 被称为子树森林A ArootrootB BC CD DE EF FG GH HI IJ JM MK KL LF F()有确定的根；()树根和子树根之间为有向关系。有向树：有向树：有序树：有序树：子树之间存在确定的次序关系。无序树：无序树：子树之间不存在确定的次序关系。线性结构线性结构 关系关系:(1:1):(1:1)树型结构树型结构 关系关系:(1:M):(1:M)第一个数据元素第一个数据元素 (无前驱无前驱)根结点根结点 (无前驱无前驱)最后一个数据元素最后一个数据元素 (无后继无后继)多个叶子结点多个叶子结点 (无后继无后继)其它数据元素其它数据元素(一个前驱、一个前驱、一个后继一个后继)其它数据元素其它数据元素(一个前驱、一个前驱、多个后继多个后继)对比树型结构和线性结构的结构特点对比树型结构和线性结构的结构特点 二叉树二叉树(binary tree)是另一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分左右之分，其次序不能任意颠倒。定义定义:二叉树或为空树空树；或是由一个根结点根结点加上两棵两棵分别称为左子树左子树和右子树的、互不交的互不交的二叉树二叉树组成。这也是一个递归定义。二叉叉树不是树的特殊情况，它们是两个独立的概念。ABCDEFGHK根结点左子树右子树二叉树的五种基本形态：二叉树的五种基本形态：N空树空树只含根结点只含根结点NNNLRR右子树为空树右子树为空树L左子树为空树左子树为空树左右子树均左右子树均不为空树不为空树用归纳法证明：用归纳法证明：归纳基：归纳基：归纳假设：归纳假设：归纳证明：归纳证明：i=1 层时，只有一个根结点，2i-1=20=1；假设对i-1层，命题成立;即有2i-2个结点二叉树上每个结点至多有两棵子树，则第 i 层的结点数=2i-2 2=2i-1 。证明：证明：基于性质1，深度为 k 的二叉树上的结点数至多为20+21+2k-1=2k-1 证明：证明：设设 二叉树上结点总数n=n0+n1+n2 b=n1+2n2 （1）而b=n-1=n0+n1+n2 1 （2）由此，由此，n0=n2+1又又 二叉树上分支总数l 两类特殊的二叉树：两类特殊的二叉树：满二叉树满二叉树：指的是深度为k k且含有2 2k k-1-1个结点的二叉树。完全二叉树完全二叉树：树中所含的 n n 个结点和满二叉树中编号为编号为 1 1 至至 n n 的结点的结点一一对应。123456789101112131415abcdefghij性质性质4：完全二叉树具有：完全二叉树具有n个结点的完全二叉树的深度为个结点的完全二叉树的深度为 log2n +1证：证：(1)设树深度为设树深度为k，根据性质，根据性质2，n=2k-1 (2)由定义：由定义：n大于深度为大于深度为k-1的满二叉树的结点数的满二叉树的结点数2k-1-1 因此因此 2k-1-1n=2k-1 即即 2k-1=n2k （不等式原理）（不等式原理）k-1=log2nk k是整数是整数 k-1=log2n 成立成立(取等号式子取等号式子)故故k=log2n +1 性质：完全二叉树中性质：完全二叉树中,已知点已知点i可推知其父点，子点位置。可推知其父点，子点位置。有有n个结点的完全二叉树（即其深度为个结点的完全二叉树（即其深度为 log2n +1），），是如上述有序表示的，则对任一结点是如上述有序表示的，则对任一结点i,=i1,i的双亲是的双亲是 PARENT（i）是）是 i/2 。（）如果（）如果2i=n,则则i的左子的左子LCHILD(i)是结点是结点2i,否则否则i无左子。无左子。（3）如果）如果2i+1data);/访问结点 Preorder(T-l lchild,visit);/遍历左子树 Preorder(T-r rchild,visit);/遍历右子树 先序遍历递归算法的描述（补充）先序遍历递归算法的描述（补充）status PreOrderT(BiTree T)if(T!=NULL)printf(“%d”,T-data);PreOrderT(T-Lchild);PreOrderT(T-rchild);四、中序遍历递归算法的描述四、中序遍历递归算法的描述 status InOrederT(BiTree T)if(T!=NULL)InOrederT(T-Lchild);printf(“%d”,T-data);InOrderT(T-rchild);以图以图6.9为例分析执行过程。为例分析执行过程。五、中序遍历非递归算法五、中序遍历非递归算法6.3说明：只根点进栈，左右子为空时不进栈说明：只根点进栈，左右子为空时不进栈 P131Status InOrder T(BiTree T,Status(*Visit)(TelemType e)InitStack(S);p=T;/P扫描扫描While(pStackEmpty(S)/P46,S空则返回空则返回True,S非空返回非空返回 false if(p)Push(s,p);p=plchild /根进栈根进栈,遍历左子树遍历左子树 else pop(s,p);if(!visit(pdata)return ERROR;p=prchild;while return OK /算法算法6.2：根、右子均进栈，用双重循环：根、右子均进栈，用双重循环 六、先序建立二叉树的六、先序建立二叉树的算法算法 Status CreateBiT(BiTree&T)Status CreateBiT(BiTree&T)scanf(&ch);scanf(&ch);If(ch=”)T=NULL;If(ch=”)T=NULL;else else T=T=（BiTNode BiTNode*)malloc(sizeof(BiTNode)malloc(sizeof(BiTNode)；Tdata=ch;Tdata=ch;CreateBiT(Tlchild);CreateBiT(Tlchild);CreateBiT(Trchild);return OK CreateBiT(Trchild);return OK 以字符串的形式以字符串的形式 按先序序列建立一棵二叉树按先序序列建立一棵二叉树例如:A AB BC CD D以空白字符“”表示A A(B B(,C C(,),D D(,)空树空树只含一个根结点的二叉树只含一个根结点的二叉树 A A以字符串“A A ”表示以下列字符串表示A B CD建立过程举例如下:ATBCD一、双亲表示法一、双亲表示法二、孩子链表表示法二、孩子链表表示法三、孩子三、孩子-兄弟表示法（树的二叉链表）兄弟表示法（树的二叉链表）ABCDEFG0A-11 B02C03D04E25F26G5r=0n=6dataparent一、双亲表示法一、双亲表示法:二、孩子链表表示法二、孩子链表表示法:1 1、多重链表表示法、多重链表表示法：每个结点有多个指针域，其中每个指针指向一棵子树根结点。有两种表示方式；a)非固定大小结点结构b)链表中结点同构，链表中域的数目为树的度。ABCDEFG0A-11B02C03D04E25F26G41234562 2、单链表表示法：、单链表表示法：把每个结点的所有孩子链接起来，以单链表作存储结构。则n个结点有n个孩子链表。三、三、孩子孩子-兄弟表示法（树的二叉链表）：又兄弟表示法（树的二叉链表）：又称二叉链表表示法。链表中结点的两个域分别指向该称二叉链表表示法。链表中结点的两个域分别指向该结点的第一个孩子结点和下一个兄弟结点。结点的第一个孩子结点和下一个兄弟结点。ABCDEFG AB C E D F Groot AB C E D F G（一）树转化为二叉树（一）树转化为二叉树 以二叉链表为媒介可导出树与二叉树之间的一个对应关系。即，给定一棵树，可以找到唯一的一棵二叉树与之对应。树转化为二叉树的方法：（1）在树中个兄弟之间加一连线；（2）对于任一结点，只保留它与最左孩子之间的连线 （3）以树的根结点为轴心，将整棵树按顺时针方向旋转成二叉树。应当注意的是：和树对应的二叉树，其左、右子树的概念已应当注意的是：和树对应的二叉树，其左、右子树的概念已改变为：改变为：左是孩子，右是兄弟左是孩子，右是兄弟ABCDEFG AB C E D F G由树转换成的二叉树，其根结点的右子树总是空的。说明任一棵树，可以找到唯一的一棵二叉树与之对应。反之，任一棵二叉树（如果有右子树），不一定有树与之对应。故两者不是一一对应关系 （二）森林转化为二叉树（二）森林转化为二叉树将森林中的每一棵树依次转换成相应的二叉树，然后将第二棵作为第一棵二叉树的根结点的右子树连接起来，将第三棵又作为第二棵的右子树连接起来.直至把所有的二叉树连接成一棵二叉树。反之我们也可方便地将二叉树转化为森林。因此，森林与二叉树 是一一对应是一一对应的的 BCDEFGCIJHLK 练习：练习：树的各种操作均可对应二叉树的操作来完成。应当注意的是，应当注意的是，和树对应的二叉树，其左、右子树的概念已改变为：左是孩子，右是兄弟左是孩子，右是兄弟一、树的遍历一、树的遍历二、森林的遍历二、森林的遍历三、树的遍历的应用三、树的遍历的应用树的遍历可有三条搜索路径树的遍历可有三条搜索路径:按层次遍历按层次遍历:先根先根(次序次序)遍历遍历:后根后根(次序次序)遍历遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。ABCDEFGHIJK先根遍历时顶点的访问次序：先根遍历时顶点的访问次序：A B E F C D G H I J K后根遍历时顶点的访问次序：后根遍历时顶点的访问次序：E F B C I J K H G D A层次遍历时顶点的访问次序：层次遍历时顶点的访问次序：A B C D E F G H I J KBCDEFGHIJK1。森林中第一棵树的根结点；2。森林中第一棵树的子树森林；3。森林中其它树构成的森林。森林由三部分构成：1.1.先序遍历先序遍历森林的遍历森林的遍历 若森林不空，则若森林不空，则访问森林中第一棵树的根结点访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林先序遍历森林中第一棵树的子树森林;先序遍历森林中先序遍历森林中(除第一棵树之外除第一棵树之外)其其余树构成的森林。余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行先根遍历先根遍历。中序遍历中序遍历若森林不空，则：中序遍历中序遍历森林中第一棵树的子树森林;访问访问森林中第一棵树的根结点;中序遍历中序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右依次从左至右对森林中的每一棵树树进行后根遍历后根遍历。树的遍历和二叉树遍历的对应关系树的遍历和二叉树遍历的对应关系？先根遍历先根遍历后根遍历后根遍历树树二叉树二叉树森林森林先序遍历先序遍历先序遍历先序遍历中序遍历中序遍历中序遍历中序遍历树的先根序遍历与后根序遍历可通过对其相应的二叉树的进行先序遍历和中序遍历得到6.8.1 6.8.1 最优二叉树（赫夫曼树）的定义最优二叉树（赫夫曼树）的定义 树的路径长度树的路径长度定义为：树中每个结点的路径长度之和。结点的路径长度结点的路径长度定义为：从根结点到该结点的路径上分支的数目。路径：路径：从树中一个点到另一个结点之间的分支构成这两个节点的路径。路径长度：路径长度：路径上的分支数目 树的带权路径长度树的带权路径长度定义为：树中所有叶子结点的带权路径长度结点的带权路径长度之和 WPL(T)=wklk(对所有叶子结点)赫夫曼树的定义赫夫曼树的定义（P144）假设有n 个权值 w1,w2,wn，试构造一 棵有n个叶子结点的二叉树，每个叶子结点带权为wi，则其中带权路径长度则其中带权路径长度WPL最小的最小的二叉树，称做最优最优二叉树或赫夫曼树。赫夫曼树。27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954构造赫夫曼树的算法：构造赫夫曼树的算法：给定 n 个权值 w1,w2,wn，构造赫夫曼树。（1）构造 n 棵二叉树的集合 F=T1,T2,Tn，其中每棵二叉树中均只含一个带权值为 wi 的根结点,其左、右子树为空树;6.8.2 6.8.2 如何构造如何构造赫夫曼树赫夫曼树（2）在 F 中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;（3）从F中删去这两棵树，同时加入 刚生成的新树;（4）重复(2)和(3)两步，直至 F 中只 含一棵树为止。7例如:已知权值 W=5,6,2,9,7 2569257697671392576713925792571667132900001111000110110111 指的是，任何一个字符的编码都不是同一字符集中另指的是，任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。一个字符的编码的前缀。6.8.3 6.8.3 前缀编码前缀编码 利用赫夫曼树可以构造一种不等长的二进制编码，并且构利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。长度最短。1.1.熟练掌握二叉树的结构特性，了解相应的证明方法。熟练掌握二叉树的结构特性，了解相应的证明方法。2.2.熟悉二叉树的各种存储结构的特点及适用范围。熟悉二叉树的各种存储结构的特点及适用范围。3.3.遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的具体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，体算法与所采用的存储结构有关。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜灵活运用遍历算法实现二叉树的其它操作。层次遍历是按另一种搜索策略进行的遍历。索策略进行的遍历。4.4.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。掌握转换方法。掌握 1 1 至至 2 2 种建立二叉树和树的存储结构的方法。种建立二叉树和树的存储结构的方法。5.5.学会编写实现树的各种操作的算法。学会编写实现树的各种操作的算法。6.6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。一、概念一、概念树的定义、层次、深度、度、二叉树、满二叉树、完全二树的定义、层次、深度、度、二叉树、满二叉树、完全二叉树、哈夫曼树、树的路径长度叉树、哈夫曼树、树的路径长度二、思考题与设计题二、思考题与设计题二叉树和树的最主要的区别是什么？二叉树和树的最主要的区别是什么？写出先序遍历的非递归算法。写出先序遍历的非递归算法。度为度为2 2的树与二叉树有何区别？的树与二叉树有何区别？写出二叉树的存储结构（二叉链表）的数据类型描述。写出二叉树的存储结构（二叉链表）的数据类型描述。设字符集为设字符集为a,b,c,d,e,f,g,ha,b,c,d,e,f,g,h，它们出现的频率分别为：，它们出现的频率分别为：4 4，8 8，5 5，3 3，2 2，6 6，1010，7 7。以这。以这8 8个字符的频率为权值，构造个字符的频率为权值，构造一棵赫夫曼树。一棵赫夫曼树。