這篇文章給大家介紹C語(yǔ)言中怎么遍歷二叉樹(shù)，內(nèi)容非常詳細(xì)，感興趣的小伙伴們可以參考借鑒，希望對(duì)大家能有所幫助。

站在用戶(hù)的角度思考問(wèn)題，與客戶(hù)深入溝通，找到蘇州網(wǎng)站設(shè)計(jì)與蘇州網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶(hù)體驗(yàn)好的作品，建站類(lèi)型包括：網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站設(shè)計(jì)、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、域名申請(qǐng)、雅安服務(wù)器托管、企業(yè)郵箱。業(yè)務(wù)覆蓋蘇州地區(qū)。

二叉樹(shù)遍歷分為三種：前序、中序、后序，其中序遍歷最為重要。為啥叫這個(gè)名字？是根據(jù)根節(jié)點(diǎn)的順序命名的。

比如上圖正常的一個(gè)滿(mǎn)節(jié)點(diǎn)，A：根節(jié)點(diǎn)、B：左節(jié)點(diǎn)、C：右節(jié)點(diǎn)，前序順序是ABC（根節(jié)點(diǎn)排最先，然后同級(jí)先左后右）；中序順序是BAC(先左后根最后右）；后序順序是BCA（先左后右最后根）。

比如上圖二叉樹(shù)遍歷結(jié)果

前序遍歷：ABCDEFGHK

中序遍歷：BDCAEHGKF

后序遍歷：DCBHKGFEA

分析中序遍歷如下圖，中序比較重要（java很多樹(shù)排序是基于中序，后面講解分析）

下面介紹一下，二叉樹(shù)的三種遍歷方式，其中每一種遍歷方式都有三種實(shí)現(xiàn)方式。

節(jié)點(diǎn)定義：

struct TreeNode{  int val;  TreeNode *left,*right;  TreeNode(int val){    this->val = val;    this ->left = this->right = NULL;  }};

先序遍歷

以上面這張圖為例：我們講講樹(shù)的三種遍歷方式：

先序遍歷：先訪(fǎng)問(wèn)根節(jié)點(diǎn)，然后訪(fǎng)問(wèn)左孩子，最后訪(fǎng)問(wèn)右孩子。

所以，上面遍歷的結(jié)果是：GEDACHS。

下面，我們來(lái)看看具體代碼實(shí)現(xiàn)

1.遞歸實(shí)現(xiàn)

void preOrder(TreeNode *root){  if (root==NULL)    return;  cout<val<left);  preOrder(root->right);}

2.使用輔助?！?/strong>　

實(shí)現(xiàn)思路：1.將根節(jié)點(diǎn)入?！　　　　　?2.每次從棧頂彈出一個(gè)節(jié)點(diǎn)，訪(fǎng)問(wèn)該節(jié)點(diǎn)　　　　　　 3.把當(dāng)前節(jié)點(diǎn)的右孩子入棧　　　　　　 4.把當(dāng)前節(jié)點(diǎn)的左孩子入棧

具體實(shí)現(xiàn)：

void preOrder2(TreeNode *root){  if (root == NULL)    return;  stack stk; //開(kāi)辟一個(gè)?？臻g  stk.push(root);  while(!stk.empty()){    TreeNode* pNode = stk.pop();    cout<val;    if (pNode->right!=NULL)      stk.push(pNode->right);    if (pNode->left!=NULL)      stk.push(pNode->left);  }}

3.Morris遍歷

Morris遍歷，常數(shù)的空間即可在O(n)時(shí)間內(nèi)完成二叉樹(shù)的遍歷。

O(1)空間進(jìn)行遍歷困難之處在于在遍歷的子結(jié)點(diǎn)的時(shí)候如何重新返回其父節(jié)點(diǎn)？

在Morris遍歷算法中，通過(guò)修改葉子結(jié)點(diǎn)的左右空指針來(lái)指向其前驅(qū)或者后繼結(jié)點(diǎn)來(lái)實(shí)現(xiàn)的。

其本質(zhì)：線(xiàn)索二叉樹(shù)（Threaded Binary Tree)，通過(guò)利用葉子節(jié)點(diǎn)空的right指針，指向中序遍歷的后繼節(jié)點(diǎn)，從而避免了對(duì) stack 的依賴(lài)。

具體實(shí)現(xiàn)：

void preOrder(TreeNode* root){  if (root == NULL)    return;  TreeNode* pNode = root;  while(pNode != NULL){    if (pNode->left == NULL)    {      cout<val<right;    }    else{      TreeNode* pPre = pNode->left;      while(pPre->right != NULL && pPre->right != pNode){        pPre = pPre->right;      }      if (pPre->right == NULL)      {        /* code */        pPre->right = pNode;        cout<val<left;      }      else{        pPre->right = NULL;        pNode = pNode->right;      }    }  }}

