学文网摘要：该文从两个角度分析了完全二叉树的总结点数与叶结点数之间的关系。其一，通过归纳找到总结点数的奇偶性与度为1的结点个数之间的关系，进而导出总结点数与叶结点数的关系；其二，由最后一个结点的父结点为倒数第一个分支结点的事实，找到总结点数与叶结点数的关系。这种多角度的分析有利于学生对此数据结构的深入理解。
关键词：数据结构；树；二叉树；完全二叉树
中***分类号：TP311文献标识码：A文章编号：1009-3044(2008)34-1569-02
Complete Binary Tree Nodes and Leaves Number Relation
LIU Song, LAN Ying
(College of Computer Science and Technology, Jilin Normal University, Siping 136000, China)
Abstract: This paper analyzed the relation between the complete binary tree nodes and the leaves number by two ways. First, it induced the relation between the odevity of complete binary tree nodes and the number of one degree nodes, then come to the conclusion. Second, through the fact that the parent of the last node is the last branch node, the paper got the same conclusion. Analyzing by two ways is helpful for students to understand complete binary tree.
Key words: Data Structure; Tree; Binary Tree; Complete Binary Tree
1 引言
1.1 树的定义及几个基本术语[1]
树（tree）是n（n≥0）个结点的有限集合T，如果T为空，则它是一棵空树（null tree），否则：
1) T中有一个特别标出的称为根（root）的结点；
2) 除根结点之外，T中其余结点被分成m个（m≥0）互不相交的非空集合T1，T2，…，Tm，其中每个集合本身又都是树。树T1，T2，…，Tm称为T的根的子树（subtree）。
几个基本术语：
度数（degree），一个结点的子树的个数。
树叶（leaf），没有子树的结点称为树叶或终端结点。
分支结点（branch node），非终端结点。
子女（child）或儿子（son），一个结点的子树之根是该结点的子女（或儿子）。
父母（parent），若结点s是结点p的儿子，则称p是s的父母或父亲。
1.2 二叉树的递归定义[1]
二叉树由结点的有限集合构成，这个有限集合或者为空集，或者由一个根节点及两棵不相交的分别称为这个根的左子树和右子树的二叉树构成。
1.3 完全二叉树的定义及性质
完全二叉树是一种特殊的二叉树，它除最后一层外每一层上的结点数均达到最大值，在最后一层只缺少右边的若干结点[2]。
如果对一棵有n个结点的完全二叉树的结点，按层次次序编号（每层从左至右），则对任一结点i（1≤i≤n），下述结论成立：
1) 若i=1，则结点i为二叉树的根节点；若i>1，则结点[i/2]为其父母节点。
2) 若2i>n，则结点i无左子女；否则结点2i为结点i的左子女。
3) 若2i+1>n，则结点i无右子女；否则结点2i+1为结点i的右子女。[1]
完全二叉树的总结点数N与叶结点数n0存在一定的关系，下面从两个角度加以分析：
2 问题分析
思路1：先用归纳的方法找出完全二叉树中度为1的结点个数n1与总结点数N的关系。下面给出结点数N＝1，2，3，4…的完全二叉树，如***1。
通过观察不难发现度为1的结点个数n1＝0，1，0，1…即：
当N为奇数时n1=0；当N为偶数时n1=1。 (1)
一般地，二叉树总结点数N可以表示为：
N＝n0＋n1＋n2（ni表示度为i的结点个数）(2)
而N＝分支数＋1（因为对于一棵树，除根结点外，每个结点上方均有一个分支与之一一对应）。在二叉树中，分支数＝0×n0＋1×n1＋2×n2，故
N＝(0×n0＋1×n1＋2×n2)+1 (3)
由(2)(3)式，可得：
n0＝n2＋1 (4)
由(2)(4)式，可得：
N＝n0＋n1＋(n0－1) (5)
综合(1)(5)，得如下结论：
当N为奇数时，N奇＝n0＋0＋(n0－1)，n0＝(N奇＋1)/2；
当N为偶数时，N偶＝n0＋1＋(n0－1)，n0＝N偶/2。
思路2：将完全二叉树的结点按层序（从上到下，从左到右）从1开始编号，则N个结点的完全二叉树中，最后一个结点的编号为N。根据完全二叉树的性质，编号为N的结点的父结点编号为[N/2]([N/2]表示的是N/2的整数部分，如***2所示。
叶结点个数为总结点数减去分支结点个数，而最后结点的父结点为最末一个分支结点，所以叶结点个数n0＝N－[N/2]。
3 两种结论的一致性
上述两种思路所得结论形式上有差别，下面分两种情况讨论它们的一致性：
第一种情况，当N为奇数时，[N/2]＝(N－1)/2。所以，由思路二所得结论n0＝N－[N/2]就可以表示为n0＝N－(N－1)/2=(N＋1)/2；
第二种情况，当N为偶数时，[N/2]＝N/2。所以，由思路二所得结论n0＝N－[N/2]就可以表示为n0＝N－N/2=N/2。
综上，思路2所得结论与思路一所得结论是一致的。
4 总结
根据上述两种思路得到本质上相同的两条结论：其一，n0＝(N奇＋1)/2或n0＝N偶/2；其二，n0＝N－[N/2]。通过如上分析可以加深对数据结构完全二叉树乃至二叉树、树的性质的理解与认识。这亦是计算机教学中一题多解的一个很好实例。
参考文献：
[1] 熊岳山,刘越. 数据结构与算法[M].北京:电子工业出版社,2007:144-148.
[2] 全国计算机等级考试教材编写组.全国计算机等级考试教程二级公共基础[M].北京:人民邮电出版社,2007:22-26.
转载请注明出处学文网 » 完全二叉树总结点数与叶结点数关系分析