文章目錄

• 一：二叉樹遍歷概述
• 二：二叉樹深度優先遍歷
• • （1）先序遍歷-根左右(NLR)
  • （2）中序遍歷-左根右(LNR)
  • （3）后序遍歷-左右根(LRN)
  • 總結：三種遍歷方式動圖演示
• 三：二叉樹的層序遍歷

一：二叉樹遍歷概述

二叉樹遍歷（traversing binary tree）：從根節點開始，按照某種次序依次訪問二叉樹中的所有結點，使得每個結點被訪問一次且僅被訪問一次

• 訪問： 訪問是一個抽象操作，是指具體你遍歷到這個節點應該做什么？比如說最簡單的打印，修改值等等
• 次序：二叉樹的遍歷有別于普通線性結構，因為樹的結點之間不存在唯一的前驅和后繼的關系，下一個被訪問的結點面臨著不同的選擇。由于選擇的方式不同，遍歷的次序也就不同了

二：二叉樹深度優先遍歷

大部分人其實都知道一些二叉樹的遍歷的口訣，例如

• 先序遍歷是“根左右”；
• 中序遍歷是“左根右”;
• 后序遍歷是“左右根“”;

通過這樣的口訣，能夠很快的寫出樹的各種遍歷次序，但如果問到為什么是這樣，很多人卻無法說清楚。

其實呈現出不同遍歷方式的根本原因在于二叉樹的遞歸結構和訪問時機的不同

如下圖，這三種遍歷方式本質是一樣的，每個結點都會經歷三次訪問，二叉樹默認遞歸時其實就是先序遍歷，也就是先根節點，再左，后右。而在不同時機訪問，就會造成不同的遍歷結果

（1）先序遍歷-根左右(NLR)

先序遍歷：第一次遇到這個結點訪問，第二次遇到或第三次遇到時跳過該結點直接訪問下一個結點

• 也即若二叉樹為空，則返回空，否則先訪問根節點，然后先序遍歷左子樹，再先序遍歷右子樹

先序遍歷算法：二叉樹定義采用的遞歸形式，所以其遍歷代碼也可以采用遞歸，形式極其簡單

