第六章树和二叉树

《第六章树和二叉树》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章树和二叉树16.1树的结构定义和基本操作树是n(n>=0)个结点的有限集。在一颗非空树中：1）有且仅有一个特定的称为根(root)的结点；2）当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1，T2,…,Tm，其中每个集合本身又是一颗树，并且称为根的子树(subtree)。ABDEFCGHIJKLM2树的四种表示方法1）树型2）广义表3）嵌套集合表4）凹入表示法3）嵌套集合KLGFMIJABDHCE(A(B(E(K,L),F),C(G),D(H(M),I,J)))2)广义表表示法ABDCEFGH

2、IJKLM1）树型表示法34)凹入表表示法KLFCGDHMIJEBA4树结构中的基本术语1.结点的度：结点具有的子树数称为该结点的度(Degree)。叶子结点：度为0的结点，即没有子树的结点。分支结点：度大于零的结点。内部结点：除根结点外的分支结点。树的度：一棵树中各个结点度数的最大值。2.儿子结点和父亲结点：一个结点的子树的根称为该结点的儿子结点；反之，该结点则称为其孩子结点的父亲结点。兄弟结点：同一个结点的儿子结点之间互称为兄弟结点。53.路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径。

3、子孙结点：一个结点的子树中所有结点均称之为该结点的子孙结点。祖先结点：反之，从根结点到达一个结点的路径上的所有结点，都叫做该结点的祖先结点。4.树的深度：树是一种层次结构，树中结点的层次（Level）是从根结点算起的。根结点为第一层，其儿子结点为第二层。其余各结点的层数逐层由上而下计算。一棵树中结点的最大层数叫做此树的深度或高度。65.有序树和无序树：若将树中每个结点的各子树看成是从左到右有次序的，则称该树为有序树；否则称为无序树。6.森林：n个树的集合叫森林(Forest)。树形结构的逻辑特征可用树中结点之间

4、的父子关系来描述：树中任一结点都可以有零个或多个直接后继结点（即儿子结点），但至多只能有一个直接前趋结点（即父亲结点）。树中只有根结点无前趋，它是开始结点；叶结点无后继，它们是终端结点。76.2二叉树二叉树是n个结点的有限集合（n≥0），此集合或者是空集（n=0），或者是由一个根结点及两棵互不相交的、分别称为左子树和右子树的二叉树组成。abcdefg8二叉树有五种基本形态(a)空二叉树(b)仅有一个根结点的二叉树(c)右子树为空的二叉树(d)左子树为空的二叉树(e)左、右子树均非空的二叉树9二叉树与度为二的有序

5、树的区别：二叉树的子树有左右之分，而度为二的有序树当某个结点只有一个子结点时是没有先后之分的。10二叉树的性质性质1在二叉树的第i层上至多有2i-1个结点。(可由数学归纳法证明)性质2一棵深度为k的二叉树中，最多具有2k－1个结点。证明:设第i层的结点数为xi（1≤i≤k），深度为k的二叉树的结点数为M，xi最多为2i-1，则有：20+21+…+2k-1=2k-111性质3对于一棵非空的二叉树，如果叶子结点数为n0，度数为2的结点数为n2，则有:n0＝n2＋1*证明:设n为二叉树的结点总数，n1为二叉树中度为1

6、的结点数，则有：n＝n0＋n1＋n2(1)在二叉树中，除根结点外，其余结点都有唯一的一个进入分支。设B为二叉树中的分支数，那么有：B＝n－1(2)12这些分支是由度为1和度为2的结点发出的，一个度为1的结点发出一个分支，一个度为2的结点发出两个分支，所以有：B＝n1＋2n2(3)由（2）、（3）得n=n1＋2n2+1(4)由(1)、(4)得n0＝n2＋113满二叉树在一棵二叉树中，如果所有分支结点都存在左子树和右子树，并且所有叶子结点都在同一层上，这样的一棵二叉树称作满二叉树。或者：一棵深度为k且有2k-1个结

7、点的二叉树称为满二叉树。14完全二叉树一棵深度为k的有n个结点的二叉树，对树中的结点按从上至下、从左到右的顺序进行编号，如果编号为i（1≤i≤n）的结点与满二叉树中编号为i的结点在二叉树中的位置相同，则这棵二叉树称为完全二叉树。完全二叉树的特点是：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。15性质4具有n个结点的完全二叉树的深度k为证明：根据完全二叉树的定义和性质2可知，当一棵完全二叉树的深度为k、结点个数为n时，有2k－1－1

8、≤log2n1，则序号为i的结点的双亲结点的序号为i/2(“/”表示整除)；如果i＝=1，则序号为i的结点是根结点，无双亲结点。（2）如果2i≤n，则序号为i的结点的左孩子结点的序号为2i；如果2i>n，