高中信息技术 竞赛班数据结构专项培训教程 07树教案-人教版高中全册信息技术教案VIP免费

§7树§7.1树的概念【定义】树（Tree）是n（n>0）个结点的有限集合T，它满足如下两个条件：(1)有且仅有一个特定的称为根（Root）的结点；(2)其余的结点可分为m（m≥0）个互不相交的有限集合，其中每一个集合又都是一颗树，并称为根的子树（SubTree）。【基本术语】k1.树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度（degree）。如图7.1，A的度为3，C的度为1，F的度为0。2.度为0的结点称为叶子（leaf）或终端结点。例如K、L、F、G、M、I、J。度不为0的结点称为分支结点或非终端结点。除根结点外，分支结点也称为内部结点。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的为E、F、K、L。5.结点的层次（level）是从根开始定义起，根为第一层，根的孩子为第二层。若某结点在第x层，则其子树的根就在x+1层。树中结点的最大层次称为树的高度或深度（depth）。如图7.1的树的深度为4。6.如果将树中的结点的各子树看成从左到右是有次序的（即不能互换），则称该树为有序树,否则称为无序树。如图7.1.2。图7.1.1图7.1.2两棵不同的有序树7.森林（forest）是m（m≥0）棵互不相交的树的集合。§7.2二叉树§7.2.1二叉树的定义二叉树（binarytree）是一种树型结构，它的每个结点至多只有二棵子树（即二叉树中不存在度大于2结点），并且，二叉树的子树有左右之分，其次序不能任意颠倒。（如图7.2.1）满二叉树和完全二叉树是两种特殊形态的二叉树。满二叉树是指深度为k，且有2k-1个结点的二叉树。完全二叉树是指深度为k，有n个结点，当且仅当每一个结点都与深度为k的满二叉树中编号从1到n的结点一一对应时。§7.2.2二叉树的性质性质1：在二叉树的第i层上至多有①个结点（i≥1）。性质2：深度为k的二叉树至多有②个结点（k≥1）。性质3：对任意一棵二叉树，如果度为2的结点数为n2，则其叶子结点数为③。性质4：具有n个结点的完全二叉树的深度为图7.2.1图7.2.2满二叉树图7.2.3完全二叉树图7.2.4非完全二叉树性质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≤j