程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 二叉樹遍歷算法總結

二叉樹遍歷算法總結

編輯：關於C++

二叉樹遍歷算法總結

本文根據《數據結構與算法》(C語言版)(第三版) 整理。

A. 二叉樹的遍歷

1.前序遍歷二叉樹：

(1)若二叉樹為空，則為空操作，返回空。
(2)訪問根結點。
(3)前序遍歷左子樹。
(4)前序遍歷右子樹。

a.二叉樹前序遍歷的遞歸算法：

   void PreOrderTraverse(BiTree BT)
   {
     if(BT)
     {
        printf("%c",BT->data);              //訪問根結點
        PreOrderTraverse(BT->lchild);       //前序遍歷左子樹
        PreOrderTraverse(BT->rchild);       //前序遍歷右子樹
     }
   }

b.使用棧存儲每個結點右子樹的二叉樹前序遍歷的非遞歸算法：

(1)當樹為空時，將指針p指向根結點，p為當前結點指針。
(2)先訪問當前結點p，並將p壓入棧S中。
(3)令p指向其左孩子。
(4)重復執行步驟(2)、(3)，直到p為空為止。
(5)從棧S中彈出棧頂元素，將p指向此元素的右孩子。
(6)重復執行步驟(2)~(5)，直到p為空並且棧S也為空。
(7)遍歷結束。
使用棧的前序遍歷的非遞歸算法：

      void PreOrderNoRec(BiTree BT)
      {
        stack S;
        BiTree p=BT->root;
        while((NULL!=p)||!StackEmpty(S))
        {
          if(NULL!=p)
          {
            printf("%c",p->data);
            Push(S,p);
            p=p->lchild;
          }
          else
          {
            p=Top(S);
            Pop(S);
            p=p->rchild;
          }
        }
      }

c.使用二叉鏈表存儲的二叉樹前序遍歷非遞歸算法：

    void PreOrder(pBinTreeNode pbnode)
    {
      pBinTreeNode stack[100];
      pBinTreeNode p;
      int top;
      top=0;
      p=pbnode;
      do
      {
        while(p!=NULL)
        {
          printf("%d\n",p->data);      //訪問結點p
          top=top+1;
          stack[top]=p;
          p=p->llink;                  //繼續搜索結點p的左子樹
        }
        if(top!=0)
        {
          p=stack[top];
          top=top-1;
          p=p->rlink;                  //繼續搜索結點p的右子樹
        }
      }while((top!=0)||(p!=NULL));
    }

2.中序遍歷二叉樹：

(1)若二叉樹為空，則為空操作，返回空。
(2)中序遍歷左子樹。
(3)訪問根結點。
(4)中序遍歷右子樹。

a.二叉樹中序遍歷的遞歸算法：

    void InOrderTraverse(BiTree BT)
    {
      if(BT)
      {
         InOrderTraverse(BT->lchild);        //中序遍歷左子樹
         printf("%c",BT->data);              //訪問根結點
         InOrderTraverse(BT->rchild);        //中序遍歷右子樹
      }
    }

b.使用棧存儲的二叉樹中序遍歷的非遞歸算法：

(1)當樹為空時，將指針p指向根結點，p為當前結點指針。
(2)將p壓入棧S中，並令p指向其左孩子。
(3)重復執行步驟(2)，直到p為空。
(4)從棧S中彈出棧頂元素，將p指向此元素。
(5)訪問當前結點p，並將p指向其右孩子。
(6)重復執行步驟(2)~(5)，直到p為空並且棧S也為空。
(7)遍歷結束。
使用棧的中序遍歷的非遞歸算法：

     void IneOrderNoRec(BiTree BT)
     {
       stack S;
       BiTree p=BT->root;
       while((NULL!=p)||!StackEmpty(S))
       {
         if(NULL!=p)
         {
           Push(S,p);
           p=p->lchild;
         }
         else
         {
           p=Top(S);
           Pop(S);
           printf("%c",p->data);
           p=p->rchild;
         }
       }
     }

c.使用二叉鏈表存儲的二叉樹中序遍歷非遞歸算法：

    void InOrder(pBinTreeNode pbnode)
    {
         pBinTreeNode stack[100];
         pBinTreeNode p;
         int top;
         top=0;
         p=pbnode;
         do
         {
           while(p!=NULL)
           {
             top=top+1;
             stack[top]=p;                //結點p進棧
             p=p->llink;                  //繼續搜索結點p的左子樹
           }
           if(top!=0)
           {
             p=stack[top];                //結點p出棧
             top=top-1;
             printf("%d\n",p->data);      //訪問結點p
             p=p->rlink;                  //繼續搜索結點p的右子樹
           }
         }while((top!=0)||(p!=NULL));
    }

3.後序遍歷二叉樹：

(1)若二叉樹為空，則為空操作，返回空。
(2)後序遍歷左子樹。
(3)後序遍歷右子樹。
(4)訪問根結點。

a.二叉樹後序遍歷的遞歸算法：

     void PostOrderTraverse(BiTree BT)
     {
       if(BT)
       {
          PostOrderTraverse(BT->lchild);        //後序遍歷左子樹
          PostOrderTraverse(BT->rchild);        //後序遍歷右子樹
          printf("%c",BT->data);                //訪問根結點
       }
     }

b.使用棧存儲的二叉樹後序遍歷的非遞歸算法：

