面試題(5)-面試中常考的樹(shù)(2)_什么是二叉樹(shù)和二叉樹(shù)的遍歷
1.什么是二叉樹(shù)
二叉樹(shù)需要滿足兩個(gè)條件:
本質(zhì)上為有序樹(shù)；
每個(gè)結(jié)點(diǎn)的度(結(jié)點(diǎn)擁有子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的度)不能超過(guò)2，即結(jié)點(diǎn)的度僅能為0，1，2。
二叉樹(shù)的性質(zhì)
二叉樹(shù)第i層的結(jié)點(diǎn)數(shù)最多為2^(i-1) (i>=1)。
深度為k的二叉樹(shù)最多有2^k - 1個(gè)結(jié)點(diǎn)。
在任意一顆二叉樹(shù)中，若終端結(jié)點(diǎn)（葉子結(jié)點(diǎn)）的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)樹(shù)為n2，則n0=n2+1。
證明：設(shè)二叉樹(shù)中度為1的結(jié)點(diǎn)數(shù)為n1，結(jié)點(diǎn)總數(shù)為n，則n = n0 + n1 +n2。同時(shí)，度為2的子結(jié)點(diǎn)共有2 * n2個(gè)，度為1的子結(jié)點(diǎn)共有n1個(gè)，總結(jié)點(diǎn)數(shù)=子結(jié)點(diǎn)數(shù)+根結(jié)點(diǎn) 故n = n2 * 2 + n1 +1。兩等式聯(lián)立得出n0 = n2 +1。
二叉樹(shù)的分類(lèi)：
1.滿二叉樹(shù)：
若二叉樹(shù)中除了葉子結(jié)點(diǎn)，每一個(gè)節(jié)點(diǎn)的度都為2，則稱此二叉樹(shù)為滿二叉樹(shù)。
滿二叉樹(shù)具有以下性質(zhì)：
滿二叉樹(shù)的第i層結(jié)點(diǎn)數(shù)為2^(i-1)；
深度為k的滿二叉樹(shù)有2^k - 1個(gè)結(jié)點(diǎn)，葉子結(jié)點(diǎn)有2^(k-1)個(gè)；
具有n個(gè)結(jié)點(diǎn)的滿二叉樹(shù)的深度為log2(n+1)；
滿二叉樹(shù)中不存在度為1的結(jié)點(diǎn)，葉子結(jié)點(diǎn)僅存在在最底層。
2.完全二叉樹(shù)
若二叉樹(shù)除了最后一層結(jié)點(diǎn)滿足滿二叉樹(shù)的定義，且最后一層節(jié)點(diǎn)滿足從左到右分布的次序，則該二叉樹(shù)被稱為完全二叉樹(shù)。
完全二叉樹(shù)除了滿足普通二叉樹(shù)的性質(zhì)外，還滿足以下性質(zhì)：
n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度為[log2n]+1;
將完全二叉樹(shù)按照層次從左到右編號(hào)，
（1）當(dāng)i > 1時(shí)，序號(hào)為i的結(jié)點(diǎn)的父結(jié)點(diǎn)為結(jié)點(diǎn)[i / 2]；
（2）若2i > n, 則序號(hào)為i的結(jié)點(diǎn)無(wú)左子女結(jié)點(diǎn)，否則該節(jié)點(diǎn)的左子女結(jié)點(diǎn)序號(hào)為2i；
（3）若2i+1>n，則序號(hào)為i的結(jié)點(diǎn)無(wú)右子女結(jié)點(diǎn)，否則該結(jié)點(diǎn)的右子女結(jié)點(diǎn)的序號(hào)為2i+1。
二叉樹(shù)的存儲(chǔ)方式
二叉樹(shù)的存儲(chǔ)方式有兩種，順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。
1.順序存儲(chǔ)
順序存儲(chǔ)只適用于完全二叉樹(shù)，若想存儲(chǔ)普通二叉樹(shù)，需要先將其轉(zhuǎn)化為完全二叉樹(shù)。滿二叉樹(shù)也是一種特殊的完全二叉樹(shù)。普通二叉樹(shù)轉(zhuǎn)化成完全二叉樹(shù)的方法如下
對(duì)于完全二叉樹(shù)的存儲(chǔ)，僅需對(duì)其從根節(jié)點(diǎn)開(kāi)始僅需編號(hào)，使用數(shù)組存儲(chǔ)編號(hào)即可。取出式依據(jù)完全二叉樹(shù)由左到右分布的性質(zhì)恢復(fù)即可。
2.鏈?zhǔn)酱鎯?chǔ)
順序存儲(chǔ)會(huì)造成一定程度上的空間浪費(fèi)，鏈?zhǔn)酱鎯?chǔ)可以很好地解決這個(gè)問(wèn)題。鏈?zhǔn)酱鎯?chǔ)中每個(gè)結(jié)點(diǎn)包含三部分：左孩子結(jié)點(diǎn)、數(shù)據(jù)域和右孩子結(jié)點(diǎn)。
鏈?zhǔn)酱鎯?chǔ)的JAVA實(shí)現(xiàn)為：
2.二叉樹(shù)的遍歷
二叉樹(shù)的遍歷指從根結(jié)點(diǎn)出發(fā)，按照某種次序依次訪問(wèn)二叉樹(shù)中所有的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)被訪問(wèn)的次數(shù)有且僅有一次。
1.前序遍歷：
前序遍歷的思想是：（根左右）
先訪問(wèn)根結(jié)點(diǎn)；
訪問(wèn)當(dāng)前結(jié)點(diǎn)的左子樹(shù)；
訪問(wèn)當(dāng)前結(jié)點(diǎn)的右子樹(shù)。
遍歷順序?yàn)椋篈 -> B -> D -> E -> C -> F -> G
2.中序遍歷：
中序遍歷的思路是：（左根右）
遇到一個(gè)節(jié)點(diǎn)，先緩存，看其是否有左子節(jié)點(diǎn)，若有，則輸出左節(jié)點(diǎn)，再輸出原節(jié)點(diǎn)，最后輸出右節(jié)點(diǎn)。
中序遍歷順序?yàn)椋篋 -> B -> E ->A -> F -> C -> G
3.后序遍歷：
后續(xù)遍歷的思路是：（左右根）
遇到一個(gè)節(jié)點(diǎn)，先緩存，看它是否存在左子節(jié)點(diǎn)，有則輸出，接著看其是否有右子結(jié)點(diǎn)，最后輸出原節(jié)點(diǎn)。
后序遍歷順序?yàn)椋篋 -> E -> B -> F -> G -> C ->A
4.廣度優(yōu)先搜索(BFS)：
又稱寬度優(yōu)先搜索,層次遍歷,廣度優(yōu)先搜索思路是：
先訪問(wèn)上一層，在訪問(wèn)下一層，從左至右進(jìn)行遍歷, 一層一層的往下訪問(wèn)
廣度優(yōu)先搜索為：A -> B -> C -> D -> E -> F ->G
5.深度優(yōu)先搜索(DFS)：
深度優(yōu)先搜索思路是：
他的訪問(wèn)順序是：先訪根節(jié)點(diǎn)，然后左結(jié)點(diǎn)，一直往下，直到最左結(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)的時(shí)候然后往上退一步到父節(jié)點(diǎn)，然后父節(jié)點(diǎn)的右子節(jié)點(diǎn)在重復(fù)上面步驟……
深度優(yōu)先搜索為：A -> B -> D -> E -> C -> F -> G
