二叉樹(Binary Tree)的定義和基本術語

定義：是n（n≥0）個結點的有限集合，由一個根結點

以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。

邏輯結構：  一對二（1：2）

基本特征  ① 每個結點最多只有兩棵子樹（不存在度大于2的結點）；

          ② 左子樹和右子樹次序不能顛倒（有序樹）。

樹的度：樹中結點的度的最大值.二叉樹中結點度的最大值為2。

結點的祖先：從根到該結點所經分支上的所有結點。

結點的子孫：以該結點為根的子樹中的任一結點。

二叉樹的邏輯結構：由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。樹中任一結點都可以有0-2個直接后繼結點但至多只能有一個直接前趨結點。

二叉樹的層數：根所在的層次為1，其孩子的層次為2，依次類推。

二叉樹的深度：樹中結點的最大層次。

有序樹：樹中結點的各子樹從左至右有次序（最左邊為第一個孩子）

無序樹：樹中結點的各子樹無次序。

基本特征:

① 每個結點最多只有兩棵子樹（不存在度大于2的結點）；

② 左子樹和右子樹次序不能顛倒。

二叉樹的性質：

性質1:在二叉樹的第i層上至多有2i-1個結點

性質2:深度為k的二叉樹至多有2k-1個結點

性質3:對于任何一棵二叉樹，若2度的結點數有n2個，則葉子數n0必定為n2＋1（即n0=n2+1）

性質4:具有n個結點的完全二叉樹的深度必為log2n＋1

性質5:對完全二叉樹，若從上至下、從左至右編號，則編號為i的結點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2。

特殊形態的二叉樹

滿二叉樹：一棵深度為k且有2k -1個結點的二叉樹。（特點：每層都“充滿”了結點）

完全二叉樹：深度為k的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1至n的結點一一對應

滿二叉樹和完全二叉樹的區別

滿二叉樹是葉子一個也不少的樹，而完全二叉樹雖然前n-1層是滿的，但最底層卻允許在右邊缺少連續若干個結點。滿二叉樹是完全二叉樹的一個特例。

滿二叉樹的特點：

◆ 基本特點是每一層上的結點數總是最大結點數。

◆ 滿二叉樹的所有的支結點都有左、右子樹。

◆ 可對滿二叉樹的結點進行連續編號，若規定從根結點開始，按“自上而下、自左至右”的原則進行。

完全二叉樹(Complete Binary Tree)：如果深度為k，由n個結點的二叉樹，當且僅當其每一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應，該二叉樹稱為完全二叉樹。

或深度為k的滿二叉樹中編號從1到n的前n個結點構成了一棵深度為k的完全二叉樹。

其中  2k-1≦ n≦2k-1。

完全二叉樹是滿二叉樹的一部分，而滿二叉樹是完全二叉樹的特例。

完全二叉樹的特點：若完全二叉樹的深度為k，則所有的葉子結點都出現在第k層或k-1層。對于任一結點，如果其右子樹的最大層次為l，則其左子樹的最大層次為l或l+1。

二叉樹遍歷

遍歷：順著某一條搜索路徑巡訪二叉樹中的結點，使得每個結點均被訪問一次，而且僅被訪問一次。