[科普中國]-空二叉樹

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

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

二叉樹是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分，邏輯上二叉樹有五種基本形態(tài)：1

(1)空二叉樹2

(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹2

(3)只有左子樹2

(4)只有右子樹2

(5)完全二叉樹1

二叉樹的基本運(yùn)算1）創(chuàng)建二叉樹 CreatBTNode(*b,*str)1

2）查找結(jié)點(diǎn) FindNode(*b,x)3

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

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

3）找孩子結(jié)點(diǎn)1

4）求樹的高度3

5）輸出二叉樹1

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

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

在節(jié)點(diǎn)空指針域存放前驅(qū)和后繼節(jié)點(diǎn)的指針，加上線索標(biāo)志域區(qū)分是線索指針還是child指針；建立線索二叉樹，實(shí)質(zhì)上就是遍歷一顆二叉樹，在相應(yīng)的指針域進(jìn)行操作。2

（2）二叉排序樹

（3）最優(yōu)二叉樹（哈夫曼樹）2

對(duì)于一組有確定權(quán)值的葉子節(jié)點(diǎn)，構(gòu)造的具有最小帶權(quán)路徑長度的二叉樹（典型應(yīng)用：哈夫曼編碼）3

（3）平衡樹

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

（4）紅黑樹

紅黑樹是平衡二叉樹的一種；它有很好的性質(zhì)，樹中的結(jié)點(diǎn)都是有序的，而且因?yàn)樗旧砭褪瞧胶獾?，所以查找也不?huì)出現(xiàn)非常惡劣的情況，基于二叉樹的操作的時(shí)間復(fù)雜度是O(log(N))。Linux內(nèi)核在管理vm_area_struct時(shí)就是采用了紅黑樹來維護(hù)內(nèi)存塊的。2

本詞條內(nèi)容貢獻(xiàn)者為:

尚軼倫 - 副教授 - 同濟(jì)大學(xué)數(shù)學(xué)科學(xué)學(xué)院