中序遍歷

中序遍歷：先訪(fǎng)問(wèn)左孩點(diǎn)，然后訪(fǎng)問(wèn)根節(jié)點(diǎn)，最后訪(fǎng)問(wèn)右孩子。

所以，上面遍歷的結(jié)果是：DEAGHCS。

下面，我們來(lái)看看具體代碼實(shí)現(xiàn)

1.遞歸實(shí)現(xiàn)

void InOrder(TreeNode *root){  if (root==NULL)    return;  InOrder(root->left);  cout<val<right);}

2.使用輔助棧

實(shí)現(xiàn)思路：

初始化一個(gè)二叉樹(shù)結(jié)點(diǎn)pNode指向根結(jié)點(diǎn)；

若pNode非空，那么就把pNode入棧，并把pNode變?yōu)槠渥蠛⒆樱唬ㄖ钡阶钭筮叺慕Y(jié)點(diǎn)）

若pNode為空，彈出棧頂?shù)慕Y(jié)點(diǎn)，并訪(fǎng)問(wèn)該結(jié)點(diǎn)，將pNode指向其右孩子（訪(fǎng)問(wèn)最左邊的結(jié)點(diǎn)，并遍歷其右子樹(shù)）

具體實(shí)現(xiàn)：

void InOrder(TreeNode *root){  if (root==NULL)  {    return;  }  stack stk;  TreeNode *pNode = root;  while(pNode!=NULL || !stk.empty()){    if (pNode != NULL)    {      stk.push(pNode);      pNode = pNode->left;    }    else{      pNode = stk.pop();      stk.pop();      cout<val<right;    }  }}

3.Morris遍歷

實(shí)現(xiàn)思路：

1.如果當(dāng)前節(jié)點(diǎn)pNode的左孩子為空，那么輸出該節(jié)點(diǎn)，并把該節(jié)點(diǎn)的右孩子作為當(dāng)前節(jié)點(diǎn)

2.如果當(dāng)前節(jié)點(diǎn)pNode的左孩子非空，那么找出該節(jié)點(diǎn)在中序遍歷的前驅(qū)結(jié)點(diǎn)prev

當(dāng)?shù)谝淮卧L(fǎng)問(wèn)該前驅(qū)結(jié)點(diǎn)prev時(shí)，其右孩子必定為空，那么就將其右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，以便根據(jù)這個(gè)指針?lè)祷氐疆?dāng)前結(jié)點(diǎn)pNode中，并將當(dāng)前結(jié)點(diǎn)pNode設(shè)置為其左孩子；

當(dāng)該前驅(qū)結(jié)點(diǎn)pPre的右孩子為當(dāng)前結(jié)點(diǎn)，那么就輸出當(dāng)前結(jié)點(diǎn)，并把前驅(qū)結(jié)點(diǎn)的右孩子設(shè)置為空（恢復(fù)樹(shù)的結(jié)構(gòu)），將當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子；

3.重復(fù)以上兩步，直到當(dāng)前結(jié)點(diǎn)為空。

具體實(shí)現(xiàn)：

void InOrder(TreeNode *root){  if (root == NULL)    return;  TreeNode* pNode = root;  while(pNode != NULL){    if (pNode->left == NULL)    {      cout<val<right;    }    else{      TreeNode* pPre = pNode->left;      while(pPre->right != NULL && pPre->right != pNode){        pPre = pPre->right;      }      if (pPre->right == NULL)      {        /* code */        pPre->right = pNode;        pNode = pNode->left;      }      else{        pPre->right = NULL;        cout<val<right;      }    }  }}

后序遍歷

后序遍歷：先訪(fǎng)問(wèn)左孩子，然后訪(fǎng)問(wèn)右孩子，最后訪(fǎng)問(wèn)根節(jié)點(diǎn)。

所以，上面遍歷的結(jié)果是：DAEHSCG。

下面，我們來(lái)看看具體代碼實(shí)現(xiàn)：

1.遞歸實(shí)現(xiàn)

