二叉樹的四種遍歷算法

2019-11-06 06:32:05

字體：大中小

來源：轉載

供稿：網友

二叉樹在作為一種重要的數據結構，它的很多算法的思想在很多地方都用到了，比如說大名鼎鼎的 STL 算法模板，里面的優先隊列（PRiority_queue）、集合（set、map）等等都用到了二叉樹里面的思想，如果有興趣的小伙伴可以去查找一些這些方面的資料。但是我們現在先不討論那么高深的數據結構，我們先從二叉樹的遍歷開始：

先來看一下二叉樹長什么樣子：

這里寫圖片描述

這是百度來的一張二叉樹圖，我們可以看到，這棵二叉樹一共有 7 個節點，其中， 0 號節點叫做“根節點”，下面的 1 號節點和 2 號節點是 0 號節點的子節點，1 號節點為 0 號節點的“左子節點， 2 號節點為 0 號節點的 右子節點 同時 1 號節點和 2 號節點又是 3 號節點、 4 號節點和 5 號節點、6號節點的雙親節點， 0 號節點有分別以 1 號節點和 2 號節點作為根節點的左右子樹。 5 號節點和 6 號節點沒有子節點（子樹），那么它們被稱為“葉子節點”。好了，一些常用的基本概念就到這了，能理解就行，如果還想了解更多專業術語，可以去找一些別的資料。

下面進入正題，二叉樹的遍歷：

一般來說，二叉樹常用的遍歷方式有：前序遍歷、中序遍歷、后序遍歷、層序遍歷 四種遍歷方式，不同的遍歷算法，其思想略有不同，我們來看一下這四種遍歷方法主要的算法思想：

1、先序遍歷二叉樹順序：根節點 –> 左子樹 –> 右子樹，即先訪問根節點，然后是左子樹，最后是右子樹。 上圖中二叉樹的前序遍歷結果為：0 -> 1 -> 3 -> 4 -> 2 -> 5 -> 6

2、中序遍歷二叉樹順序：左子樹 –> 根節點 –> 右子樹，即先訪問左子樹，然后是根節點，最后是右子樹。 上圖中二叉樹的中序遍歷結果為：3 -> 1 -> 4 -> 0 -> 5 -> 2 -> 6

3、后續遍歷二叉樹循序：左子樹 –> 右子樹 –> 根節點，即先訪問左子樹，然后是右子樹，最后是根節點。 上圖中二叉樹的后序遍歷結果為：3 -> 4 -> 1 -> 5 -> 6 -> 2 -> 0

4、層序遍歷二叉樹順序：從最頂層的節點開始，從左往右依次遍歷，之后轉到第二層，繼續從左往右遍歷，持續循環，直到所有節點都遍歷完成 上圖中二叉樹的中序遍歷結果為：0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6

下面給出這四種算法思想的偽代碼：

前序遍歷：

