高中信息技术-竞赛班大数据结构专项培训教程-07树教案设计.doc

《高中信息技术-竞赛班大数据结构专项培训教程-07树教案设计.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实用文档§7树§7.1树的概念【定义】树（Tree）是n（n>0）个结点的有限集合T，它满足如下两个条件：(1)有且仅有一个特定的称为根（Root）的结点；(2)其余的结点可分为m（m≥0）个互不相交的有限集合，其中每一个集合又都是一颗树，并称为根的子树（SubTree）。图7.1.1【基本术语】k1.树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（degree）。如图7.1，A的度为3，C的度为1，F的度为0。2.度为0的结点称为叶子（leaf）或终端结点。例如K、L、F、G、M、I、J。度不为0的

2、结点称为分支结点或非终端结点。除根结点外，分支结点也称为内部结点。3.树的度是树内各结点的度的最大值，如图7.1中树的度为3。4.结点的子树的根称为该结点的孩子（Child），该结点称为孩子的双亲（parent）。如图7.1.1，B为A的子树的根，则B是A的孩子，而A则是B的双亲。同一个双亲的孩子之间互称为兄弟（sibling），例如B、C、D互为兄弟。实用文档将这些关系进一步推广，可认为D是M的祖父。结点的祖先是从根到该结点所经分支上的所有结点。例如，M的祖先为A、D、H。反之，结点的子树中的任一结点都称为该结点的子孙，如B的为

3、E、F、K、L。5.结点的层次（level）是从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第x层，则其子树的根就在x+1层。树中结点的最大层次称为树的高度或深度（depth）。如图7.1的树的深度为4。图7.1.2两棵不同的有序树6.如果将树中的结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树,否则称为无序树。如图7.1.2。7.森林（forest）是m（m≥0）棵互不相交的树的集合。§7.2二叉树图7.2.1§7.2.1二叉树的定义二叉树（binarytree）是一种树型结构，它的每个结点至多只有二

4、棵子树（即二叉树中不存在度大于2结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。实用文档（如图7.2.1）满二叉树和完全二叉树是两种特殊形态的二叉树。满二叉树是指深度为k，且有2k-1个结点的二叉树。完全二叉树是指深度为k，有n个结点，当且仅当每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时。图7.2.4非完全二叉树图7.2.3完全二叉树图7.2.2满二叉树§7.2.2二叉树的性质性质1：在二叉树的第i层上至多有①个结点（i≥1）。性质2：深度为k的二叉树至多有②个结点（k≥1）。性质3：对任意一棵二叉树，

5、如果度为2的结点数为n2，则其叶子结点数为③。性质4：具有n个结点的完全二叉树的深度为性质5：如果对一棵有n个结点的完全二叉树的结点按层序编号（每层从左到右），则对任一结点i（1≤i≤n），有：实用文档①如果i=1，则结点i是二叉树的根；如果i>1，则其双亲结点是idiv2②如果2*i>n，则结点i无左孩子（结点i为叶子结点）；否则其左孩子为2*i③如果2*i+1>n，则结点i无右孩子，否则其右孩子为2*i+1[参考答案及证明]：①2i-1证明：利用归纳法当i=1时，只有一个根结点，显然，2i-1=20=1正确；假设对所有的j，1

6、≤j

7、＝n1+2n2所以：n–1＝n1+2n2（2）由式（1）和（2）得：n0+n1+n2–1＝n1+2n2即：n0＝n2+1④证明：假设深度为K的完全二叉树的结点数为n，则根据性质2和完全二叉树定义有：或于是∵k是整数∴⑤证明略§7.2.2二叉树的存储结构1．顺序存储结构图7.2.5将二叉树的所有结点按一定的次序，存储到一片连续的存储单元中。这种结构，较适用于满二叉树或近似满二叉树。如图7.2.5中完全二叉树的存储结构如下：ABCDEFGHIJKLM实用文档123456789101112131415图7.2.6图7.2.6中的二叉树的

8、存储结构如下：ABCDFGIM123456789101112131415可以看出，当二叉树较稀疏时，采用顺序存储将造成浪费。[练习]1)如果完全二叉树最多有n层，那么存储该树的数组最少设________个单元；2)某结点存储于S[i]，则存在双亲结