• 遞歸遍歷：

二叉樹的三種遞歸遍歷為先序遍歷，中序遍歷和后續遍歷。它們相似之處在于都是對二叉樹的遞歸遍歷且對任何一個結點都經過三次，區別之處在于哪一次對該結點進行訪問，由此分為先，中，后序遍歷。所以對于任一結點都有：三次經過，一次訪問。

先序遍歷：

僅以先序遍歷為例說明其思路。

當我們對二叉樹進行遍歷時，先對該結點內的數據進行訪問，然后依次遍歷它的左右孩子結點，遞歸進行直至結束。

例：對一個有三個結點的二叉樹，包含根結點A，左孩子結點B和右孩子結點C。先序遍歷的函數執行過程如下：（下面的字母和數字表示函數的執行步驟）

第一次函數調用：A，訪問根結點中的數據，遞歸調用左孩子結點B，遞歸調用右孩子結點C。

第二次函數調用左孩子結點 B：訪問左孩子結點內的數據，遞歸調用左孩子結點的左孩子結點B->left，遞歸調用左孩子結點的右孩子結點B->right。

第三次函數調用左孩子的左孩子結點B->left：該結點為空，不執行。返回第二次函數調用。

第四次函數調用左孩子的右孩子結點B->right：該結點為空，不執行。返回第二次函數調用。第二次函數調用執行完畢，返回第一次函數調用中。

第五次函數調用右孩子結點 C：訪問右孩子結點內數據，遞歸調用右孩子結點的左孩子結點C->left，遞歸調用右孩子結點的右孩子結點C->right。

第六次函數調用右孩子的左孩子結點C->left：該結點為空，不執行。返回第五次函數調用。

第七次函數調用右孩子的右孩子結點C->right：該結點為空，不執行。返回第五次函數調用。第五次函數調用執行完畢，返回第一次函數調用。

第一次函數調用執行完畢。遞歸結束。

void preorder(btNode* p) {if (p != NULL){visit(p);preorder(p->lc);preorder(p->rc);} }

中序遍歷：

void inorder(btNode* p) {if (p != NULL){inorder(p->lc);visit(p);inorder(p->rc);} }

后序遍歷：

void postorder(btNode* p) {if (p != NULL){postorder(p->lc);postorder(p->rc);visit(p);} }

對于下圖中的樹：

先序遍歷結果為：ABDECF ? 根 ? 左 ? 右

中序遍歷結果為：DBEAFC ? 左 ? 根 ? 右

后序遍歷結果為：DEBFCA ? 左 ? 右 ? 根

中序與先（后）序可唯一確定一顆二叉樹。

• 層序遍歷：

二叉樹的層序遍歷的實現思路：

建立一個輔助數據結構隊列，在此采用大小為10的循環隊列。初始先將二叉樹根節點入隊，從而使得隊列不為空，接下來進入到循環中，當隊列不為空時，隊列中元素出隊，訪問出隊元素中的數據，并在出隊時將其左右孩子挨個入隊，每出隊一個結點，將其左右孩子分別入隊，直至隊列為空，此時所有結點都被訪問過了。

void level(btNode* p) {int front, rear;front = rear = 0;btNode* que[10];//構造一個大小為10的簡單循環隊列if (p != NULL){rear = (rear + 1) % 10;que[rear] = p;while (rear != front){front = (front + 1) % 10;std::cout << que[front]->data << ' ';//出隊時進行輸出或進行操作if (que[front]->lc != NULL){rear = (rear + 1) % 10;que[rear] = que[front]->lc;}if (que[front]->rc != NULL){rear = (rear + 1) % 10;que[rear] = que[front]->rc;}}} }

關于樹的遍歷完整代碼如下：

#include<iostream> typedef struct btNode {char data;//結點中的信息struct btNode* lc;//左孩子結點struct btNode* rc;//右孩子結點 }btNode;btNode* initial(char* ele, int num);//用數組初始化一棵樹（默認創建一棵完全二叉樹） void preorder(btNode* p);//先序遍歷 void inorder(btNode* p);//中序遍歷 void postorder(btNode* p);//后續遍歷 void level(btNode* p);//層序遍歷 int main() {using namespace std;char data[6] = { 'a', 'b', 'c', 'd', 'e', 'f' };btNode* p = initial(data, 6);cout << "先序遍歷： ";preorder(p);cout << endl;cout << "中序遍歷： ";inorder(p);cout << endl;cout << "后序遍歷： ";postorder(p);cout << endl;cout << "層序遍歷： ";level(p);cout << endl;return 0; } btNode* initial(char* ele, int num) {if (num<1)return NULL;btNode* temp = new btNode[num];int i = 0;while (i < num)//將所有結點的左右子樹置為空{temp[i].lc = NULL;temp[i].rc = NULL;++i;}i = 0;while (i < num/2)//通過完全二叉樹的順序存儲來創建樹的結構{if (2*i+1<num)temp[i].lc = temp + 2 * i + 1;if (2*i+2<num)temp[i].rc = temp + 2 * i + 2;++i;}for (i = 0; i < num; i++)//對樹中的每個結點賦值temp[i].data = ele[i];return temp; } void preorder(btNode* p) {if (p != NULL){std::cout << p->data << ' ';preorder(p->lc);preorder(p->rc);} } void inorder(btNode* p) {if (p != NULL){inorder(p->lc);std::cout << p->data << ' ';inorder(p->rc);} } void postorder(btNode* p) {if (p != NULL){postorder(p->lc);postorder(p->rc);std::cout << p->data << ' ';} } void level(btNode* p) {int front, rear;front = rear = 0;btNode* que[10];if (p != NULL){rear = (rear + 1) % 10;que[rear] = p;while (rear != front){front = (front + 1) % 10;std::cout << que[front]->data << ' ';if (que[front]->lc != NULL){rear = (rear + 1) % 10;que[rear] = que[front]->lc;}if (que[front]->rc != NULL){rear = (rear + 1) % 10;que[rear] = que[front]->rc;}}} }

其中數組中的輸入為下圖中的樹：

程序的輸出結果為：

二叉樹非遞歸遍歷可參考：

二叉樹的非遞歸遍歷（c/c++）_Little_ant_的博客-CSDN博客

總結

以上是生活随笔為你收集整理的二叉树的递归遍历和层序遍历（c/c++）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。