樹(shù)：n（n>=0）個(gè)結(jié)點(diǎn)的有限集。n=0時(shí)稱為空樹(shù)碳想。在任意一顆非空樹(shù)中：有且僅有一個(gè)特定的稱為根的結(jié)點(diǎn)烧董；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互不相交的有限集T1胧奔，T2逊移，….Tm，其中每一個(gè)集合本身又是一顆樹(shù)龙填，并且稱為根的子樹(shù)胳泉。
結(jié)點(diǎn)擁有的子樹(shù)數(shù)稱為結(jié)點(diǎn)的度。度為0的結(jié)點(diǎn)稱為葉結(jié)點(diǎn)或終端結(jié)點(diǎn)岩遗；度不為0的結(jié)點(diǎn)稱為非終端結(jié)點(diǎn)或分支節(jié)點(diǎn)扇商。除根結(jié)點(diǎn)外，分支結(jié)點(diǎn)也稱為內(nèi)部結(jié)點(diǎn)宿礁。樹(shù)的度是樹(shù)內(nèi)部結(jié)點(diǎn)的度的最大值案铺。（即那個(gè)結(jié)點(diǎn)分支最多，度即為它的分支數(shù)）
結(jié)點(diǎn)的層次：樹(shù)中結(jié)點(diǎn)的最大層次稱為樹(shù)的深度或高度梆靖。
線性表與樹(shù)在結(jié)構(gòu)上的區(qū)別：
- 線性結(jié)構(gòu)：第一個(gè)數(shù)據(jù)元素：無(wú)前驅(qū)控汉；最后一個(gè)數(shù)據(jù)元素：無(wú)后繼笔诵；中間元素：一個(gè)前驅(qū)一個(gè)后繼
- 樹(shù)結(jié)構(gòu)： 根結(jié)點(diǎn)：無(wú)雙親，唯一姑子；葉結(jié)點(diǎn)：無(wú)孩子乎婿，可以多個(gè)；中間結(jié)點(diǎn)：一個(gè)雙親多個(gè)孩子
- 二叉樹(shù)：n（n>=0）個(gè)結(jié)點(diǎn)的有限集合街佑，該集合或者為空集（稱為空二叉樹(shù)）谢翎，或者由一個(gè)根結(jié)點(diǎn)和兩棵互不相交的分別稱為根結(jié)點(diǎn)的左子樹(shù)和右子樹(shù)的二叉樹(shù)組成。
二叉樹(shù)特點(diǎn)：
1：每個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)沐旨，所以二叉樹(shù)中不存在度大于2 的結(jié)點(diǎn)岳服；
2：左子樹(shù)和右子樹(shù)是有順序的；
3：即使樹(shù)中某結(jié)點(diǎn)只有一顆子樹(shù)希俩，也要區(qū)分它是左子樹(shù)還是右子樹(shù)
所有的結(jié)點(diǎn)都只有左子樹(shù)的二叉樹(shù)叫左斜樹(shù)吊宋。所有的結(jié)點(diǎn)都是只有右子樹(shù)的二叉樹(shù)叫右斜樹(shù)。
滿二叉樹(shù)特點(diǎn)：
1颜武；葉子只能出現(xiàn)在最下一層
2璃搜；非葉子結(jié)點(diǎn)的度一定為2
3；在同樣深度的二叉樹(shù)中鳞上，滿二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)最多这吻，葉子數(shù)最多。
完全二叉樹(shù)的特點(diǎn)：
1篙议；葉子結(jié)點(diǎn)只能出現(xiàn)在最下兩層唾糯。
2；最下層的葉子一定集中在左部連續(xù)位置鬼贱。
3移怯；倒數(shù)二層，若有葉子結(jié)點(diǎn)这难，一定都在右部連續(xù)位置舟误。
4；如果結(jié)點(diǎn)度為1姻乓，則該結(jié)點(diǎn)只有左孩子嵌溢，即不存在只有右子樹(shù)的情況。
5蹋岩；同樣結(jié)點(diǎn)數(shù)的二叉樹(shù)赖草，完全二叉樹(shù)的深度最小。
二叉樹(shù)的性質(zhì)：
- 在二叉樹(shù)的第i層上至多有2的（i-1）次方個(gè)結(jié)點(diǎn)剪个⊙砥铮【i>=1】；
- 深度為k二叉樹(shù)至多有2的k次方-1個(gè)結(jié)點(diǎn)⊥鹊蹋【k>=1】；
- 對(duì)任何一棵二叉樹(shù)T如暖，如果其終端結(jié)點(diǎn)數(shù)（即葉子結(jié)點(diǎn)數(shù)）為n0笆檀，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1;
具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為 [log以2為底n的對(duì)數(shù)]+1 （[x]表示不大于x的最大整數(shù)）盒至；
** 如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)（其深度為[log以2為底n的對(duì)數(shù)]+1）的結(jié)點(diǎn)按層序編號(hào)（從第一層到第[log以2為底n的對(duì)數(shù)]+1層酗洒，每層從左到右），對(duì)任一結(jié)點(diǎn)i（1<=i<=n）有：**
- 如果i=1枷遂，則結(jié)點(diǎn)i是二叉樹(shù)的根樱衷，無(wú)雙親；如果i>1酒唉，則其雙親是結(jié)點(diǎn)[i/2]
- 如果2i>n矩桂，則結(jié)點(diǎn)i無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左孩子是結(jié)點(diǎn)2i;
- 如果2i+1>n痪伦，則結(jié)點(diǎn)i無(wú)右孩子侄榴；否則其右孩子是結(jié)點(diǎn)2i+1；
二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)：
順序存儲(chǔ)結(jié)構(gòu)一般只用于完全二叉樹(shù)网沾，二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)是用一維數(shù)組存儲(chǔ)二叉樹(shù)中的結(jié)點(diǎn)癞蚕，并且結(jié)點(diǎn)的存儲(chǔ)位置，就是數(shù)組的下標(biāo)辉哥。
二叉鏈表：鏈表設(shè)計(jì)了一個(gè)數(shù)據(jù)和兩個(gè)指針域（指針域分別存放指向左孩子和右孩子的指針）
二叉樹(shù)遍歷方法：
前序遍歷：若二叉樹(shù)為空桦山，則空操作返回，否則先訪問(wèn)根結(jié)點(diǎn)醋旦，然后前序遍歷左子樹(shù)恒水，再前序遍歷右子樹(shù)。
中序遍歷：若樹(shù)為空饲齐，則空操作返回寇窑，否則從根結(jié)點(diǎn)開(kāi)始（注意并不是先訪問(wèn)根結(jié)點(diǎn)），中序遍歷根結(jié)點(diǎn)的左子樹(shù)箩张，然后是訪問(wèn)根結(jié)點(diǎn)甩骏，最后中序遍歷右子樹(shù)。
后序遍歷：若樹(shù)為空先慷，則空操作返回饮笛，否則從左到右先葉子后結(jié)點(diǎn)的方式遍歷訪問(wèn)左右子樹(shù)，最后是訪問(wèn)根結(jié)點(diǎn)论熙。
層序遍歷：若樹(shù)為空福青，則空操作返回，否則從樹(shù)的第一層，也就是根結(jié)點(diǎn)開(kāi)始訪問(wèn)无午，從上而下逐層遍歷媒役，在同一層中，按從左到右的順序?qū)Y(jié)點(diǎn)逐個(gè)訪問(wèn)宪迟。
【已知前序遍歷序列和中序遍歷序列酣衷，可以唯一確定一棵二叉樹(shù)。已知后序遍歷序列和中序遍歷序列次泽，可以唯一確定一棵二叉樹(shù)】
把指向前驅(qū)和后繼的指針?lè)Q為線索穿仪，加上線索的二叉鏈表稱為線索鏈表，相應(yīng)的二叉樹(shù)就稱為線索二叉樹(shù)意荤。
對(duì)二叉樹(shù)以某種次序遍歷使其變?yōu)榫€索二叉樹(shù)的過(guò)程稱作是線索化啊片。線索化的實(shí)質(zhì)是將二叉鏈表中的空指針改為指向前驅(qū)或后繼的線索。線索化的過(guò)程就是在遍歷的過(guò)程中修改空指針的過(guò)程玖像。
