C語言二叉樹的三種遍歷方式的實(shí)現(xiàn)及原理

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

成都創(chuàng)新互聯(lián)公司主營(yíng)企業(yè)營(yíng)銷型網(wǎng)站建設(shè)，為眾多企業(yè)提供了品牌網(wǎng)站制作服務(wù)，建網(wǎng)站哪家好？擁有多年的網(wǎng)絡(luò)營(yíng)銷推廣流程，能夠?yàn)槠髽I(yè)定制化制作網(wǎng)站服務(wù)，在公司網(wǎng)站建設(shè)維護(hù)方面成績(jī)突出。

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

C語言二叉樹的三種遍歷方式的實(shí)現(xiàn)及原理

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

前序遍歷：ABCDEFGHK

中序遍歷：BDCAEHGKF

后序遍歷：DCBHKGFEA

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

C語言二叉樹的三種遍歷方式的實(shí)現(xiàn)及原理

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

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

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

先序遍歷

C語言二叉樹的三種遍歷方式的實(shí)現(xiàn)及原理

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

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

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

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

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

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

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

實(shí)現(xiàn)思路：1.將根節(jié)點(diǎn)入棧
　　　　　　 2.每次從棧頂彈出一個(gè)節(jié)點(diǎ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<TreeNode*> stk; //開辟一個(gè)?？臻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)時(shí)間內(nèi)完成二叉樹的遍歷。

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

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

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

具體實(shí)現(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;
      }
    }
  }
}

中序遍歷

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

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

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

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

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

2.使用輔助棧

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

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

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

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

具體實(shí)現(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遍歷

實(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問該前驅(qū)結(jié)點(diǎn)prev時(shí)，其右孩子必定為空，那么就將其右孩子設(shè)置為當(dāng)前結(jié)點(diǎn)，以便根據(jù)這個(gè)指針返回到當(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ù)樹的結(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<<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é)點(diǎn)。

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

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

1.遞歸實(shí)現(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;
  }
}

雙輔助棧實(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)，并訪問之。

第一個(gè)棧的入棧順序是：根結(jié)點(diǎn)，左孩子和右孩子；于是，壓入第二個(gè)棧的順序是：根結(jié)點(diǎn)，右孩子和左孩子。

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

void PostOrder2(TreeNode *root){ //兩個(gè)棧實(shí)現(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é)點(diǎn)壓棧
    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遍歷實(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ù)以上過程，直到當(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<<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;
      }
    }
  }
}

總結(jié)

上述三種遍歷方式時(shí)間復(fù)雜度和空間復(fù)雜度分析：

1.遞歸遍歷和非遞歸遍歷時(shí)間復(fù)雜度0(n) 空間復(fù)雜度O(n)

2.Morris遍歷時(shí)間復(fù)雜度0(n) 空間復(fù)雜度O(1)

以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持創(chuàng)新互聯(lián)。

網(wǎng)站題目：C語言二叉樹的三種遍歷方式的實(shí)現(xiàn)及原理
鏈接分享：http://muchs.cn/article40/gdspho.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App設(shè)計(jì)、建站公司、網(wǎng)站內(nèi)鏈、網(wǎng)站導(dǎo)航、App開發(fā)、

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源：創(chuàng)新互聯(lián)

猜你還喜歡下面的內(nèi)容

php刪除最后一個(gè)逗號(hào)的方法
Android軟件缺陷管理有哪些
怎么解決Tomcat亂碼
如何理解javaModule模塊化
批量創(chuàng)建數(shù)據(jù)庫(kù)和批量數(shù)據(jù)恢復(fù)
C#ref、out修飾方法的參數(shù)
js布局如何實(shí)現(xiàn)單選按鈕控件