二叉树
在電腦科學中，二元樹（）是每個節點最多只有兩個分支（即不存在分支度大於2的節點）的樹結構。通常分支被稱作“左子樹”或“右子樹”。二元樹的分支具有左右次序，不能随意顛倒。
二元樹的第formula_1層至多擁有formula_2個節點；深度為formula_3的二元樹至多總共有formula_4個節點（定义根节点所在深度 formula_5），而總計擁有節點數符合的，稱為「滿二元樹」；深度為formula_3有formula_7個節點的二元樹，當且僅當其中的每一節點，都可以和深度formula_3的滿二元樹，序號1到formula_7的節點一對一對應時，稱為完全二元樹。對任何一棵非空的二元樹formula_10，如果其葉片（終端節點）數為formula_11，分支度為2的節點數為formula_12，則formula_13。
與普通樹不同，普通樹的節點個數至少為1，而二元樹的節點個數可以為0；普通樹節點的最大分支度沒有限制，而二元樹節點的最大分支度為2；普通樹的節點無左、右次序之分，而二元樹的節點有左、右次序之分。
二元樹通常作為資料結構應用，典型用法是對節點定義一個標記函數，將一些值與每個節點相關聯。這樣標記的二元樹就可以實現二元搜尋樹和二元堆積，並應用於高效率的搜索和排序。
二元樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二元樹還要滿足根節點的度不大於2。有了根節點之後，每個頂點定義了唯一的父節點，和最多2個子節點。然而，沒有足夠的資訊來區分左節點和右節點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。
二元樹是一個有根树，並且每個節點最多有2個子節點。非空的二叉樹，若樹葉總數為 n0，分支度為2的總數為 n2，則 n0 = n2 + 1。
一棵深度為k，且有formula_14個節點的二元樹，稱為完美二元樹（Perfect Binary Tree）。這種樹的特點是每一層上的節點數都是最大節點數。 对于一棵深度为 formula_3 的完美二叉树：
在一颗二元樹中，若除最後一層外的其餘層都是滿的，並且最後一層要么是满的，要么在右邊缺少連續若干節點，則此二元樹為完全二元樹（Complete Binary Tree）。具有n個節點的完全二元樹的深度為formula_20。深度為k的完全二元樹，至少有formula_21個節點，至多有formula_14個節點。
在程式設計語言中能用多種方法來構造二元樹。
二元樹可以用陣列或鏈結串列來存儲，若是滿二元樹就能緊湊排列而不浪費空間。如果某個節點的索引為i，（假設根節點的索引為0）則在它左子節點的索引會是formula_23，以及右子節點會是formula_24；而它的父節點（如果有）索引則為"formula_25"。這種方法更有利於緊湊存儲和更好的訪問的局部性，特別是在前序遍歷中。然而，它需要連續的存儲空間，這樣在存儲高度為"h"的"n"個節點所組成的一般樹時，將浪費很多空間。在最糟糕的情況下，如果深度為h的二元樹其每個節點都只有右孩子，則該存儲結構需要佔用formula_26的空間，實際上卻有h個節點，浪費了不少空間，是順序存儲結構的一大缺點。
/* 二叉树的顺序存储表示 */
/* 二元樹的順序存儲的基本操作(23個)*/ void InitBiTree(SqBiTree T) －－－（SqBiTree & T）
void CreateBiTree(SqBiTree T)  int l;  InitBiTree(T); /* 構造[空二元樹]T */  for(i=1;i記錄或記憶體位址指標的程式設計語言中，二叉樹通常用樹結點結構來存儲。有時也包含指向唯一的父節點的指標。如果一個結點的子結點個數小於2，一些子結點指針可能為空值，或者為特殊的哨兵結點。  使用鏈表能避免順序儲存浪費空間的問題，演算法和結構相對簡單，但使用二叉鏈表，由於缺乏父鏈的指引，在找回父節點時需要重新掃描樹得知父節點的節點位址。
/* 二叉樹的二叉鏈表存儲表示 */
/* 二叉樹的二叉鏈表存儲的基本操作(22個) */
改進於二叉鏈表，增加父節點的指引，能更好地實現節點間的訪問，不過演算法相對複雜。 當二叉樹用三叉鏈表表示時，有N個結點，就會有N+2個空指針。
/* 二叉樹的三叉鏈表存儲表示 */
/* 二叉樹的三叉鏈表存儲的基本操作(21個) */
我們經常希望訪問樹中的每一個結點並且查看它的值。有很多常見的順序來訪問所有的結點，而且每一種都有有用的性質。
在深度優先順序中，我們希望從根結點訪問最遠的結點。和圖的深度優先搜索不同的是，不需記住訪問過的每一個結點，因為樹中不會有環。前序，中序和後序遍歷都是深度優先遍歷的特例。
遍歷二叉樹：L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹，則先(根)序遍歷二叉樹的順序是DLR，中(根)序遍歷二叉樹的順序是LDR，後(根)序遍歷二叉樹的順序是LRD。還有按層遍歷二叉樹。這些方法的時間複雜度都是O(n)，n為結點個數。
如果T2是由有序樹T轉換而來的二叉樹，那麼T中結點的前序就是T2中結點的前序，T中結點的後序就是T2中結點的中序。任何一棵二叉樹的葉結點在先序、中序和後序遍歷中的相對次序不發改變。設n,m為一棵二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是n在m的左方。前序序列和中序序列相同的二叉樹為空樹或任一結點均無左孩子的非空二叉樹；中序序列和後序序列相同的二叉樹為空樹或任一結點均無右孩子的非空二叉樹；前序序列和後序序列相同的二叉樹為空樹或僅有一個結點的二叉樹。
假設我們有一個包含值的codice_1和指向兩個子結點的codice_2和codice_3的樹結點結構。我們可以寫出這樣的過程：
這樣會用前序打印出樹中的值。在前序，每個結點在訪問它的子結點之前訪問。類似地，如果打印語句在最後，每個結點在訪問他的子節點之後訪問，樹中的值會用後序來打印。在這兩種情況中，左子樹中的值比右子樹中得值先打印。
最後，上面的中序遍歷，每個結點在訪問左子樹和右子樹之間訪問。這在遍歷二叉搜尋樹時很常用，因為它能用遞增的順序來遍歷所有的值。
為什麼呢？如果"n"是二叉搜尋樹的結點，那麼"n"的左子樹的所有結點的值都比n的值要小，而且"n"的右子樹的所有節點的值都比n的值要大。因此，如果我們順序遍歷左子樹，然後訪問"n"，然後順序遍歷右子樹。我們就已經循序存取了整個樹。
后序遍历伪代码如下：
以上的遞迴演算法使用與樹的高度成比例的棧空間。如果我們在每個結點中存儲指向父結點的指標，那樣可以使用反覆運算演算法，只使用常數空間實現所有這些遍歷。然而，指向父結點的指標佔用更多的空間。這只在需要指向父節點的指標或棧空間有限時才使用。例如， 這是一個中序遍歷的反覆運算演算法：
和深度優先遍歷不同，廣度優先遍歷會先訪問離根節點最近的節點。二叉樹的廣度優先遍歷又稱按層次遍歷。演算法借助佇列實現。
一般有序樹可映射为二叉樹，但反之未必成立。
n叉樹轉換為二叉樹的方法：二叉樹中結點x的左子結點為n叉樹中結點x的左子結點；二叉樹中結點x的右子結點為n叉樹中結點x的第一個右邊的同級結點y。
二叉树当且仅当根节点没有右子结点时可转换为n叉树。 例如，在左邊的樹中，A有6個子結點{B,C,D,E,F,G}。它能被轉換成右邊的二叉樹。樹的二叉鏈表標記法（孩子兄弟標記法）是樹和二叉樹轉換的媒介。
/* 樹的二叉鏈表(孩子—兄弟)存儲表示 */  /* 樹的二叉鏈表(孩子—兄弟)存儲的基本操作(17個) */
線索二叉樹（，保留遍歷時結點在任一序列的前驅和後繼的資訊）：若結點有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右孩子，否則令rchild指示其後繼。還需在結點結構中增加兩個標誌域LTag和RTag。LTag=0時，lchild域指示結點的左孩子，LTag=1時，lchild域指示結點的前驅；RTag=0時，rchild域指示結點的右孩子，RTag=1時，rchild域指示結點的後繼。以這種結點結構構成的二叉鏈表作為二叉樹的存儲結構，叫做線索鏈表，其中指向結點前驅和後繼的指標叫做線索，加上線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。若對二叉樹進行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索鏈表稱為為中序線索鏈表。線索二叉樹是一種物理結構。 在中序線索樹找結點後繼的規律是：若其右標誌為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標誌為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。 在後序線索樹中找到結點的後繼分三種情況：
二叉樹的二叉線索存儲表示：在線索鏈表上添加一個頭結點，並令其lchild域的指標指向二叉樹的根結點，其rchild域的指標指向中序遍歷時訪問的最後一個結點。令二叉樹中序序列中的第一個結點的lchild域指標和最後一個結點的rchild域的指標均指向頭結點，這樣就建立了一個雙向線索鏈表。二叉樹常採用二叉鏈表方式存儲。
/* 二叉樹的二叉線索存儲的基本操作 */