C語言中怎么遍歷二叉樹

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

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

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

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

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

前序遍歷：ABCDEFGHK

中序遍歷：BDCAEHGKF

后序遍歷：DCBHKGFEA

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

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

節(jié)點定義：

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

先序遍歷

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

先序遍歷：先訪問根節(jié)點，然后訪問左孩子，最后訪問右孩子。

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

下面，我們來看看具體代碼實現(xiàn)

1.遞歸實現(xiàn)

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

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

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

具體實現(xiàn)：

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

3.Morris遍歷

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

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

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

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

具體實現(xiàn)：

void preOrder(TreeNode* root){  if (root == NULL)    return;  TreeNode* pNode = root;  while(pNode != NULL){    if (pNode->left == NULL)    {      cout<<pNode->val<<endl;      pNode = pNode->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<<pNode->val<<endl;        pNode = pNode->left;      }      else{        pPre->right = NULL;        pNode = pNode->right;      }    }  }}

中序遍歷

中序遍歷：先訪問左孩點，然后訪問根節(jié)點，最后訪問右孩子。

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

下面，我們來看看具體代碼實現(xiàn)

1.遞歸實現(xiàn)

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

2.使用輔助棧

實現(xiàn)思路：

初始化一個二叉樹結(jié)點pNode指向根結(jié)點；

若pNode非空，那么就把pNode入棧，并把pNode變?yōu)槠渥蠛⒆?；（直到最左邊的結(jié)點）

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

具體實現(xiàn)：

void InOrder(TreeNode *root){  if (root==NULL)  {    return;  }  stack<TreeNode*> 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<<pNode->val<<endl;      pNode = pNode->right;    }  }}

3.Morris遍歷

實現(xiàn)思路：

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

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

當(dāng)?shù)谝淮卧L問該前驅(qū)結(jié)點prev時，其右孩子必定為空，那么就將其右孩子設(shè)置為當(dāng)前結(jié)點，以便根據(jù)這個指針返回到當(dāng)前結(jié)點pNode中，并將當(dāng)前結(jié)點pNode設(shè)置為其左孩子；

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

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

具體實現(xiàn)：

void InOrder(TreeNode *root){  if (root == NULL)    return;  TreeNode* pNode = root;  while(pNode != NULL){    if (pNode->left == NULL)    {      cout<<pNode->val<<endl;      pNode = pNode->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<<pNode->val<<endl;        pNode = pNode->right;      }    }  }}

后序遍歷

后序遍歷：先訪問左孩子，然后訪問右孩子，最后訪問根節(jié)點。

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

下面，我們來看看具體代碼實現(xiàn)：

1.遞歸實現(xiàn)

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

2.使用輔助棧

void postOrder(TreeNode *root) {   if(root == NULL)    return;  stack<TreeNode *> 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;  }}

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

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

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

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

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

實現(xiàn)思路：

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

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

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

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

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

具體實現(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<<pNode->val<<endl;    if (pNode == p1)      break;    pNode = pNode->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語言中怎么遍歷二叉樹就分享到這里了，希望以上內(nèi)容可以對大家有一定的幫助，可以學(xué)到更多知識。如果覺得文章不錯，可以把它分享出去讓更多的人看到。