完全二叉树的特点 (1)叶子结点只可能 在层次最大的两层上出现。(80①④2 (2)对任一结点,若其右分支下的子孙的最大层次 为k则其左分支下的子孙的最大层次必为k或k+1。 (3)深度为k的完全二叉树,前k-1层结点构成的二 叉树必为满二叉树。 完全二叉树又定义为: 若一颗二叉树至多只有最下面的两层上结点的度数 可以小于2,并且最下一层的结点都集中在该层最左 更的若干位置上,则称此二叉树为完全二叉抛 26
26 ➢ 完全二叉树的特点： （1）叶子结点只可能 在层次最大的两层上出现。 （2）对任一结点，若其右分支下的子孙的最大层次 为k,则其左分支下的子孙的最大层次必为k或k+1。 （3）深度为k的完全二叉树，前k-1层结点构成的二 叉树必为满二叉树。 完全二叉树又定义为： 若一颗二叉树至多只有最下面的两层上结点的度数 可以小于2，并且最下一层的结点都集中在该层最左 边的若干位置上，则称此二叉树为完全二叉树。 1 2 4 8 9 5 10 3 6 7 11 12
722二叉树的性质 性质x:非空二叉树上叶子结点数等于双分支结点数加1。 设其终端结点数为n,度为2的结点数为n2,则 no=n2+1。 证明:设n为二叉树T中度为1的结点数。因为二叉树 中所有结点的度均小于或等于2,所以其缜点总 数为:n=n+n1+n2 在二叉树中,除了根结点,其余结点 3) 都有一个分支指向它,设B为分支总数,④ 则n=B+1。由于这些分支是由度为1或为2的(6 结点发出的,所以有:B=n1+2n2 故:n=m+n1+n2=n1+2n2+1(=B+→m0=n2+1
7.2.2 二叉树的性质 性质1：非空二叉树上叶子结点数等于双分支结点数加1。 设其终端结点数为n0，度为2的结点数为n2，则 n0=n2+1。 证明： 0 1 2 n = n + n + n 在二叉树中，除了根结点，其余结点 都有一个分支指向它，设B为分支总数， 则n=B+1。由于这些分支是由度为1或为2的 结点发出的，所以有: 1 2 B = n + 2n 故： 2 1( 1) n = n0 + n1 + n2 = n1 + n2 + = B + 1 n0 = n2 + 设n1为二叉树T中度为1的结点数。因为二叉树 中所有结点的度均小于或等于2，所以其结点总 数为： 1 2 3 4 5 6
已知二叉树中叶子数为50,单分支的结 点数为30,则总结点数 n=notn, +n=notn +no-1=2n+n-1 =2*50+30-1=129 棵二叉树有67个结点,这些结点的度 要么是0,要么是2。这棵二叉树中度为2 的结点有(个 n=n+n2=n2+1+n2=2n2+1=67 故n2=33 28
28 ➢ 已知二叉树中叶子数为50，单分支的结 点数为30，则总结点数 。 ➢一棵二叉树有67个结点，这些结点的度 要么是0，要么是2。这棵二叉树中度为2 的结点有( )个 n=n0+n1+n2=n0+n1+n0 -1=2n0+n1 -1 =2*50+30-1=129 n=n0+n2=n2+1+n2=2n2+1=67 故 n2＝33
性质2:在二叉树的第i层上至多有21个结点 (≥1) 性质3:深度为k的二又树至多有-个结点 29
29 性质3：深度为k的二叉树至多有 2 k −1 个结点。 性质2：在二叉树的第i层上至多有2i-1个结点 (i≥1)
性质4对完全二叉树中编号为i的结点 (1≤≤n,n≥1,m为结点数)有: (1)若过n2即2n,则编号为结点为分支结 点,否则为叶子结点。 (2)着为奇数则每个分支结点都既有左孩子结 点也有右孩子结点;着为周数则编号最大的分支 结点(编号为n2)只有左孩子结点没有右孩子结点 其余分支结点都有左、右孩子结点。 (8)(o①0①1①2 30
30 1 2 4 8 9 5 10 3 6 7 11 12 性 质4 对完全二叉树中编号为 i 的结点 (1≤i≤n,n≥1,n为结点数)有： (1) 若i≤n/2,即2i≤n,则编号为i的结点为分支结 点,否则为叶子结点。 (2) 若n为奇数,则每个分支结点都既有左孩子结 点,也有右孩子结点；若n为偶数,则编号最大的分支 结点(编号为n/2)只有左孩子结点,没有右孩子结点, 其余分支结点都有左、右孩子结点