空二叉樹

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

基本介紹

• 中文名：空二叉樹
• 外文名：empty binary tree
• 解釋：一個結點都沒有的二叉樹
• 歸屬學科：數據結構
• 性質：一種數據結構
• 相關概念：非空二叉樹

概念

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

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

(1)空二叉樹

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

(3)只有左子樹

(4)只有右子樹

(5)完全二叉樹

二叉樹的基本運算

1）創建二叉樹 CreatBTNode(*b,*str)

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

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

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

3）找孩子結點

4）求樹的高度

5）輸出二叉樹

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

二叉樹定義

//二叉樹節點定義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）二叉排序樹

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

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

（3）平衡樹

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

（4）紅黑樹

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