算法思想：首先掃描根結點的所有左結點並入棧，然後出棧一個結點，掃描該結點的右結點並入棧，再掃描該右結點的所有左結點並入棧，當一個結點的左、右子樹均被訪問後再訪問該結點。因為在遞歸算法中，左子樹和右子樹都進行了返回，因此為了區分這兩種情況，還需要設置一個標識棧tag，當tag的棧頂元素為0時表示從左子樹返回，為1表示從右子樹返回。
(1)當樹為空時，將指針p指向根結點，p為當前結點指針。
(2)將p壓入棧S中，0壓入棧tag中，並令p指向其左孩子。
(3)重復執行步驟(2)，直到p為空。
(4)如果tag棧中的棧頂元素為1，跳至步驟(6)。
(5)如果tag棧中的棧頂元素為0，跳至步驟(7)。
(6)將棧S的棧頂元素彈出，並訪問此結點，跳至步驟(8)。
(7)將p指向棧S的棧頂元素的右孩子。
(8)重復執行步驟(2)~(7)，直到p為空並且棧S也為空。
(9)遍歷結束。
使用棧的後序遍歷非遞歸算法：

       void PostOrderNoRec(BiTree BT)
       {
         stack S;
         stack tag;
         BiTree p=BT->root;
         while((NULL!=p)||!StackEmpty(S))
         {
           while(NULL!=p)
           {
             Push(S,p);
             Push(tag,0);
             p=p->lchild;
           }
           if(!StackEmpty(S))
           {
             if(Pop(tag)==1)
             {
               p=Top(S);
               Pop(S);
               printf("%c",p->data);
               Pop(tag);    //棧tag要與棧S同步
             }
             else
             {
               p=Top(S);
               if(!StackEmpty(S))
               {
                 p=p->rchild;
                 Pop(tag);
                 Push(tag,1);
               }
             }
           }
         }
       }

c.使用二叉鏈表存儲的二叉樹後序遍歷非遞歸算法：

     void PosOrder(pBinTreeNode pbnode)
     {
          pBinTreeNode stack[100];       //結點的指針棧
          int count[100];                //記錄結點進棧次數的數組
          pBinTreeNode p;
          int top;
          top=0;
          p=pbnode;
          do
          {
            while(p!=NULL)
            {
              top=top+1;
              stack[top]=p;                //結點p首次進棧
              count[top]=0;
              p=p->llink;                  //繼續搜索結點p的左子樹
            }
            p=stack[top];                  //結點p出棧
            top=top-1;
            if(count[top+1]==0)
            {
              top=top+1;
              stack[top]=p;                //結點p首次進棧
              count[top]=1;
              p=p->rlink;                  //繼續搜索結點p的右子樹
            }
            else
            {
              printf("%d\n",p->data);      //訪問結點p
              p=NULL;
            }
          }while((top>0));
     }

B 線索化二叉樹：

線索化二叉樹的結點類型說明：

      typedef struct node
      {
        DataType data;
        struct node *lchild, *rchild;       //左、右孩子指針
        int ltag, rtag;                     //左、右線索
      }TBinTNode;         //結點類型
      typedef TBinTNode *TBinTree;

在線索化二叉樹中，一個結點是葉子結點的充分必要條件是其左、右標志均為1.

(1)中序線索化二叉樹的算法：

       void InOrderThreading(TBinTree p)
      {
        if(p)
        {
          InOrderThreading(p->lchild);   //左子樹線索化
          if(p->lchild)
            p->ltag=0;
          else
            p->ltag=1;
          if(p->rchild)
            p->rtag=0;
          else
            p->rtag=1;
          if(*(pre))      //若*p的前驅*pre存在
          {
            if(pre->rtag==1)
              pre->rchild=p;
            if(p->ltag==1)
              p->lchild=pre;
          }
          pre=p;                         //另pre是下一訪問結點的中序前驅
          InOrderThreading(p->rchild);   //右子樹線索化
        }
      }

(2)在中序線索化二叉樹下，結點p的後繼結點有以下兩種情況：

①結點p的右子樹為空，那麼p的右孩子指針域為右線索，直接指向結點p的後繼結點。
②結點p的右子樹不為空，那麼根據中序遍歷算法，p的後繼必是其右子樹中第1個遍歷到的結點。中序線索化二叉樹求後繼結點的算法：

    TBinTNode *InOrderSuc(BiThrTree p)
    {
       TBinTNode *q;
       if(p->rtag==1)   //第①情況
         return p->rchild;
       else            //第②情況
       {
         q=p->rchild;
         while(q->ltag==0)
           q=q->lchild;
         return q;
       }
    }

中序線索化二叉樹求前驅結點的算法：

    TBinTNode *InOrderPre(BiThrTree p)
    {
       TBinTNode *q;
       if(p->ltag==1)
         return p->lchild;
       else
       {
         q=p->lchild;         //從*p的左孩子開始查找
         while(q->rtag==0)
           q=q->rchild;
         return q;
       }
    }

(3)遍歷中序線索化二叉樹的算法

    void TraversInOrderThrTree(BiThrTree p)
    {
      if(p)
      {
        while(p->ltag==0)
          p=p->lchild;
        while(p)
        {
          printf("%c",p->data);
          p=InOrderSuc(p);
        }
      }
    }