滿二叉樹

在國際交流場合，包括學(xué)術(shù)會議發(fā)表論文等都應(yīng)該使用美國和國際定義.在國內(nèi)的各種考試場合，比如研究生考試/軟考/計算機(jī)等級考試等，都應(yīng)該使用國內(nèi)教材的定義.在校學(xué)生的校級考根據(jù)所在學(xué)校采用教材情況而定.

又叫Full Binary Tree. 除葉子節(jié)點外，每一層上的所有節(jié)點都有兩個子節(jié)點(最后一層上的無子結(jié)點的結(jié)點為葉子結(jié)點)。也可以這樣理解，除葉子結(jié)點外的所有節(jié)點均有兩個子節(jié)點。節(jié)點數(shù)達(dá)到最大值。所有葉子結(jié)點必須在同一層上.

如果一顆樹深度為d，最大層數(shù)為k

它的葉子數(shù)是: 2^d

第k層的節(jié)點數(shù)是: 2^(k-1)

總節(jié)點數(shù)是: 2^k-1 (2的k次方減一)

總節(jié)點數(shù)一定是奇數(shù)。

定義介紹

美國以及國際上所定義的滿二叉樹 ，即full binary tree,和國內(nèi)的定義不同，美國NIST給出的定義為:A binary tree in which each node has exactly zero or two children. In other words, every node is either a leaf or has two children. For efficiency, any Huffman coding is a full binary tree.

滿二叉樹的任意節(jié)點，要么度為0，要么度為2.換個說法即要么為葉子結(jié)點，要么同時具有左右孩子?；舴蚵鼧涫欠线@種定義的，滿足國際上定義的滿二叉樹，但是不滿足國內(nèi)的定義.

是程序算法中的一種算法模式。

在二叉樹中出現(xiàn)空的子樹（包括樹葉）上增加空的樹葉，使其成為滿二叉樹的二叉樹稱之為擴(kuò)充二叉樹。

完全二叉樹(Complete Binary Tree)

若設(shè)二叉樹的深度為h，除第 h 層外，其它各層 (1~h-1) 的結(jié)點數(shù)都達(dá)到最大個數(shù)，第 h 層所有的結(jié)點都連續(xù)集中在最左邊，這就是完全二叉樹。

完全二叉樹是由滿二叉樹而引出來的。對于深度為K的，有n個結(jié)點的二叉樹，當(dāng)且僅當(dāng)其每一個結(jié)點都與深度為K的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時稱之為完全二叉樹。

一棵二叉樹至多只有最下面的一層上的結(jié)點的度數(shù)可以小于2，并且最下層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹成為完全二叉樹。

1

/ \

2 3

\ /

4 5 是均衡二叉樹，因為它去掉葉結(jié)點及相應(yīng)的樹枝后，

變成了：

1

/ \

2 3 ，這是一個二叉樹。

1

/ \

2 3

而 \ / \ 則不是，因為它去掉葉結(jié)點及相應(yīng)的樹枝后，

4 5 6

/

7

變成了：

1

/ \

2 3

\

4

很顯然，這并不是一個完全二叉樹。