preOrderParse(int n) { if(tree[n] == NULL) return ; // 如果這個節點不存在，那么結束 cout << tree[n].w ; // 輸出當前節點內容 preOrderParse(tree[n].leftChild); // 遞歸輸出左子樹 preOrderParse(tree[n].rightChild); // 遞歸輸出右子樹 }

中序遍歷：

inOrderParse(int n) { if(tree[n] == NULL) return ; // 如果這個節點不存在，那么結束 inOrderParse(tree[n].leftChild); // 遞歸輸出左子樹 cout << tree[n].w ; // 輸出當前節點內容 inOrderParse(tree[n].rightChild); // 遞歸輸出右子樹 }

后續遍歷：

pastOrderParse(int n) { if(tree[n] == NULL) return ; // 如果這個節點不存在，那么結束 pastOrderParse(tree[n].leftChild); // 遞歸輸出左子樹 pastOrderParse(tree[n].rightChild); // 遞歸輸出右子樹 cout << tree[n].w ; // 輸出當前節點內容 }

可以看到前三種遍歷都是直接通過遞歸來完成，用遞歸遍歷二叉樹簡答方便而且好理解，接下來層序遍歷就需要動點腦筋了，我們如何將二叉樹一層一層的遍歷輸出？其實在這里我們要借助一種數據結構來完成：隊列。我們都知道，隊列是一種先進先出的數據結構，我們可以先將整顆二叉樹的根節點加入隊尾，然后循環出隊，每次讀取對頭元素輸出并且將隊頭元素出隊，然后將這個輸出的元素節點的的左右子樹分別依次加入隊尾，重復這個循環，知道隊列為空的時候結束輸出。那么整個二叉樹就被我們采用層序遍歷的思想輸出來了。下面我們看一下上圖的二叉樹用層序遍歷思想的遍歷步驟：

這里寫圖片描述

因為筆者不會用 PS，所以用手工代替了，字寫的不好，大家多擔待，理解過程就行了。好了，對于上圖中的步驟，我們用偽代碼來實現：

while(!que.empty()) { int n = que.front(); // 得到隊頭元素 que.pop(); // 隊頭元素出隊列 // 如果當前節點的右子樹不為空，那么輸出節點的數值，并且在隊尾插入左右子節點 if(tree[n].w != NULL) { cout << tree[n].w; que.push(tree[n].leftChild); que.push(tree[n].rightChild); }}

Ok，下面來看一下這幾個遍歷算法的最終代碼：

/* * 二叉樹的四種遍歷方式，這里沒有采用真實的指針去做， * 而是采用數組下標去模擬指針，是一種更加方便快速的方法 */#include <iostream>#include <queue> using namespace std;const int N = 10010;const int INF = -1; // 我們用一個常數來表示當前二叉樹節點為空的情況 struct Node { int w; // 當前樹節點的值 int p; // 當前樹節點的雙親所在數組下標 int l; // 當前樹節點的左子節點所在數組下標 int r; // 當前樹節點的右子節點所在數組下標 }; Node node[N];// 按照前序遍歷二叉樹的順序輸入樹節點 void input(int n) { cin >> node[n].w; if(node[n].w == INF) { // 輸入 -1 代表當前節點所在子二叉樹停止輸入 return ; } node[n].p = n / 2; node[n].l = n * 2; node[n].r = n * 2 + 1; input(n*2); input(n*2+1);}// 前序遍歷二叉樹 void preOrderParse(int n) { if(node[n].w == INF) { return ; } cout << node[n].w << " "; preOrderParse(node[n].l); preOrderParse(node[n].r);} // 中序遍歷二叉樹 void inOrderParse(int n) { if(node[n].w == INF) { return ; } inOrderParse(n*2); cout << node[n].w << " "; inOrderParse(n*2+1); }// 后續遍歷二叉樹 void postOrderParse(int n) { if(node[n].w == INF) { return ; } postOrderParse(n*2); postOrderParse(n*2+1); cout << node[n].w << " ";} /* * 層序遍歷二叉樹，這里采用的是 C++ STL 模板的提供的隊列(queue)， * 并沒有自己去實現一個隊列 */ void sequenceParse() { queue<int> que; int n = 1; que.push(1); // 插入根節點所在數組下標 while(!que.empty()) { n = que.front(); que.pop(); // 得到隊頭元素并且將隊頭元素出隊列 // 如果當前節點不為空，那么輸出該節點，并且將該節點的左右子節點插入隊尾 if(node[n].w != INF) { cout << node[n].w << " "; que.push(node[n].l); que.push(node[n].r); } }}int main() { cout << "請以前序遍歷的順序輸入二叉樹，空節點輸入 -1 ：" << endl; input(1); // 從下標為 1 開始前序輸入二叉樹 cout << "前序遍歷：" << endl; preOrderParse(1); cout << endl << "中序遍歷：" << endl; inOrderParse(1); cout << endl << "后序遍歷：" << endl; postOrderParse(1); cout << endl << "層序遍歷：" << endl; sequenceParse(); return 0;}

結果：

這里寫圖片描述