樹和二叉樹
1盏档、樹的定義
樹(Tree)是由?一個 或 多個結(jié)點 ?組成的有限集合T虱痕，且滿足：
①有且僅有一個稱為根的結(jié)點域仇；
②其余結(jié)點分成n(n≥0)個互不相交的集合T1,T2,…Tn葫哗，其中每個集合都是一棵樹，并且稱Ti (1≤i≤n) 為根的子樹振湾。
顯然樹是一個遞歸定義杀迹。
圖1.3是一棵具有13個結(jié)點的樹，其中A結(jié)點是樹的根押搪，其余12個結(jié)點劃分為3個互不相交的子集：
T1?=?{?B,?E?,F,?K,?L?}?T2?=?{C?,G?}
T3?=?{?D,?H,?I,?J,?M?}
T1,?T2,?T3?均是根A的子樹树酪，其本身也都是樹浅碾。我們還可以繼續(xù)劃分，集合{E,?K?L}是B的子樹续语，以此類推垂谢。所以我們除了用圖來表示樹的結(jié)構(gòu)，還可用廣義表來表示樹疮茄，例如滥朱，圖1.3的樹用廣義表表示如下：
T=（A（B（E（K，L）力试，F(xiàn)））徙邻，C（G），D（H（M）懂版，I鹃栽，J）））
2躏率、樹的基本術(shù)語
因為樹的結(jié)構(gòu)比其他線性結(jié)構(gòu)更復(fù)雜躯畴，所以我們需要用一些術(shù)語來描述結(jié)點和結(jié)點之間的關(guān)系。
①根結(jié)點
每一棵樹都有一個根結(jié)點薇芝，如圖1.3中A結(jié)點蓬抄。根據(jù)樹的定義，樹中的每一個結(jié)點都可以看成是它的一個子樹的根夯到。
如結(jié)點B,?C,?D分別是子樹T1,?T2,?T3的根結(jié)點嚷缭。但是A結(jié)點與其它結(jié)點不同的是，只有后繼結(jié)點而沒有前趨結(jié)點耍贾，所以
A被稱為樹的根阅爽。
②結(jié)點的度和樹的度
一個結(jié)點的子樹的個數(shù)稱為是該結(jié)點的度。如根結(jié)點A有3個子樹荐开，則A結(jié)點的度為3付翁；而C結(jié)點只有1
個子樹，則C結(jié)點的度為1晃听。樹中度數(shù)最大的結(jié)點的度為樹的度百侧。樹T的度是3。
③分支結(jié)點和葉結(jié)點
度為0的結(jié)點稱為葉結(jié)點或端結(jié)點能扒。如K,?L,?F,?G,?M,?I,?J,這些結(jié)點都是樹的葉結(jié)點佣渴。度大于0的結(jié)點稱作分支結(jié)點。
④子結(jié)點和父結(jié)點
每個結(jié)點的子樹的根結(jié)點稱為該結(jié)點的兒子（子結(jié)點）初斑，而該結(jié)點稱為子結(jié)點的父親（父結(jié)點）辛润。如A結(jié)點為B結(jié)點的父結(jié)點，B
為A的子結(jié)點见秤。樹中的一條邊連接兩個結(jié)點砂竖，這兩個結(jié)點互為父子關(guān)系灵迫。有同一個父結(jié)點的所有子結(jié)點稱為兄弟。如B,?C,?D就互為兄弟晦溪。
某結(jié)點到整棵樹的根結(jié)點的路徑上的所有結(jié)點叫作該結(jié)點的祖先瀑粥。如結(jié)點K到根結(jié)點A的路徑上的所有結(jié)點E,?B,?A，都是結(jié)點K的祖先三圆。
⑤結(jié)點的層數(shù)和樹的深度
樹既是一種遞歸結(jié)構(gòu)狞换，也是一種層次結(jié)構(gòu)，樹中的每個結(jié)點都處在一定的層數(shù)上舟肉。結(jié)點的層數(shù)從樹根開始定義修噪，設(shè)根結(jié)點的層號為1，其兒子結(jié)點的層號為2路媚，以此類推黄琼；若某結(jié)點在第L層，則該結(jié)點的兒子處于第L+1層整慎。樹中結(jié)點最大的層號為樹的深度脏款。樹T的深度為4。
⑥ 有序樹和無序樹
若結(jié)點的子樹有次序排列裤园，且先后次序不能互換撤师，這樣的樹稱為有序樹，反之為無序樹拧揽。
⑦?森林
森林是若干棵互不相交的樹的集合剃盾。若刪除圖1.3中樹T的根結(jié)點A，就得到一個森林{T1,?T2,?T3}淤袜。
1痒谴、二叉樹的定義
如果樹中每個結(jié)點的子樹個數(shù)小于或等于2的樹，并且各子樹的次序不能互換铡羡，有左积蔚、右子樹之分，這樣的樹稱為二叉樹蓖墅。所以二叉樹是一種度為2的有序樹库倘。
根據(jù)定義，二叉樹共有5種不同的基本形態(tài)论矾，如圖1.4所示教翩。
a. 空二叉樹；
b.?只有一個根結(jié)點的二叉樹贪壳；
?c.?右子樹為空的二叉樹饱亿；
?d.?左子樹為空的二叉樹；
?e.?左、右子樹非空的二叉樹彪笼。
2钻注、二叉樹的性質(zhì)
性質(zhì)1 在二叉樹中，第i層的結(jié)點總數(shù)不超過2i-1(i>=1)配猫；?
性質(zhì)2 深度為k的二叉樹的結(jié)點總數(shù)不超過2k-1(k>=1)幅恋。
請看圖1.5中的二叉樹：
第1層?1個結(jié)點，20
第2層?2個結(jié)點泵肄，21?第3層?4個結(jié)點捆交，22
第I層?2i-1個結(jié)點；
那么對于深度為k的二叉樹所具有的結(jié)點總數(shù)為：
如果一個深度為K的二叉樹腐巢，具有2k-1個結(jié)點品追，則稱該二叉樹為滿二叉樹。如圖1.5是深度為4的滿二叉樹冯丙，它的結(jié)點總數(shù)是15肉瓦。滿二叉樹最底一層的各個結(jié)點的度數(shù)為0，而其余的結(jié)點的度數(shù)均為2胃惜。
如果一棵深度為K二叉樹泞莉，1至k-1層的結(jié)點都是滿的，即滿足2i-1蛹疯，只有最下面的一層的結(jié)點數(shù)小于2i-1戒财，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置，則此二叉樹稱為完全二叉樹捺弦。如圖1.6所示。
如果二叉樹的中間有些結(jié)點不存在孝扛，如圖1.7所示二叉樹列吼，稱為不完全二叉樹
性質(zhì)3 在任意一棵二叉樹中，度為0的結(jié)點（葉結(jié)點）比度為2的結(jié)點多一個苦始。
在二叉樹中寞钥，如果其葉結(jié)點的個數(shù)為N0，其度數(shù)為2的結(jié)點總數(shù)為N2陌选，則有： N0=N2+1理郑。
例如：圖1.5的樹，n0=8,?n2=7
圖?1.7的樹咨油，n0=4,?n2=3
性質(zhì)4 具有n個結(jié)點的二叉樹您炉，其深度至少為[log2n]+1，其中[log2n]表示取log2n的整數(shù)部分役电。
對于完全二叉樹赚爵，還有如下性質(zhì)： 1) 在完全二叉樹中，深度K與結(jié)點總數(shù)N的關(guān)系為：K=[Log2N]+1，且有如下關(guān)系：2k-11冀膝，則父結(jié)點為[i/2]唁奢。
如果2*I>N，則I無左子樹窝剖；如果2*I<=N麻掸，則I的左兒子的編號為2*I。
如果2*I+1>N赐纱，則I無右子樹论笔；如果2*I+1<=N，則I的右兒子的編號為2*I+1千所。
3狂魔、 二叉樹的存儲結(jié)構(gòu)
二叉樹的存儲結(jié)構(gòu)有兩種形式：
?1) 順序存儲方式；
?2) 鏈表存儲方式淫痰。
【順序存儲方式】
對于滿二叉樹和完全二叉樹最楷，可以對每個結(jié)點進(jìn)行連續(xù)編號，所以通常采用順序存儲的方式待错。具體做法是：定義一個一維數(shù)組籽孙，把每個結(jié)點的編號作為數(shù)組的下標(biāo)變量，將結(jié)點的值存放在數(shù)組中火俄。二叉樹的各結(jié)點的編號從根結(jié)點開始犯建，根結(jié)點的標(biāo)號為1，然后瓜客，逐層由左向右進(jìn)行連續(xù)編號适瓦，并將該結(jié)點的值存于對應(yīng)編號為下標(biāo)的一維數(shù)組中。如圖1.9所示谱仪。
如圖1.10所示的不完全二叉樹玻熙，也可以用順序存儲的形式。將不完全二叉樹缺掉的結(jié)點補(bǔ)齊疯攒，然后以滿二叉樹編號方式進(jìn)行編號嗦随，以編號順序?qū)⒃摌涞母鹘Y(jié)點存放在一維數(shù)組中。由此看出敬尺，6枚尼，7，8砂吞，9署恍，12，13呜舒，14锭汛，15的單元里是沒有存放數(shù)據(jù)的笨奠，而這樣的不完全二叉樹實際上只有7個結(jié)點，卻要占用15個存儲單元唤殴，不免浪費(fèi)空間般婆。
但是，在這種存儲方式下朵逝，從一個結(jié)點的編號就可以推測其父結(jié)點蔚袍，左右子結(jié)點的編號，據(jù)此配名，可以輕易畫出二叉樹啤咽。
【鏈表存儲方式】
用鏈接表存儲二叉樹，每個結(jié)點由三部分組成：數(shù)據(jù)域渠脉、左地址域宇整、右地址域。左指針芋膘、右指針分別指向該結(jié)點的左兒子和右兒子的地址域鳞青。見圖1.12。
每個結(jié)點的數(shù)據(jù)格式為：
4. 二叉樹的遍歷
二叉樹的遍歷是根據(jù)一定的規(guī)律訪問二叉樹的每一個結(jié)點为朋，所謂訪問臂拓，可以是打印該結(jié)點的值，修改該結(jié)點的值习寸，或?qū)⒃摻Y(jié)點做某些處理等胶惰。
二叉樹的遍歷是二叉樹必須掌握的知識點，一般面試都會碰到根據(jù)已知遍歷序列求出要求序列霞溪，只要真正掌握了遍歷的方法孵滞，這類問題也就很簡單了。
根據(jù)根結(jié)點威鹿，左子樹剃斧，右子樹先后訪問的不同順序，可以有以下六種不同的遍歷方式：
①根忽你，左，右臂容；
②左科雳，根，右脓杉；
③左糟秘，右，根球散；
④根尿赚，右，左；
⑤右凌净，左悲龟，根；
⑥右冰寻，根须教，左。
二叉樹最常用的遍歷運(yùn)算是：
①先序遍歷斩芭，根轻腺，左，右划乖；
②中序遍歷贬养，左，根琴庵，右误算；
③后序遍歷，左细卧，右尉桩，根。
1)?先序遍歷：
先訪問根結(jié)點贪庙，再先序遍歷左子樹蜘犁，最后再先序遍歷右子樹。
圖1.13按先序遍歷 各結(jié)點被訪問的順序為：ABDHIECFG
2)中序遍歷：
先中序遍歷左子樹止邮，然后再訪問根結(jié)點这橙，最后再中序遍歷右子樹。
圖1.13按中序遍歷 各結(jié)點被訪問的順序為：HDIBEAFCG
3) 后序遍歷：
先后序遍歷左子樹导披，然后再后序遍歷右子樹屈扎，最后再訪問根結(jié)點。
對圖1.13的二叉樹進(jìn)行后序遍歷撩匕，訪問各個結(jié)點的順序為：HIDEBFGCA
遍歷算法案例：
給出一棵二叉樹的中序遍歷：DBGEACHFI與后序遍歷：DGEBHIFCA鹰晨，畫出此二叉樹（求先序遍歷的話連二叉樹都出來了還不簡單？）止毕。
問題分析：
后序遍歷中最后訪問的是根結(jié)點模蜡，所以后序遍歷DGEBHIFCA序列中A是根結(jié)點；
根據(jù)中序遍歷的算法扁凛，先中序遍歷左子樹忍疾，然后再訪問根結(jié)點，最后再中序遍歷右子樹谨朝，所以中序遍歷DBGEACHFI序列中卤妒，根結(jié)點A的兩側(cè)分別是左子樹和右子樹：DBGE甥绿、CHFI。
對左子樹的中序遍歷DBGE则披、后序遍歷DGEB
用上面的方法分析共缕，得知B是左子樹的根結(jié)點，D是B的左子樹收叶，GE是B的右子樹骄呼。
同理可以推出E是G的父結(jié)點，G是E的左兒子判没。
上述推導(dǎo)過程如圖1.14 a所示蜓萄，最后的結(jié)果如圖1.14 b所示。
以上就是二叉樹的三種遍歷算法澄峰，其實還有一個層次遍歷嫉沽，有興趣的可以自己去了解一下
本來想著弄二叉搜索樹的，但是想先把定義之類的理一下俏竞，找了很多資料綜合自己以前學(xué)的绸硕，整理了一下書和二叉樹的基本概念。
在這里還有一個坑：就是二叉樹是不是樹的問題魂毁。
我的看法是：二叉樹不是樹玻佩，最為關(guān)鍵的一點，樹不可以為空席楚，二叉樹可以空咬崔，大家看上面的定義就可以知道。
（純粹個人觀點烦秩，因為我在網(wǎng)上找了好久兩種說法都有垮斯，我是比較偏向二叉樹不是樹的，如果我看的定義都沒錯的話）
