完全二叉樹總結點數與葉結點數關系分析

摘要：該文從兩個角度分析了完全二叉樹的總結點數與葉結點數之間的關系。其一，通過歸納找到總結點數的奇偶性與度為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為空，則它是一棵空樹（1 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.