void PreOrderTraverse(BTNode* root) {if(root==NULL)return NULL;printf("%c",root->data);//結點訪問操作，也可以是其他PreOrderTraverse(BTNode->lchild);//再先序遍歷左子樹PreOrderTraverse(BTNode->rchild);//最后先序遍歷右子樹}

接下來，我們用下面的樹來說明上述代碼是怎樣執行的

• 1：首先調用了PreOrderTraverse(A)，由于根節點A不為空，所以執行了printf，字母A被打印
  

• 2：接著調用了PreOrderTraverse(A->lchild)，由于根節點A的左孩子不為空，所以執行了printf，字母B被打印
  

• 3：接著調用了PreOrderTraverse(B->lchild)，由于結點B的左孩子不為空，所以執行了printf，字母D被打印
  

• 4：接著調用了PreOrderTraverse(D->lchild)，由于結點D的左孩子不為空，所以執行了printf，字母H被打印
  

• 5：接著調用了PreOrderTraverse(H->lchild)，但此時結點H沒有左孩子，所以被調函數傳入root==NULL，直接return NULL;PreOrderTraverse(H->lchild)于是直接結束，立馬執行PreOrderTraverse(H->rchild)，執行了printf，字母K被打印
  

• 6：接著調用了PreOrderTraverse(K->lchild)，訪問K結點左孩子，但沒有左孩子，所以調用后直接返回了NULL，然后調用PreOrderTraverse(K->rchild)，但沒有右孩子，所以調用后直接返回了NULL。那么這就導致PreOrderTraverse(H->rchild)函數的結束，而PreOrderTraverse(H->rchild)的結束就導致了PreOrderTraverse(D->lchild)，于是會執行PreOrderTraverse(D->rchild)，但沒有右孩子，從而導致了PreOrderTraverse(B->lchild)函數的結束，于是繼續執行PreOrderTraverse(B->rchild)，執行了printf，字母E被打印
  

• 7：對于結點E來說，它也沒有左右孩子，所以訪問完成之后PreOrderTraverse(B->rchild)結束，它的結束自然導致了PreOrderTraverse(A->lchild)的結束，于是A的左子樹訪問完畢，現在開始右子樹，因此PreOrderTraverse(A->rchild)，執行了printf，字母C被打印
  

• 8：后續訪問過程不再贅述。遍歷結果為$A?B?D?H?K?E?C?F?I?G?J$

（2）中序遍歷-左根右(LNR)

中序遍歷：第一次遇到結點跳過，第二次再遇到結點訪問，第三次遇到跳過

• 也即若樹為空，則返回空，否則從根節點開始（注意并不是先訪問根節點），中序遍歷根節點的左子樹，然后是訪問根節點，最后中序遍歷右子樹

中序遍歷算法：二叉樹定義采用的遞歸形式，所以其遍歷代碼也可以采用遞歸，形式極其簡單

void InOrderTraverse(BTNode* root) {if(root==NULL)return NULL;InOrderTraverse(BTNode->lchild);//中序遍歷左子樹printf("%c",root->data);//結點訪問操作，也可以是其他InOrderTraverse(BTNode->rchild);//中序遍歷右子樹}

接下來，我們用下面的樹來說明上述代碼是怎樣執行的

• 1：首先調用InOrderTraverse(A)，結點A不為空，于是再調用InOrderTraverse(A->lchild)，對于B來說也不空，于是再調用InOrderTraverse(B->lchild)，對于D來說也不空，于是再調用InOrderTraverse(D->lchild)。對于結點H，當其調用InOrderTraverse(H->lchild)時，由于其左孩子為空，因此會返回NULL，然后執行了printf，字母H被打印
  

• 2：然后調用InOrderTraverse(H->rchild)，訪問H的右孩子K，然后執行InOrderTraverse(K->lchild)，但其左孩子為空所以返回NULL，然后執行了printf，字母K被打印
  

• 3：然后InOrderTraverse(K->rchild)，但K沒有右孩子，所以這直接導致InOrderTraverse(H->rchild)的結束，接著導致了InOrderTraverse(D->lchild)，然后執行了printf，字母D被打印
  

• 4：然后調用InOrderTraverse(D->rchild)，但D沒有右孩子所以返回NULL，這直接導致了InOrderTraverse(B->lchild)的結束，然后執行了printf，字母B被打印
  

• 5：然后調用InOrderTraverse(B->rchild)，接著再調用InOrderTraverse(E->lchild)，但E沒有左孩子所以返回NULL，然后執行了printf，字母E被打印
  

• 6：然后調用InOrderTraverse(E->rchild)，但E沒有右孩子所以返回NULL，這就導致了InOrderTraverse(B->rchild)的結束，繼而導致了InOrderTraverse(A->lchild)的結束，然后執行了printf，字母A被打印
  

• 7：然后調用InOrderTraverse(A->rchild)，開始A的右子樹的遍歷過程

• 8：后續訪問過程不再贅述。遍歷結果為$H?K?D?B?E?A?I?F?C?G?J$

（3）后序遍歷-左右根(LRN)

后序遍歷：前兩次遇見結點不訪問，最后一次遇見時訪問

• 也即若樹為空，則返回空。否則從左到右先葉子后結點的方式遍歷訪問左右子樹，最后根節點

后序遍歷算法：二叉樹定義采用的遞歸形式，所以其遍歷代碼也可以采用遞歸，形式極其簡單

void PostnOrderTraverse(BTNode* root) {if(root==NULL)return NULL;PostOrderTraverse(BTNode->lchild);//后序遍歷左子樹PostOrderTraverse(BTNode->rchild);//后序遍歷右子樹printf("%c",root->data);//結點訪問操作，也可以是其他}

后序遍歷大家可以自己推導一下

• 結果為：$K?H?D?E?B?I?F?J?G?C?A$

總結：三種遍歷方式動圖演示

本人在初學數據結構時，對于三個地方理解的不是特別深入，其中有一個便是二叉樹的遞歸，就如空中樓閣一般，感覺明白了，其實沒有明白，這種感覺相信大家深有體會，的確不好受。不過在接觸了很多和遞歸算法相關的題目及案例后，對于其理解確實有了一定的進步

所以我相信對于很多人來說，遞歸這一部分的理解也不是很到位（除大佬外），而天勤相較于王道來說，對于遞歸這一部分講解確實很不錯，人家把遞歸一層層的為我們剖析開來了。下面的圖取自其視頻課，質量不高（因為圖片有大小限制，進行了很多次壓縮），但是確實是一幀一幀的錄制的，希望可以對大家的理解有所幫助

先序遍歷

中序遍歷

后序遍歷

三：二叉樹的層序遍歷

層次遍歷：需要借助隊列完成。若樹為空，則返回空，然后從上至下，從左至右依次訪問結點

• 初始化一個輔助隊列
• 根結點入隊
• 若隊列非空，則隊頭結點出隊，訪問該結點，然后將其左、右孩子（如果有）插入隊尾
• 重復第三步，直至隊列為空

具體過程如下圖

代碼如下

void LevelOrder(BTNode* root) {LinkQueue Q;InitQueue(Q);BTNode* p;//輔助結點EnQueue(Q,root);//先將根節點入隊列while(isEmpty(Q)){DeQueue(Q,p);//出隊列，p拿到結點visit(p);if(p->lchild!=NULL)EnQueue(Q,p->lchild);if(p->rchild!=NULL)EnQueue(Q,p->rchild);} } 新人創作打卡挑戰賽發博客就能抽獎！定制產品紅包拿不停！

總結

以上是生活随笔為你收集整理的(王道408考研数据结构)第五章树-第三节1：二叉树遍历（先序、中序和后序）的全部內容，希望文章能夠幫你解決所遇到的問題。

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