完美二叉樹, 完全二叉樹和完滿二叉樹

樹在資料結構中占有非常重要的地位。本文從樹的基本概念入手，給出完美(Perfect)二叉樹，完全(Complete)二叉樹和完滿(Full)二叉樹的差別。如果學習過二叉樹，但是對這三種二叉樹并沒有深入的了解，或者完全被國産資料結構教科書所誤導(隻聽說過滿二叉樹和完全二叉樹)的朋友不妨花點時間耐着性子将本文仔細閱讀N(>=1)遍。

1. 樹(Tree)的基本概念

1.1 樹的定義

A tree is a (possibly non-linear) data structure made up of nodes or vertices 
and edges without having any cycle. The tree with no nodes is called the null 
or empty tree. A tree that is not empty consists of a root node and potentially 
many levels of additional nodes that form a hierarchy.      

樹是由結點或頂點和邊組成的(可能是非線性的)且不存在着任何環的一種資料結構。沒有結點的樹稱為空(null或empty)樹。一棵非空的樹包括一個根結點，還(很可能)有多個附加結點，所有結點構成一個多級分層結構。

[注：本文将node一律譯為"結點"(而不是"節點")，因為joint或connection是節點，而node是結點。關于"結點"與"節點"請自行搜尋浙江大學陳水福教授的文章--"360度"解讀如何正确應用"結點"與"節點"]

例如： 【圖檔來源： https://upload.wikimedia.org/wikipedia/commons/f/f7/Binary_tree.svg】

A simple unordered tree; in this diagram, the node labeled 7 has two children, 
labeled 2 and 6, and one parent, labeled 2. The root node, at the top, 
has no parent. 上圖是一棵無序的樹示例。在上圖中，标号為7的結點有兩個孩子，分别是标号為2和6的結點。
根結點，在最頂端，它沒有雙親。      

1.2 樹的基本術語

Root	The top node in a tree.	根	樹的頂端結點
Child	A node directly connected to another node when moving away from the Root.	孩子	當遠離根(Root)的時候，直接連接配接到另外一個結點的結點被稱之為孩子(Child);
Parent	The converse notion of a child.	雙親	相應地，另外一個結點稱為孩子(child)的雙親(parent)。
Siblings	A group of nodes with the same parent.	兄弟	具有同一個雙親(Parent)的孩子(Child)之間互稱為兄弟(Sibling)。
Ancestor	A node reachable by repeated proceeding from child to parent.	祖先	結點的祖先(Ancestor)是從根（Root）到該結點所經分支(Branch)上的所有結點。
Descendant	A node reachable by repeated proceeding from parent to child.	子孫	反之，以某結點為根的子樹中的任一結點都稱為該結點的子孫(Ancestor)。
Leaf	A node with no children.	葉子（終端結點）	沒有孩子的結點(也就是度為0的結點)稱為葉子(Leaf)或終端結點。
Branch	A node with at least one child.	分支(非終端結點)	至少有一個孩子的結點稱為分支(Branch)或非終端結點。
Degree	The number of sub trees of a node.	度	結點所擁有的子樹個數稱為結點的度(Degree)。
Edge	The connection between one node and another.	邊	一個結點和另一個結點之間的連接配接被稱之為邊(Edge)。
Path	A sequence of nodes and edges connecting a node with a descendant.	路徑	連接配接結點和其後代的結點之間的(結點,邊)的序列。
Level	The level of a node is defined by ０ + (the number of connections between the node and the root).	層次	結點的層次(Level)從根(Root)開始定義起，根為第0層，根的孩子為第1層。以此類推，若某結點在第i層，那麼其子樹的根就在第i+1層。
Height of node	The height of a node is the number of edges on the longest path between that node and a leaf.	結點的高度	結點的高度是該結點和某個葉子之間存在的最長路徑上的邊的個數。
Height of tree	The height of a tree is the height of its root node.	樹的高度	樹的高度是其根結點的高度。
Depth of node	The depth of a node is the number of edges from the tree's root node to the node.	結點的深度	結點的深度是從樹的根結點到該結點的邊的個數。（注：樹的深度指的是樹中結點的最大層次。）
Forest	A forest is a set of n ≥ 0 disjoint trees.	森林	森林是n(>=0)棵互不相交的樹的集合。

2 二叉樹（Binary Tree)

2.1 什麼是二叉樹（Binary Tree)

每個結點至多擁有兩棵子樹(即二叉樹中不存在度大于2的結點)，并且，二叉樹的子樹有左右之分，其次序不能任意颠倒。

2.2 二叉樹的性質