void PostOrder(TreeNode *root){  if (root==NULL)    return;  PostOrder(root->left);  PostOrder(root->right);  cout<val<

2.使用輔助棧

void postOrder(TreeNode *root) {   if(root == NULL)    return;  stack stk;  stk.push(root);  TreeNode *prev = NULL;  while(!stk.empty()) {    TreeNode *pNode = stk.top();    if(!prev || prev->left == pNode || prev->right == pNode) { // traverse down      if(pNode->left)        stk.push(pNode->left);      else if(pNode->right)        stk.push(pNode->right);     /* else {        cout << pNode->val << endl;        stk.pop();      }    */    }    else if(pNode->left == prev) { // traverse up from left      if(pNode->right)        stk.push(pNode->right);    }  /* else if(pNode->right == prev) { // traverse up from right        cout << pNode->val << endl;        stk.pop();    }  */    else {      cout << pNode->val << endl;      stk.pop();    }    prev = pNode;  }}

雙輔助棧實(shí)現(xiàn)思路：

設(shè)置兩個(gè)棧stk, stk2；  將根結(jié)點(diǎn)壓入第一個(gè)棧stk；  彈出stk棧頂?shù)慕Y(jié)點(diǎn)，并把該結(jié)點(diǎn)壓入第二個(gè)棧stk2；  將當(dāng)前結(jié)點(diǎn)的左孩子和右孩子先后分別入棧stk；  當(dāng)所有元素都?jí)喝雜tk2后，依次彈出stk2的棧頂結(jié)點(diǎn)，并訪(fǎng)問(wèn)之。  第一個(gè)棧的入棧順序是：根結(jié)點(diǎn)，左孩子和右孩子；于是，壓入第二個(gè)棧的順序是：根結(jié)點(diǎn)，右孩子和左孩子。

因此，彈出的順序就是：左孩子，右孩子和根結(jié)點(diǎn)。

void PostOrder2(TreeNode *root){ //兩個(gè)棧實(shí)現(xiàn)  if (root == NULL)    return;  stack stk,stk2;  stk.push(root);  while(!stk.empty()){    TreeNode* pNode = stk.top();    stk.pop();    stk2.push(pNode);// 將根節(jié)點(diǎn)壓棧    if (pNode->left != NULL) // 如果左孩子不為空，則壓棧    {      stk.push(pNode->left);    }    if (pNode->right != NULL) // 如果左孩子不為空，則壓棧    {      stk.push(pNode->right);    }  }  while(!stk2.empty()){    cout<val<

3.Morris遍歷實(shí)現(xiàn)

實(shí)現(xiàn)思路：

1.先建立一個(gè)臨時(shí)結(jié)點(diǎn)dummy，并令其左孩子為根結(jié)點(diǎn)root，將當(dāng)前結(jié)點(diǎn)設(shè)置為dummy；

2.如果當(dāng)前結(jié)點(diǎn)的左孩子為空，則將其右孩子作為當(dāng)前結(jié)點(diǎn)；

3.如果當(dāng)前結(jié)點(diǎn)的左孩子不為空，則找到其在中序遍歷中的前驅(qū)結(jié)點(diǎn)，

-如果前驅(qū)結(jié)點(diǎn)的右孩子為空，將它的右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，將當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的左孩子；  -如果前驅(qū)結(jié)點(diǎn)的右孩子為當(dāng)前結(jié)點(diǎn)，倒序輸出從當(dāng)前結(jié)點(diǎn)的左孩子到該前驅(qū)結(jié)點(diǎn)這條路徑上所有的結(jié)點(diǎn)。將前驅(qū)結(jié)點(diǎn)的右孩子設(shè)置為空，將當(dāng)前結(jié)點(diǎn)更新為當(dāng)前結(jié)點(diǎn)的右孩子。

4.重復(fù)以上過(guò)程，直到當(dāng)前結(jié)點(diǎn)為空。

具體實(shí)現(xiàn)：

void reverse(TreeNode* p1,TreeNode *p2){  if (p1 == p2)    return;  TreeNode* x = p1;  TreeNode* y = p1->right;  while(true){    TreeNode* tmp = y->right;    y->right = x;    x = y;    y = tmp;    if (x == p2)      break;  }}

void printReverse(TreeNode* p1,TreeNode *p2){  reverse(p1,p2);  TreeNode* pNode = p2;  while(true){    cout<val<right;  }  reverse(p2,p1);}

void PostOrder3(TreeNode* root){  if(root == NULL)    return;  TreeNode *dummy = new TreeNode(-1);  dummy->left = root;  TreeNode *pNode = dummy;  while(pNode != NULL) {    if(pNode->left == NULL)      pNode = pNode->right;    else {      TreeNode *pPrev = pNode->left;      while(pPrev->right != NULL && pPrev->right != pNode)        pPrev = pPrev->right;      if(pPrev->right == NULL) {        pPrev->right = pNode;        pNode = pNode->left;      }      else {        printReverse(pNode->left, pPrev);        pPrev->right = NULL;        pNode = pNode->right;      }    }  }}

關(guān)于C語(yǔ)言中怎么遍歷二叉樹(shù)就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。