1. 樹的遍歷方式
樹的遍歷是指訪問樹節(jié)點的數(shù)據(jù)（可以是打印，也可以是做其他的事情）。樹的遍歷有廣度優(yōu)先與深度優(yōu)先兩大類。
- 廣度優(yōu)先：先處理同一層的兄弟結(jié)點（增加寬度），再處理子結(jié)點。廣度優(yōu)先遍歷又叫層序遍歷，是從上往下從左到右的遍歷方式。
- 深度優(yōu)先：先處理子結(jié)點（增加深度），再處理同級的兄弟結(jié)點。另外，深度優(yōu)先遍歷，根據(jù)被遍歷結(jié)點與其左右子結(jié)點的位置，分為三種情況：
- 先序遍歷（pre-order）：[DLR]( data, left, right )，先訪問結(jié)點數(shù)據(jù)，再遞歸遍歷左子樹，然后遞歸遍歷右子樹；
- 中序遍歷（in-order）：[LDR]( left, data, right )，先遞歸遍歷左子樹，再訪問結(jié)點數(shù)據(jù)，然后遞歸遍歷右子樹；
- 后序遍歷（post-order）：[LRD]( left, right, data )，先遞歸遍歷左子樹，再遞歸遍歷右子樹，最后訪問結(jié)點數(shù)據(jù)。
注意：剛學(xué)習(xí)的時候很容易忘記遞歸，經(jīng)常遍歷左結(jié)點之后立馬就回去了，這樣會遍歷不全。記住，我們是深度優(yōu)先，只要當(dāng)前遍歷的結(jié)點不為null，就繼續(xù)往下處理子結(jié)點，直到遇到null再回歸。
1.1 怎樣牢記三種遍歷方式
- 先左后右——LR：左右子樹順序固定不變。
- x1-L-x2-R-x3，顯然看得出，我們可以在x1, x2, x3的任意一個位置上遍歷結(jié)點本身。在最前邊就叫前序遍歷，在中間的叫中序遍歷，在最后的叫后序遍歷。
1.2 遍歷示例
我們分別用不同的遍歷方式遍歷上圖二叉樹，結(jié)果為：
- 層序遍歷：3-1-5-2-4；
- 先序遍歷：3-1-2-5-4；
- 中序遍歷：1-2-3-4-5；
- 后序遍歷：2-1-4-5-3.
2. 代碼實現(xiàn)
2.1 層序遍歷
層序遍歷的思路挺有用的，希望大家能熟記，之后在別的地方會用到。
在層序遍歷中，當(dāng)我們遍歷完某一層的最后一個結(jié)點后，接下來要遍歷下一層的第一個結(jié)點（假設(shè)存在），但這兩個結(jié)點之間沒有一點關(guān)系，沒有任何連接，怎樣才能從上一層的最后一個跳到下一層的第一個呢？
答案是：我們需要借助一種數(shù)據(jù)結(jié)構(gòu)——隊列。我們可以在遍歷上一層的每個結(jié)點的時候，把該結(jié)點的子結(jié)點放入隊列中，當(dāng)上一層處理完之后，再從隊列里面取出結(jié)點就是下一層的結(jié)點，且是從左到右的順序。利用隊列先進先出的特性，能保證遍歷順序的正確性。根結(jié)點比較特殊，直接入隊列即可。
// 遍歷：可以對node做任何你想做的事情，這里我們僅僅打印。
private void doSomethingWithNode(Node node) {
System.out.printf("%s\t", node.data);
}
// 層序遍歷（廣度優(yōu)先遍歷）
public void layerTraversal() {
if (root == null) {
return;
}
// 這里用到自己實現(xiàn)的隊列（我會在其他的文章里面詳解隊列的原理與實現(xiàn)），你可以換成系統(tǒng)自帶的。
LinkQueue<Node> queue = new LinkQueue<>();
queue.enqueue(root);
while (!queue.isEmpty()) {
Node node = queue.dequeue();
doSomethingWithNode(node);
if (node.left != null) {
queue.enqueue(node.left);
}
if (node.right != null) {
queue.enqueue(node.right);
}
}
}
2.2 深度優(yōu)先遍歷
我們這里用遞歸的方式實現(xiàn)，遞歸出口是node == null。另外，遞歸都可以轉(zhuǎn)化為非遞歸，我會單獨詳細講述遞歸與非遞歸之間的相互轉(zhuǎn)換，這里不再進一步敘述。
核心代碼就3行，2行遞歸調(diào)用，一行遍歷操作(代碼中的doSomethingWithNode)。doSomethingWithNode在最上面，就是先序遍歷，在中間就是中序遍歷，在最后就是后序遍歷。
// 先序遍歷
private void preOrder(Node node) {
if (node == null) {
return;
}
doSomethingWithNode(node);
preOrder(node.left);
preOrder(node.right);
}
// 中序遍歷
private void inOrder(Node node) {
if (node == null) {
return;
}
inOrder(node.left);
doSomethingWithNode(node);
inOrder(node.right);
}
// 后序遍歷
private void postOrder(Node node) {
if (node == null) {
return;
}
postOrder(node.left);
postOrder(node.right);
doSomethingWithNode(node);
}
3. 根據(jù)遍歷結(jié)果把樹還原
我們可以根據(jù)：中序遍歷 + 任意一種其他的遍歷，來還原一棵樹。拿簡單點的中序遍歷 + 層序遍歷舉例：
層序遍歷：3-1-5-2-4；中序遍歷：1-2-3-4-5。接下來的敘述統(tǒng)一用層序x來表示層序遍歷x結(jié)點，中序也一樣。層序3說明根結(jié)點為3，層序1和5表示第2層（即根3的左右孩子）分別為1和5；層序2和4說明2和4在第3層，但無法確定位置，我們再看中序，中序1在2之前，表示2為1的父結(jié)點（不可能，因為2在1的下面）或2為1的右結(jié)點，所以2為1的右結(jié)點。同理，得出4為5的左結(jié)點。
4. 遍歷的應(yīng)用
- 前序遍歷：1. 打印目錄樹。 // TODO
- 中序遍歷：1. 排序數(shù)的順序輸出。// TODO
- 后序遍歷：1. 計算目錄內(nèi)的文件大小。 // TODO
源碼
轉(zhuǎn)載聲明
如果您需要轉(zhuǎn)載，請注明轉(zhuǎn)載來源。