（1）若二叉樹的層次從0開始，則在二叉樹的第i層至多有2^i個結點(i>=0)。

（2）高度為k的二叉樹最多有2^(k+1) - 1個結點(k>=-1)。 (空樹的高度為-1)

（3）對任何一棵二叉樹，如果其葉子結點(度為0)數為m, 度為2的結點數為n, 則m = n + 1。

2.3 完美二叉樹(Perfect Binary Tree)

A Perfect Binary Tree(PBT) is a tree with all leaf nodes at the same depth. 
All internal nodes have degree 2.      

一個深度為k(>=-1)且有2^(k+1) - 1個結點的二叉樹稱為完美二叉樹。 (注： 國内的資料結構教材大多翻譯為"滿二叉樹")

例如：

2.4 完全二叉樹(Complete Binary Tree)

A Complete Binary Tree （CBT) is a binary tree in which every level, 
except possibly the last, is completely filled, and all nodes 
are as far left as possible.      

換句話說，完全二叉樹從根結點到倒數第二層滿足完美二叉樹，最後一層可以不完全填充，其葉子結點都靠左對齊。

例如：

2.5 完滿二叉樹(Full Binary Tree)

A Full Binary Tree (FBT) is a tree in which every node other than the leaves has two children.      

換句話說，所有非葉子結點的度都是2。（隻要你有孩子，你就必然是有兩個孩子。） 

注：Full Binary Tree又叫做Strictly Binary Tree。

例如：

2.6 完美(Perfect)二叉樹 v.s. 完全(Complete)二叉樹

(1) 一棵完美(Perfect)二叉樹看起來是這個樣兒的， 【圖2.6.1】

（2） 那麼，将編号為15, 14, ..., 9的葉子結點從右到左依次拿掉或者拿掉部分，則是一棵完全(Complete)二叉樹,

例如，将上圖中的編号為15, 14, 13, 12, 11葉子結點都拿掉(從右到左的順序)， 【圖2.6.2】

（3） 下圖就不是一棵完全(Complete)二叉樹，【圖2.6.3】，

如果将編号11(K)結點從編号6(E)的左兒子位置移動到編号5(E)的右兒子位置，則變成一棵完全(Complete)二叉樹。

注： 圖2.6.1， 2.6.2和2.6.3均來自：http://alrightchiu.github.io/SecondRound/binary-tree-introjian-jie.html， 但是，其将Full Binary Tree當做就是Perfect Binary Tree, 我認為是不正确的，特此說明。

特别說明： 其實，了解完全(Complete)二叉樹可以借助于棧(stack)的思想。 例如，把圖2.6.1中的完美(Perfect)二叉樹的所有結點按照編号1, 2, 3, ..., 15依次入棧(push)。 那麼，對棧的每一次出棧(pop)操作後，棧裡儲存的結點集對應到圖2.6.1上去都是一棵完全(Complete)二叉樹。

2.7 完全(Complete)二叉樹 v.s. 完滿(Full)二叉樹

【截圖來源：http://courses.cs.vt.edu/~cs3114/Fall09/wmcquain/Notes/T03a.BinaryTreeTheorems.pdf】

2.8 完滿(Full)二叉樹 v.s. 完全(Complete)二叉樹 v.s. 完美(Perfect)二叉樹

【圖檔來源： http://www.csie.ntnu.edu.tw/~u91029/BinaryTree2.png】

3. 總結 (下表參考來源)

完美二叉樹	Perfect Binary Tree	Every node except the leaf nodes have two children and every level (last level too) is completely filled. 除了葉子結點之外的每一個結點都有兩個孩子，每一層(當然包含最後一層)都被完全填充。
完全二叉樹	Complete Binary Tree	Every level except the last level is completely filled and all the nodes are left justified. 除了最後一層之外的其他每一層都被完全填充，并且所有結點都保持向左對齊。
完滿二叉樹	Full/Strictly Binary Tree	Every node except the leaf nodes have two children. 除了葉子結點之外的每一個結點都有兩個孩子結點。

• 完美(Perfect)二叉樹一定是完全(Complete)二叉樹，但完全(Complete)二叉樹不一定是完美(Perfect)二叉樹。
• 完美(Perfect)二叉樹一定是完滿(Full)二叉樹，但完滿(Full)二叉樹不一定是完美(Perfect)二叉樹。
• 完全(Complete)二叉樹可能是完滿(Full)二叉樹，完滿(Full)二叉樹也可能是完全(Complete)二叉樹。
• 既是完全(Complete)二叉樹又是完滿(Full)二叉樹也不一定就是完美(Perfect)二叉樹。