二叉樹(shù)（Binary tree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類(lèi)型。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式，即使是一般的樹(shù)也能簡(jiǎn)單地轉(zhuǎn)換為二叉樹(shù)，而且二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。二叉樹(shù)特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分。
二叉樹(shù)是n個(gè)有限元素的集合，該集合或者為空、或者由一個(gè)稱(chēng)為根（root）的元素及兩個(gè)不相交的、被分別稱(chēng)為左子樹(shù)和右子樹(shù)的二叉樹(shù)組成，是有序樹(shù)。當(dāng)集合為空時(shí)，稱(chēng)該二叉樹(shù)為空二叉樹(shù)。在二叉樹(shù)中，一個(gè)元素也稱(chēng)作一個(gè)節(jié)點(diǎn)。
定義
二叉樹(shù)（binary tree）是指樹(shù)中節(jié)點(diǎn)的度不大于2的有序樹(shù)，它是一種最簡(jiǎn)單且最重要的樹(shù)。二叉樹(shù)的遞歸定義為：二叉樹(shù)是一棵空樹(shù)，或者是一棵由一個(gè)根節(jié)點(diǎn)和兩棵互不相交的，分別稱(chēng)作根的左子樹(shù)和右子樹(shù)組成的非空樹(shù)；左子樹(shù)和右子樹(shù)又同樣都是二叉樹(shù)。
基本概念
二叉樹(shù)是遞歸定義的，其結(jié)點(diǎn)有左右子樹(shù)之分，邏輯上二叉樹(shù)有五種基本形態(tài)：
(1)空二叉樹(shù)
(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹(shù)
(3)只有左子樹(shù)
(4)只有右子樹(shù)
(5)完全二叉樹(shù)
注意：盡管二叉樹(shù)與樹(shù)有許多相似之處，但二叉樹(shù)不是樹(shù)的特殊情形。
類(lèi)型
(1)完全二叉樹(shù)——若設(shè)二叉樹(shù)的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹(shù)。
(2)滿(mǎn)二叉樹(shù)——除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹(shù)。
(3)平衡二叉樹(shù)——平衡二叉樹(shù)又被稱(chēng)為AVL樹(shù)（區(qū)別于AVL算法），它是一棵二叉排序樹(shù)，且具有以下性質(zhì)：它是一棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)。
完全二叉樹(shù)的特點(diǎn)是葉子節(jié)點(diǎn)只可能出現(xiàn)在層序最大的兩層上，并且某個(gè)節(jié)點(diǎn)的左分支下子孫的最大層序與右分支下子孫的最大層序相等或大1。
辨析
二叉樹(shù)不是樹(shù)的一種特殊情形，盡管其與樹(shù)有許多相似之處，但樹(shù)和二叉樹(shù)有兩個(gè)主要差別：
1. 樹(shù)中結(jié)點(diǎn)的最大度數(shù)沒(méi)有限制，而二叉樹(shù)結(jié)點(diǎn)的最大度數(shù)為2；
2. 樹(shù)的結(jié)點(diǎn)無(wú)左、右之分，而二叉樹(shù)的結(jié)點(diǎn)有左、右之分。
相關(guān)術(shù)語(yǔ)
①結(jié)點(diǎn)：包含一個(gè)數(shù)據(jù)元素及若干指向子樹(shù)分支的信息。
②結(jié)點(diǎn)的度：一個(gè)結(jié)點(diǎn)擁有子樹(shù)的數(shù)目稱(chēng)為結(jié)點(diǎn)的度。
③葉子結(jié)點(diǎn)：也稱(chēng)為終端結(jié)點(diǎn)，沒(méi)有子樹(shù)的結(jié)點(diǎn)或者度為零的結(jié)點(diǎn)。
④分支結(jié)點(diǎn)：也稱(chēng)為非終端結(jié)點(diǎn)，度不為零的結(jié)點(diǎn)稱(chēng)為非終端結(jié)點(diǎn)。
⑤樹(shù)的度：樹(shù)中所有結(jié)點(diǎn)的度的最大值。
⑥結(jié)點(diǎn)的層次：從根結(jié)點(diǎn)開(kāi)始，假設(shè)根結(jié)點(diǎn)為第1層，根結(jié)點(diǎn)的子節(jié)點(diǎn)為第2層，依此類(lèi)推，如果某一個(gè)結(jié)點(diǎn)位于第L層，則其子節(jié)點(diǎn)位于第L+1層。
⑦樹(shù)的深度：也稱(chēng)為樹(shù)的高度，樹(shù)中所有結(jié)點(diǎn)的層次最大值稱(chēng)為樹(shù)的深度。
⑧有序樹(shù)：如果樹(shù)中各棵子樹(shù)的次序是有先后次序，則稱(chēng)該樹(shù)為有序樹(shù)。
⑨無(wú)序樹(shù)：如果樹(shù)中各棵子樹(shù)的次序沒(méi)有先后次序，則稱(chēng)該樹(shù)為無(wú)序樹(shù)。
⑩森林：由m（m≥0）棵互不相交的樹(shù)構(gòu)成一片森林。如果把一棵非空的樹(shù)的根結(jié)點(diǎn)刪除，則該樹(shù)就變成了一片森林，森林中的樹(shù)由原來(lái)根結(jié)點(diǎn)的各棵子樹(shù)構(gòu)成。
性質(zhì)
(1) 在非空二叉樹(shù)中，第i層的結(jié)點(diǎn)總數(shù)不超過(guò),i>=1；
(2) 深度為h的二叉樹(shù)最多有個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)；
(3) 對(duì)于任意一棵二叉樹(shù)，如果其葉結(jié)點(diǎn)數(shù)為n0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為n2，則n0=n2+1；
(4) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為（注：[ ]表示向下取整）
(5)有N個(gè)結(jié)點(diǎn)的完全二叉樹(shù)各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：
若I為結(jié)點(diǎn)編號(hào)則 如果I>1，則其父結(jié)點(diǎn)的編號(hào)為I/2；
如果2I<=N，則其左孩子（即左子樹(shù)的根結(jié)點(diǎn)）的編號(hào)為2I；若2*I>N，則無(wú)左孩子；
如果2I+1<=N，則其右孩子的結(jié)點(diǎn)編號(hào)為2I+1；若2*I+1>N，則無(wú)右孩子。
(6)給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹(shù)。
h(N)為卡特蘭數(shù)的第N項(xiàng)。h(n)=C(2*n，n)/(n+1)。
(7)設(shè)有i個(gè)枝點(diǎn)，I為所有枝點(diǎn)的道路長(zhǎng)度總和，J為葉的道路長(zhǎng)度總和J=I+2i
遍歷
遍歷是對(duì)樹(shù)的一種最基本的運(yùn)算，所謂遍歷二叉樹(shù)，就是按一定的規(guī)則和順序走遍二叉樹(shù)的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問(wèn)一次，而且只被訪問(wèn)一次。由于二叉樹(shù)是非線性結(jié)構(gòu)，因此，樹(shù)的遍歷實(shí)質(zhì)上是將二叉樹(shù)的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來(lái)表示。
設(shè)L、D、R分別表示遍歷左子樹(shù)、訪問(wèn)根結(jié)點(diǎn)和遍歷右子樹(shù)，則對(duì)一棵二叉樹(shù)的遍歷有三種情況：DLR（稱(chēng)為先根次序遍歷），LDR（稱(chēng)為中根次序遍歷），LRD （稱(chēng)為后根次序遍歷）。
先序遍歷
首先訪問(wèn)根，再先序遍歷左（右）子樹(shù)，最后先序遍歷右（左）子樹(shù)，c語(yǔ)言代碼如下：
中序遍歷
首先中序遍歷左（右）子樹(shù)，再訪問(wèn)根，最后中序遍歷右（左）子樹(shù)，C語(yǔ)言代碼如下
后序遍歷
首先后序遍歷左（右）子樹(shù)，再后序遍歷右（左）子樹(shù)，最后訪問(wèn)根，C語(yǔ)言代碼如下
層次遍歷
即按照層次訪問(wèn)，通常用隊(duì)列來(lái)做。訪問(wèn)根，訪問(wèn)子女，再訪問(wèn)子女的子女（越往后的層次越低）（兩個(gè)子女的級(jí)別相同）
線索
線索二叉樹(shù)(保留遍歷時(shí)結(jié)點(diǎn)在任一序列的前驅(qū)和后繼的信息)：若結(jié)點(diǎn)有左子樹(shù)，則其lchild域指示其左孩子，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹(shù)，則其rchild域指示其右孩子，否則令rchild指示其后繼。還需在結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域LTag和RTag。LTag=0時(shí)，lchild域指示結(jié)點(diǎn)的左孩子，LTag=1時(shí)，lchild域指示結(jié)點(diǎn)的前驅(qū)；RTag=0時(shí)，rchild域指示結(jié)點(diǎn)的右孩子，RTag=1時(shí)，rchild域指示結(jié)點(diǎn)的后繼。以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉線索鏈表，鏈表作為二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)，叫做其中指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索，加上線索的二叉樹(shù)稱(chēng)為線索二叉樹(shù)。對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程叫做線索化。若對(duì)二叉樹(shù)進(jìn)行中序遍歷，則所得的線索二叉樹(shù)稱(chēng)為中序線索二叉樹(shù)，線索鏈表稱(chēng)為為中序線索鏈表。線索二叉樹(shù)是一種物理結(jié)構(gòu)。在中序線索樹(shù)找結(jié)點(diǎn)后繼的規(guī)律是：若其右標(biāo)志為1，則右鏈為線索，指示其后繼，否則遍歷其右子樹(shù)時(shí)訪問(wèn)的第一個(gè)結(jié)點(diǎn)（右子樹(shù)最左下的結(jié)點(diǎn)）為其后繼；找結(jié)點(diǎn)前驅(qū)的規(guī)律是：若其左標(biāo)志為1，則左鏈為線索，指示其前驅(qū)，否則遍歷左子樹(shù)時(shí)最后訪問(wèn)的一個(gè)結(jié)點(diǎn)（左子樹(shù)中最右下的結(jié)點(diǎn)）為其前驅(qū)。
在后序線索樹(shù)中找到結(jié)點(diǎn)的后繼分三種情況：
若結(jié)點(diǎn)是二叉樹(shù)的根，則其后繼為空；若結(jié)點(diǎn)是其雙親的右孩子，或是其雙親的左孩子且其雙親沒(méi)有右子樹(shù)，則其后繼即為雙親結(jié)點(diǎn)；若結(jié)點(diǎn)是其雙親的左孩子，且其雙親有右子樹(shù)，則其后繼為雙親右子樹(shù)上按后序遍歷列出的第一個(gè)結(jié)點(diǎn)。
示例
范例二叉樹(shù)：
A
B C
D E
此樹(shù)的順序結(jié)構(gòu)為：ABCDE
參考資料 >
二叉樹(shù)詳解 - 那些年的代碼 - 博客園.博客園.2021-11-03