数据结构（C语言描述） 马秋菊 第6章树

《数据结构（C语言描述） 马秋菊 第6章树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第6章树6.1树的概念与表示6.2二叉树的概念与性质6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树的存储结构6.7树、森林与二叉树的转换6.8哈夫曼树及其应用小结1本章学习目标树型结构是一类重要的非线性结构，在计算机领域有着广泛的应用，如数据库系统中的信息组织等。通过本章学习，应掌握如下内容：树的定义及相关术语。二叉树的性质、存储结构及其遍历算法。树的存储结构，树和森林与二叉树的转换。哈夫曼算法及应用。26.1树的概念与表示6.1.1树的定义树（Tree）是n个（n≥0）个结点组成的有限集合T，当T为空集时称为空树，否则它满足如下两个条件：(1)有且仅有一个特定

2、的称为根（Root）的结点。(2)除根结点外的其余结点可分为m（m>0）个互不相交的子集T1，T2，…，Tm，其中每个子集Ti本身又是一棵树，并称其为根的子树。ABFDEGICHKA树非树3树具有下面两个特点：（1）树的根结点没有前驱结点，除根结点之外的所有结点有且只有一个前驱结点。（2）树中所有结点可以有零个或多个后继结点。WEBHELFONTSYSDOSUSERWINC:TEMCOMTEMP46.1.2树的相关术语结点：一个数据元素及若干个指向其子树的分支。结点的度：结点所拥有的子树的个数称为该结点的度。树的度：树中结点度的最大值。ABFKDEGICHLJ叶子结点：度为0的

3、结点称为叶子结点，或者称为终端结点。分支结点：度不为0的结点称为分支结点或非终端结点。孩子、双亲和兄弟结点：树中结点子树的根称为该结点的孩子。相应地，该结点称为孩子结点的双亲。5ABFKDEGICHLJ具有同一个双亲的孩子结点互称为兄弟。祖先、子孙：从树中根结点到某一结点所经过的分支上的所有结点称为该结点的祖先。反之，以某结点为根的子树中的任一结点都称为该结点的子孙。结点的层数：规定树的根结点的层数为1，其余结点的层数等于它的双亲结点的层数加1。树的深度：树中所有结点的最大层数称为树的深度或高度。有序树和无序树：如果一棵树中结点的各子树从左到右是有次序的——有序树；反之，——无序

4、树。森林：m（m≥0）棵互不相交的树的集合称为森林。66.1.3树的表示树的表示有四种方法，直观表示法、嵌套集合表示法、凹入表示法、广义表表示法。ABCEDFHGIABDEHFCGI(A(B(D,E(H),F),C(G,I)))广义表表示法ABFKDEGICHLJ76.2二叉树的概念与性质6.2.1二叉树的基本概念定义：二叉树是n个（n≥0）结点的集合，该集合或者为空、或者由一个根结点和两个分别称为左子树和右子树的互不相交的二叉树组成，当集合为空时，称该二叉树为空二叉树。二叉树具有五种基本形态：空二叉树、仅有根结点的二叉树、右子树为空的二叉树、左子树为空的二叉树和左右子树均不为空

5、的二叉树。左子树右子树左子树右子树(b)仅有根结点(c)右子树为空(d)左子树为空(e)左右子树均不为空二叉树的五种基本形态86.2.2二叉树的重要性质二叉树有以下重要性质。性质1二叉树的第i（i≥1）层上最多有2i-1个结点。对非空二叉树，第一层为根结点，最多只有一个结点，即20个；显然第二层最多有21个；以此类推，第i层上最多只有2i-1个结点。性质2在一棵深度为k的二叉树中，最多具有2k－1个结点。ABFECABCDEGFHIKJMLNO1523467891011121314159性质2在一棵深度为k的二叉树中，最多具有2k－1个结点。证明：由性质1可知，第i层的结点数最多

6、为2i-1（1≤i≤k），则深度为k的二叉树的结点数最多为：性质3对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0＝n2＋1。ABFECABCDEGFHIKJMLNO15234678910111213141510证明：设度为i的结点有ni个(其中：i=0，1，2)，总结点个数为n，总分支数为e，则根据二叉树的定义，有如下的式子：n=n0+n1+n2e=2n2+n1=n-1将两式结合有：2n2+n1=n0+n1+n2-1即有n0=n2+1一棵深度为k且有2k－1个结点的二叉树称为满二叉树。当深度为k，含有n个结点的二叉树，当且仅当其每个结点的编号与相应

7、满二叉树结点顺序编号从1~n互相对应时，则称此二叉树为完全二叉树。ABCDEGFHIKJMLNO152346789101112131415ABFEC11(c)非完全二叉树DA123674BCEFACBEDFGHIJ12435768910(b)完全二叉树ACBEDFGHIJ12435768910LM1213NO1415K11(a)满二叉树12性质4具有n个结点的完全二叉树的深度k为。性质5对于具有n个结点的完全二叉树，如果按照从上至下和从左到右的顺序对所有结点从1开始顺序编号，则对