6.C语言-树.pptx

第6章 树 ;6.1 树的应用实例 ;图6.1 Windows 2000系统的注册表 ;6.2 树的基本概念和术语 ; 图6.3是一棵由9个结点组成的树T。其中A是根结点，其余结点分为三个互不相交的子集：T1={B,H,I}，T2={C}，T3={D,E,F,G}。T1、T2、T3都是树根A的子树，这三棵子树的根结点分别是B、C、D。每棵子树本身也是一棵树，可继续划分。例如子树T3以D为根结点，它的其余结点又可分为两个互不相交的子集：T31={E}，T32={F，G}，而其中T31可以认为是仅有一个根结点的子树。 ;图6.2 树T ;6.2.2 树的常用术语 1. 结点的度和树的度 树的结点包含一个数据元素及若干指向其子树的分支。结点拥有的子树数称为结点的度(Degree)。而树的度是指树中结点的度的最大值。如图6.2中，B结点有2个子树，则它的度为2。在树T中，A结点的度最大，值为3，也就是说，树T的度为3。 2. 分支结点和叶子结点 称度不为0的结点为分支结点，也叫非终端结点。称度为0的结点为叶子(Leaf)或终端结点。如图6.3中，分支结点分别为A、B、D、F，而叶子结点分别为H、I、C、E、G。; 3. 孩子、双亲、兄弟、子孙、祖先 结点的子树的根称为该结点的孩子(Child)，相应地，该结点称为孩子的双亲(Parent)。同一个双亲的孩子之间互称兄弟(Sibling)。如图6.3中，B、C、D分别是根结点A的子树的根，三个都是A的孩子，相应地，A是它们的双亲，其中，B、C、D三者是兄弟。一棵树上除根结点以外的其它结点称为根结点的子孙。对于树中某结点，从根结点开始到该结点的双亲是该结点的祖先。 ; 4. 结点的层次和树的高度 结点的层次(Level)从根结点开始定义，根为第一层，根结点的孩子为第二层，依次类推，其余结点的层次值为双亲结点层次值加1。树中结点的最大层次值称为树的高度或深度(Depth)。如图6.3所示的树T高度为4。 5. 无序树、有序树、森林 若树中结点的各子树看成从左至右是有次序的(即不能互换)，则称该树为有序树，否则称为无序树。在有序树中最左边的子树的根称为第一个孩子，最右边的称为最后一个孩子。 森林(Forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。 ;6.2.3 树的表示方法 树的表示形式有多种，常见的三种方法是： (1) 倒悬树法，如图6.2所示。 (2) 嵌套集合表示法，如图6.3(a)所示。 (3) 凹入表示法，如图6.3(b)所示。 ;图6.3 树结构的不同表示方法 (a) 嵌套集合表示法；(b) 凹入表示法 ;6.3 二 叉 树 ; 这个递归定义表明二叉树或为空，或是由一个根结点加上两棵分别称为左子树和右子树的互不相交的二叉树组成的。由于左、右子树也是二叉树，则由二叉树的定义，它们也可以为空。由此，二叉树可以有五种基本形态，如图6.4所示。 ; 从以上分析得知二叉树与普通树比较，有以下特点： (1) 二叉树可以为空树。 (2) 二叉树的度不大于2(即每个结点至多只有两棵子树)。 (3) 二叉树是有序树，其左子树和右子树是严格区分且不能随意颠倒的。如图6.4(c)和图6.4(d)就是二棵不同的二叉树。 ;6.3.2 二叉树的重要性质 性质1 二叉树第i(i≥1)层上至多有2i-1个结点。 根据二叉树和结点层次的定义可知，根结点在第一层上，这层结点数至多为1个，即20个；显然第二层上至多有2个结点，即21个…… 假设第i－1层的结点至多有2i-2个，且每个结点最多有两个孩子，那么第i层上结点至多有2×2i-2=2i-1个。 性质2 深度为k(k≥1)的二叉树至多有2k－1个结点。 由性质1可知，各层结点最多数目之和为20+21+22+…+2k-1；由二进制换算关系可知：20+21+22+…+2k-1=2k－1，因此二叉树中结点的最大数目为2k－1。 ; 性质3 在任意二叉树中，若叶子结点(即度为零的结点)个数为n0，度为1的结点个数为n1，度为2的结点个数为n2，那么n0=n2+1。 证明：设n代表二叉树结点总数，那么 n=n0+n1+n2 (1)由于有n个结点的二叉树总分支数为n－1条，于是得 n－1=0×n0+1×n1+2×n2 (2)将式(1)代入式(2)得 n0=n2+1 ; 有