背景
前面已經(jīng)學(xué)習(xí)了線性結(jié)構(gòu)和表結(jié)構(gòu)撑毛，這些數(shù)據(jù)結(jié)構(gòu)適用于一部分的數(shù)據(jù)組織抹锄，但是對于局域分支結(jié)構(gòu)的數(shù)據(jù)获高，就需要另一種數(shù)據(jù)結(jié)構(gòu)了—樹。這種分支結(jié)構(gòu)的數(shù)據(jù)與數(shù)據(jù)之間可能有上下級關(guān)系币狠、可能有整體與部分的關(guān)系漩绵，如現(xiàn)實(shí)世界中的族譜止吐、公司的組織結(jié)構(gòu)粟害、書的章節(jié)等悲幅。
樹的定義是一個遞歸的定義卓鹿，即樹的定義中又用到了樹的概念。
二叉樹
它的特點(diǎn)是每個結(jié)點(diǎn)最多有兩個子女，分別成為該結(jié)點(diǎn)的左子女和右子女。就是說倍宾，在二叉樹中不存在度大于2的結(jié)點(diǎn)辞州，并且二叉樹的子樹有左、右之分牵啦，其子樹的次序不能顛倒哈雏。
滿二叉樹：每一層結(jié)點(diǎn)都達(dá)到了最大個數(shù)。
完全二叉樹：一共有k層，從第1層到第k-1層的所有各層結(jié)點(diǎn)數(shù)都是滿的还最。
二叉樹的存儲結(jié)構(gòu)又兩種：數(shù)組方式和鏈表方式
數(shù)組存儲是從根節(jié)點(diǎn)開始為數(shù)組的第一個元素，然后一層層往下毡惜，從左到右拓轻，存儲到數(shù)組中，如果遇到空的经伙，也就是說不是完全二叉樹扶叉，則用空置將其補(bǔ)全。所以說存儲完全二叉樹是最簡單帕膜、最節(jié)省存儲的存儲方式枣氧。
鏈表存儲對于形態(tài)劇烈變化的二叉樹是比較好的存儲表示，其針對每個二叉樹結(jié)點(diǎn)應(yīng)該包含三個域泳叠，即data作瞄、左子女結(jié)點(diǎn)指針、右子女結(jié)點(diǎn)指針危纫。使用這種結(jié)構(gòu)尋找子女結(jié)點(diǎn)很方便宗挥，但要尋找父節(jié)點(diǎn)就很困難了，因此可以增加一個父指針域种蝶。
二叉樹遍歷
所謂二叉樹遍歷就是遵從某種次序契耿，遍訪二叉樹中的所有結(jié)點(diǎn)，使得每個結(jié)點(diǎn)被訪問一次螃征，而且只訪問一次搪桂。
前序遍歷：遵循VLR的原則（V表示該結(jié)點(diǎn)，L表示左子樹、R表示右子樹）
中序遍歷：遵循LVR的原則
后續(xù)遍歷：遵循LRV的原則
要理解好以上遍歷規(guī)則踢械，是需要在每一個結(jié)點(diǎn)都對（VLR/LVR/LRV）進(jìn)行嚴(yán)格地判斷酗电。
二叉樹遍歷的應(yīng)用
- 二叉樹后序遍歷的應(yīng)用
- 二叉樹前序遍歷的應(yīng)用
- 利用二叉樹謙虛遍歷建立二叉樹
二叉樹遍歷的非遞歸算法（這個后面看）
二叉樹的計(jì)數(shù)
線索二叉樹
