數(shù)據(jù)結(jié)構(gòu)—基礎(chǔ)知識（11）：二叉樹的遍歷

二叉樹的遍歷

二叉樹的遍歷是指按某條搜索路徑訪問樹中每個結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。由于二叉樹是一種非線性結(jié)構(gòu)，每個結(jié)點都可能有兩棵子樹，因而需要尋找一種規(guī)律，以便使二叉樹上的結(jié)點能排列在一個線性隊列上，進(jìn)而便于遍歷。
由二叉樹的遞歸定義可知，遍歷一棵二叉樹便要決定對根結(jié)點N、左子樹L和右子樹R的訪問順序。按照先遍歷左子樹再遍歷右子樹的原則，常見的遍歷次序有先序(NLR)、中序(LNR)和后序(LRN)三種遍歷算法，其中“序”指的是根結(jié)點在何時被訪問。

先序遍歷：ABCDEFGH
中序遍歷：BDCEAFHG
后序遍歷：DECBHGFA

1. 先序遍歷

   先序遍歷的操作過程如下：

   若二叉樹為空則什么都不做；否則，①訪問根節(jié)點；②先序遍歷左子樹；③先序遍歷右子樹。

   對應(yīng)的遞歸算法：

   void PreOrder(BinTree T)
   {//先序遍歷的遞歸算法
       if(T!=NULL)
       {
           visit(T);//訪問根結(jié)點
           PreOrder(T->lchild);//遞歸遍歷左子樹
           PreOrder(T->rchild);//遞歸遍歷右子樹
       }
   }
   

   先序遍歷的非遞歸算法：

   void PreOrder2(BinTree T)
   {//先序遍歷的非遞歸算法
       InitStack(S);BiTree p=T;//初始化棧S；p是遍歷指針
       while(p||!IsEmpty(S))//棧不空或p不空時循環(huán)
       {
           if(p){//一路向左
               visit(p);Push(S,p);//訪問當(dāng)前結(jié)點，并入棧
               p=p->lchild;//左孩子不空，一直向左走
           }
           else{//出棧，并轉(zhuǎn)向出棧結(jié)點的右子樹
               Pop(S,p);//棧頂元素出棧
               p=p->rchild;//向右子樹走，p賦值為當(dāng)前結(jié)點的右子樹
           }//返回while循環(huán)繼續(xù)進(jìn)入if-else語句
       }
   }
   

2. 中序遍歷

   中序遍歷的操作過程如下：

   若二叉樹為空則什么都不做；否則，①先序遍歷左子樹；②訪問根節(jié)點；③先序遍歷右子樹。

   對應(yīng)的遞歸算法：

   void InOrder(BinTree T)
   {//中序遍歷的遞歸算法
       if(T!=NULL)
       {
           InOrder(T->lchild);//遞歸遍歷左子樹
           visit(T);//訪問根結(jié)點
           InOrder(T->rchild);//遞歸遍歷右子樹
       }
   }
   

   中序非遞歸遍歷

   void InOrder2(BiTree T)
   {
       InitStack(S); BiTree p=T;//初始化棧S；p是遍歷指針
       while(p||!IsEmpty(S))//棧不空或p不空時循環(huán)
       {
           if(p){//一路向左
               Push(S,p);//當(dāng)前結(jié)點入棧
               p=p->1child;//左孩子不空，一直向左走
           } 
           else{//出棧，并轉(zhuǎn)向出棧結(jié)點的右子樹
               Pop(S,p);visit(p);//棧頂元素出棧，訪問出棧結(jié)點
               p=p->rchild;//向右子樹走，p賦值為當(dāng)前結(jié)點的右孩子
           }//返回 while 循環(huán)繼續(xù)進(jìn)入if-else語句
       }
   }
   
   

3. 后序遍歷

   后序遍歷的操作過程如下：

   若二叉樹為空則什么都不做；否則，①先序遍歷左子樹；②先序遍歷右子樹；③訪問根節(jié)點。

   對應(yīng)的遞歸算法：

   void PostOrder(BinTree T)
   {//后序遍歷的遞歸算法
       if(T!=NULL)
       {
           PostOrder(T->lchild);//遞歸遍歷左子樹
           PostOrder(T->rchild);//遞歸遍歷右子樹
           visit(T);//訪問根結(jié)點
       }
   }
   

   后序遍歷的非遞歸算法：文章來源地址http://www.zghlxwxcb.cn/news/detail-827589.html

   void PostOrder (BiTree T)
   {
       InitStack(S);
       BiTNode *p=T;
       BiTNode *r=NULL;
       while(p||!IsEmpty(S))
       {
           if(p){//走到最左邊
               push(S,p);
               p=p->lchild;
           }
           else{//向右
               GetTop(S,p);//讀棧頂結(jié)點(非出棧)
               if(p->rchild&&p->rchild!=r)//若右子樹存在，且未被訪問過
                   p=p->rchild;//轉(zhuǎn)向右
               else{//否則，彈出結(jié)點并訪問
                   pop(S,p);//將結(jié)點彈出
                   visit(p->data);//訪問該結(jié)點
                   r=p;//記錄最近訪問過的結(jié)點
                   p=NULL;//結(jié)點訪問完后，重置p指針
               }
           }//else
       }//while
   }
   

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu)—基礎(chǔ)知識（11）：二叉樹的遍歷的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！