二叉樹是最常用的數(shù)據(jù)結(jié)構(gòu)之一晕翠，筆者過去一直將關(guān)注點放在復(fù)雜的樹結(jié)構(gòu)（例如紅黑樹蚪战，自平衡樹）棘利，認為那些才是樹的重要應(yīng)用拧粪，但當(dāng)重新由基本看起修陡，才發(fā)現(xiàn)樹的基本定中就隱藏著樹這一結(jié)構(gòu)的精髓。盡管是些淺薄蠢笨的理解和推演可霎，但筆者還是滿懷興奮的想要將它記錄下來濒析。
一、二叉樹的定義
二叉樹的定義不用多說啥纸，很多書本上都有明確的定義号杏，但有些細節(jié)是筆者過去所沒有注意的，先給出殷人昆教授對于二叉樹的基本定義——
二叉樹是結(jié)點的一個有限集合斯棒，該集合或者為空盾致，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成荣暮。
可以看出二叉樹的定義是遞歸的庭惜，根結(jié)點的子樹仍然是二叉樹，到達空子樹時遞歸定義結(jié)束穗酥。
一般來說护赊，關(guān)于樹的術(shù)語對于二叉樹都是適用的，但應(yīng)該明確的是二叉樹不是樹砾跃，理由如下：
- 樹在圖論中被視為用n-1條邊連接n個結(jié)點的的特殊的圖骏啰。圖的頂點結(jié)合非空，故樹的頂點非空抽高。圖論中另外定義了N叉樹判耕，它可以是空樹，二叉樹屬于N叉樹翘骂。
- 非空二叉樹有根壁熄，根結(jié)點的子樹有左右之分，次序不能顛倒碳竟；若其中一棵子樹為空草丧，則另一棵子樹也必須保持左右之分。樹可以沒有根（自由樹）莹桅；即使有根昌执，其子樹也沒有這種區(qū)分。
那么，這就出現(xiàn)一個問題——二叉樹的葉結(jié)點無子女仙蚜，是否可稱它為無子樹此洲？
根據(jù)定義，應(yīng)該是不能的委粉，因為可認為葉子點的左右子樹為空子樹呜师。
雖然認識這一區(qū)別的目的并非應(yīng)試，但筆者還是提一句：個人認為在一般的測試中未必會考察到這么細致贾节，所以遇到忽略這一細致區(qū)別的出題人時請不要過于驚訝汁汗。
二、二叉樹的性質(zhì)
接下來的描述中有必要用到一些數(shù)學(xué)符號栗涂，在Markdown中不好畫出知牌，因此我們再次規(guī)定一些符號——
- ａ＾ｂ—— a的b的次方 （計算機常用，無需多言）
- int_UP（）—— 向上取整（即去掉浮點數(shù)的小數(shù)部分斤程，然后將整數(shù)部分加1）
- int_DOWN（）—— 向下取整（即去掉浮點數(shù)的小數(shù)部分角寸，只留整數(shù)部分）
- log(a,b) —— 表示以a為底取b的對數(shù)
性質(zhì)的內(nèi)容
二叉樹具有以下五個性質(zhì)：
- 在二叉樹的第ｉ（ｉ>=１）層最多有２＾(ｉ - １)個結(jié)點。
- 深度為k(k>=0)的二叉樹最少有k個結(jié)點忿墅，最多有２＾ｋ－１個結(jié)點扁藕。
- 對于任一棵非空二叉樹，若其葉結(jié)點數(shù)為n0疚脐，度為2的非葉結(jié)點數(shù)為n2亿柑，則ｎ0 = ｎ2 ＋１。
- 具有n個結(jié)點的完全二叉樹的深度為int_UP（log(2棍弄，ｎ+1)）望薄。
- 如果將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號１呼畸，２痕支，３，．．．．．．役耕，ｎ采转，然后按此結(jié)點編號將樹中各結(jié)點順序的存放于一個一維數(shù)組，并簡稱編號為i的結(jié)點為結(jié)點i（ ｉ>=１ && ｉ<=ｎ）,則有以下關(guān)系：
（1）若 ｉ= 1瞬痘，則結(jié)點i為根，無父結(jié)點板熊；若 ｉ> 1框全，則結(jié)點 i 的父結(jié)點為結(jié)點int_DOWN（ｉ / ２）;
（2）若 ２＊ｉ <= ｎ，則結(jié)點 ｉ 的左子女為結(jié)點 ２＊ｉ干签；
（3）若２＊ｉ＜＝ｎ津辩，則結(jié)點ｉ的右子女為結(jié)點２＊ｉ＋１；
（4）若結(jié)點編號ｉ為奇數(shù)，且ｉ４亍＝１闸度，它處于右兄弟位置，則它的左兄弟為結(jié)點ｉ－１蚜印；
（5）若結(jié)點編號ｉ為偶數(shù)莺禁，且ｉ！＝ｎ窄赋，它處于左兄弟位置哟冬，則它的右兄弟為結(jié)點ｉ＋１；
（6）結(jié)點ｉ所在的層次為 int_DOWN（log（2忆绰，ｉ））＋１浩峡。
部分性質(zhì)的證明
- 性質(zhì)１可以通過數(shù)學(xué)歸納法得到證明
- 性質(zhì)２證明：
由性質(zhì)１可知，ｋ層的最大節(jié)點總數(shù)可表示為２＾０＋２＾ 1＋……＋２^ (ｋ－１) = ２^ｋ- １错敢； - 性質(zhì)３證明：
首先翰灾，由節(jié)點的角度看ｎ１＋ｎ２＋ｎ０＝ｎ，設(shè)此為（１）式稚茅；
再從邊的角度看预侯，ｎ２下接兩條邊，ｎ１下接一條邊峰锁，ｎ個節(jié)點兩兩相連一共需要ｎ－１條邊萎馅，可得２＊ｎ２＋ｎ１＝ｎ－１，此為（２）式虹蒋；
由（１）式－（２）式糜芳，可得
ｎ０－ｎ２＝１。
三魄衅、一些拓展和說明
1. 完全二叉樹
可以看出性質(zhì)4和5是針對重要的特殊二叉樹——完全二叉樹的峭竣，在此先給出特殊二叉樹的定義。
（1）滿二叉樹
深度k的滿二叉樹是有2^k－1個結(jié)點的二叉樹晃虫，在滿二叉樹中皆撩，每一層結(jié)點都達到了最大個數(shù)，除最底層結(jié)點的度為0外哲银，其他各層結(jié)點的度都為2扛吞。
（2）完全二叉樹
如果一棵具有n個結(jié)點的深度為k的二叉樹，它的每一個結(jié)點都與高度為k的滿二叉樹中編號為1 ~ n－1的結(jié)點一一對應(yīng)荆责，則稱這棵二叉樹為完全二叉樹滥比。
其特點是：上面從第１層到第ｋ－１層的所有各層的結(jié)點數(shù)都是滿的，僅最下面的第ｋ層是滿的做院，或從右往左連續(xù)缺少若干結(jié)點盲泛。
（3）完全二叉樹的結(jié)論
- 若完全二叉樹有ｎ個結(jié)點濒持，當(dāng)ｎ為奇數(shù)時，n1 = 0寺滚，n2 = int_DOWN（ｎ／２）柑营，n0 = n2 + 1；
- 當(dāng)ｎ為偶數(shù)時村视，n1 = 1, n0 = ｎ／２官套；n2 = n0 - 1。
證明 ——
由之前的結(jié)論可知蓖议，k層結(jié)點數(shù)為ｎ－（２＾（ｋ－１）－１）虏杰；
由于僅最下面的第ｋ層是滿的，或從右往左連續(xù)缺少若干結(jié)點勒虾；
ｋ層結(jié)點依次從左到右位于ｋ－１層結(jié)點的下方纺阔，且中間不留空子樹；
故表達式（ｎ－（２＾（ｋ－１）－１））／２的商為ｋ－１層中度為２的結(jié)點修然，余數(shù)為度為１的結(jié)點笛钝。
故當(dāng)ｎ為奇數(shù)時，n1＝０愕宋；
當(dāng)ｎ為偶數(shù)時玻靡，n1＝１；
由于ｋ－１層以及以上的結(jié)點都是滿的中贝，即一共２＾（ｋ－２）－１個結(jié)點囤捻；
ｎ２＝ int_DOWN（（ｎ－（２＾（ｋ－１）－１））／２）＋２＾（ｋ－２）－１
＝ int_DOWN（（ｎ＋１）／２）－１
故當(dāng)ｎ為奇數(shù)時，ｎ２＝ int_DOWN（ｎ／２）＋１－１＝ int_DOWN（ｎ／２）邻寿，ｎ０＝ｎ２＋１蝎土；
當(dāng)ｎ為偶數(shù)時，ｎ２＝ ｎ／２－１绣否，ｎ０＝ｎ／２－１＋１＝ｎ／２誊涯。
證畢。
2. 性質(zhì)５的拓展
如果結(jié)點編號從0開始蒜撮，則有以下結(jié)論：
（1）結(jié)點ｉ（１＜＝ｉ＜＝ｎ－１）的父結(jié)點為結(jié)點int_DOWN（（ｉ－１）／２）暴构，結(jié)點０無父結(jié)點；
（2）分支結(jié)點中編號最大的是結(jié)點int_DOWN（（ｎ－２）／２）或結(jié)點int_DOWN（ｎ／２）－１段磨；
（3）若ｉ＜＝int_DOWN（（ｎ－２）／２）取逾，則結(jié)點ｉ的左子女為２＊ｉ＋１；若ｉ＜＝int_DOWN（（ｎ－３）／２）薇溃，則結(jié)點ｉ的右子女為２＊ｉ＋２菌赖；
（4）若ｉ為偶數(shù)且大于０，則結(jié)點ｉ有左兄弟結(jié)點ｉ－１沐序；若ｉ為奇數(shù)且ｉ＜＝ｎ－２琉用，則結(jié)點ｉ有右兄弟結(jié)點ｉ＋１；
（5）結(jié)點ｉ（０＜＝ｉ＜＝ｎ－１）在第int_DOWN（ｌｏｇ（２策幼，ｉ＋１））＋１邑时。
3. 二叉樹存儲和遍歷的小結(jié)論
- 含有 n 個結(jié)點的二叉鏈表中有 n+1 個空指針域，這是因為在所有結(jié)點的2ｎ個鏈指針域中只有ｎ－１個存有邊信息的緣故特姐。三叉鏈表則有ｎ＋２個空指針域晶丘。
- 前序遍歷算法中，第一個被訪問的元素一定是二叉樹的根唐含，如果根的左子樹非空浅浮，則緊跟在根后的一定是根的左子女；如果左子樹為空捷枯，則其后緊跟的是其右子樹的根滚秩。
- 后序遍歷算法中，最后一個被訪問的一定是二叉樹的根淮捆，如果根的右子樹非空郁油，則在根之前的一定是根的右子女；如果右子樹為空攀痊，則其前的元素是其左子樹的根桐腌。
參考資料:數(shù)據(jù)結(jié)構(gòu)（C語言描述），清華大學(xué)出版社（2012.10）苟径，殷人昆
