二叉樹遍歷

來自專欄良哥說IT2 人贊了文章

二叉搜索樹的遍歷

遍歷即將樹的所有結點訪問且僅訪問一次。按照根節點位置的不同主要分為前序遍歷，中序遍歷，後序遍歷。注意，二叉搜索樹和普通的二叉樹其遍歷是一模一樣的，因此下文中，不區分是二叉搜索樹還是二叉樹。

前序遍歷

對一顆二叉樹的前序遍歷操作如下：

• 訪問根節點
• 前序遍歷左子樹
• 前序遍歷右子樹

例如下圖中二叉樹前序遍歷節點訪問順序為3 1 2 5 4 6：

根據前面所分析的前序遍歷的操作步驟，不難看出很容易用遞歸的方法實現二叉樹的前序訪問：

//前序遍歷遞歸版本void preOrder(struct node *root){ if(root != NULL) { cout << root->data << " "; preOrder(root->left); preOrder(root->right); }}

其實，還能以非遞歸的方式實現二叉樹的前序遍歷：由於在遍歷完根節點後還要將其找回來以便遍歷該根節點對應的右子樹，因此可以考慮使用棧來存儲訪問過的根節點，代碼實現如下：

//前序遍歷的非遞歸版本void preOrder(struct node *root) { stack<struct node *> s; while (root != NULL || !s.empty()) { if (root != NULL) { //訪問結點併入棧 cout << root->data << " "; s.push(root); root = root->left; //訪問左子樹 } else { root = s.top(); //回溯至父親結點 s.pop(); root = root->right; //訪問右子樹 } } cout << endl; }

中序遍歷

對一顆二叉樹的中序遍歷操作如下：

• 中序遍歷左子樹
• 訪問根節點
• 中序遍歷右子樹

例如下圖中二叉樹中序遍歷節點訪問順序為1 2 3 4 5 6：

如同前序遍歷一樣，也可以用遞歸或者非遞歸的方式實現，而且其思想也類似，只是訪問的順序不一樣了，其兩種實現方式如下：

//中序遍歷遞歸版本void inOrder(struct node *root){ if(root != NULL) { inOrder(root->left); //和前序遍歷相比，只是輸出語句換了個位置唯一 cout << root->data << " "; inOrder(root->right); }}

//中序遍歷的非遞歸版本void inOrder(struct node *root) { stack<struct node *> s; while (root != NULL || !s.empty()) { if (root != NULL) { s.push(root); root = root->left; } else { //訪問完左子樹後才訪問根結點 root = s.top(); cout << root->data << " "; s.pop(); root = root->right; //訪問右子樹 } } cout << endl; }

後續遍歷

對一顆二叉樹的後序遍歷操作如下：

• 後序遍歷左子樹
• 後序遍歷右子樹
• 訪問根節點

例如下圖中二叉樹後序遍歷節點訪問順序為2 1 4 6 5 3：

二叉樹後序遍歷遞歸版本與前序中序類似，如下：

//後序遍歷遞歸版本void postOrder(struct node *root){ if(root != NULL) { postOrder(root->left); postOrder(root->right); //最後訪問根節點 cout << root->data << " "; }}

後序遍歷的非遞歸演算法較複雜，使用一個棧可以實現，但是過程很繁瑣，我們可以考慮用兩個棧來實現後序遍歷的非遞歸演算法。注意到後序遍歷可以看作是下面遍歷的逆過程：即先遍歷某個結點，然後遍歷其右孩子，然後遍歷其左孩子。這個過程逆過來就是後序遍歷。演算法步驟如下：

(1) push根結點到第一個棧s中。

(2) 從棧s中pop一個結點，將其push到棧output中。

(3) 然後push結點的左孩子和右孩子到第一個棧s中。

(4) 重複過程2和3直到棧s為空。

(5) 現在所有結點已經push到棧output中，且按照後序遍歷的順序存放，直接全部 pop出來即是二叉樹後序遍歷結果。

代碼實現如下：

//後序遍歷的非遞歸版本void postOrder(struct node *root) { if (!root) return; stack<struct node*> s, output; s.push(root); while (!s.empty()) { struct node *curr = s.top(); output.push(curr); s.pop(); if (curr->left) s.push(curr->left); if (curr->right) s.push(curr->right); } while (!output.empty()) { cout << output.top()->data << " "; output.pop(); } cout << endl; }

掃描文章上方二維碼，加入演算法交流群，和更多大佬一起聊技術