二叉樹是n（n≥0）個結點的有限集合。n=0的樹稱為空二叉樹。n>0的二叉樹由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。1

概念二叉樹是n（n≥0）個結點的有限集合。n=0的樹稱為空二叉樹。n>0的二叉樹由一個根結點以及兩棵互不相交的、分別稱為左子樹和右子樹的二叉樹組成。1

二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：1

(1)空二叉樹2

(2)只有一個根結點的二叉樹2

(3)只有左子樹2

(4)只有右子樹2

(5)完全二叉樹1

二叉樹的基本運算1）創建二叉樹 CreatBTNode(*b,*str)1

2）查找結點 FindNode(*b,x)3

采用遞歸算法在二叉樹b中查找值為x的結點，找到后返回其指針，否則返回NULL。2

在查找前，通常先判斷二叉樹是否為空，若為空，則返回查找失敗。2

3）找孩子結點1

4）求樹的高度3

5）輸出二叉樹1

通常也需判斷二叉樹是否為空。2

二叉樹定義//二叉樹節點定義struct BinaryTreeNode{ int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight;};構造空樹//清空或銷毀二叉樹void ClearTree(PTree *T){ T->n = NULL;}如何判斷TreeEmpty(PTree *T){ /* 初始條件：樹T存在。操作結果：若T為空樹，則返回TRUE，否則返回FALSE */ return T->n==NULL;} 二叉樹拓展（1）線索二叉樹

在節點空指針域存放前驅和后繼節點的指針，加上線索標志域區分是線索指針還是child指針；建立線索二叉樹，實質上就是遍歷一顆二叉樹，在相應的指針域進行操作。2

（2）二叉排序樹

（3）最優二叉樹（哈夫曼樹）2

對于一組有確定權值的葉子節點，構造的具有最小帶權路徑長度的二叉樹（典型應用：哈夫曼編碼）3

（3）平衡樹

它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，并且左右兩個子樹都是一棵平衡二叉樹。（防止退化為鏈表，提高搜索效率）3

（4）紅黑樹

紅黑樹是平衡二叉樹的一種；它有很好的性質，樹中的結點都是有序的，而且因為它本身就是平衡的，所以查找也不會出現非常惡劣的情況，基于二叉樹的操作的時間復雜度是O(log(N))。Linux內核在管理vm_area_struct時就是采用了紅黑樹來維護內存塊的。2

本詞條內容貢獻者為:

尚軼倫 - 副教授 - 同濟大學數學科學學院