資料結構面試之六——二叉樹的常見操作2（非遞歸周遊&二叉排序樹)

題注

《面試寶典》有相關習題，但思路相對不清晰，排版有錯誤，作者對此參考相關書籍和自己觀點進行了重寫，供大家參考。

接上一節第五部分，主要分析二叉樹的非遞歸周遊和二叉排序樹的操作。

1. 非遞歸中序周遊

//1.依次将根節點root的左子樹入棧,直到lchild=NULL,執行2

//2.将棧的元素出棧、通路；将目前指針指向節點的rchild，循環周遊。直到棧空為止！

template<typenameelemType>
       voidbinaryTreeType<elemType>::noRecursionInorderTraversal()                      //非遞歸中序周遊
       {
              cout<< "noRecursionInorderTraversal--------------------------->"<< endl;
              linkedStackType<nodeType<elemType>* > stack;
              nodeType<elemType>*current = root;
              while(current!= NULL || !stack.isEmptyStack())  //或者||
              {
                     if(current!= NULL)
                     {
                            stack.push(current);
                            current= current->llink;
                     }
                     else
                     {
                            stack.pop(current);
                            cout<< current->info << "\t"; //出棧的時候通路節點
                            current= current->rlink;
                     }
              }
              cout<< endl;
              cout<< "<------------------------noRecursionInorderTraversal"<< endl;
       }

2. 非遞歸先序周遊

//在中序周遊的基礎上，通路次序發生變化;

//先序周遊，需要先逐個周遊根節點，然後依次處理其左、右孩子節點。

template<typenameelemType>
       voidbinaryTreeType<elemType>::noRecursionPreorderTraversal()                     //非遞歸前序周遊
       {
              cout<<"noRecursionPreorderTraversal--------------------------->"<< endl;
              linkedStackType<nodeType<elemType>* > stack;
              nodeType<elemType>*current = root;
              while(current!= NULL || !stack.isEmptyStack())  //或者||
              {
                     if(current!= NULL)
                     {
                            cout<< current->info << "\t";   //先通路節點後入棧
                            stack.push(current);
                            current= current->llink;
                     }
                     else
                     {
                            stack.pop(current);
                            current= current->rlink;
                     }
              }
              cout<< endl;
              cout<< "<------------------------noRecursionPreorderTraversal"<< endl;
       }

3. 非遞歸後序周遊

由于通路的順序為先左子樹、然後右子樹，最後根節點。并且對于每一個節點都是上述操作，是以，對于周遊來講，需要識别目前節點類型是根（相對）、左孩子節點、右孩子節點。故，我們設定了flag标記變量，flag=0初始标記，節點尚未入棧；在通路左孩子之前将flag置為1；在通路右孩子之前将flag置為2；并且在通路右孩子之後，将flag置為0。

//後序非遞歸周遊比較複雜..

template<typenameelemType>
voidbinaryTreeType<elemType>::noRecursionPostorderTraversal()                    //非遞歸後序周遊
       {
              cout<<"noRecursionPostorderTraversal--------------------------->"<< endl;
              linkedStackType<nodeType<elemType>* > stack;
              linkedStackType<int>intStack;                       //标記位同步棧.
              nodeType<elemType>*current = root;
              intnflag = 0;                                      //初始标記為0.
              if(current== NULL)
              {
                     cout<< "The Stack is Empty!" << endl;
              }
              else
              {
                     //1.将頭節點先入棧,
                     stack.push(current);
                     intStack.push(1);
               current = current->llink;        //注意此處需要調整指向******
                     while(!stack.isEmptyStack()&& !intStack.isEmptyStack())         
                     {
                            if(current!= NULL && nflag == 0)                                     
                            {
                               stack.push(current);
                                   intStack.push(1);   //标記位為1,[在通路左孩子之前，将其值置為1]。
                               current = current->llink;
                            }
                            else
                            {
                                   stack.pop(current);
                                   intStack.pop(nflag);    //此時的标記位為傳回值,需要根據其做判斷
                                   if(nflag== 1)         //說明下一步需要入棧的為右孩子.
                                   {
                                          stack.push(current);   //繼續将該節點入棧，                                                              
                                         intStack.push(2);      //但[在通路右孩子之前，将其置為2]。
                                          current= current->rlink;           //通路右節點，
                                          nflag= 0;                                  //置标記位為0
                                   }
                                   else
                                   {
                                          cout<< current->info << " ";  //待左右子樹都為空再通路節點。
                                   }
                            }
                     }
                     cout<< endl;
                     cout<< "<------------------------noRecursionPostorderTraversal"<< endl;
              }    
       }

4. 二叉排序樹的搜尋操作

明确概念，國内、國外的著作裡提及的下三個概念等價，二叉搜尋樹=二叉查找樹=二叉排序樹。

//二叉排序樹的查找存在以下幾種情況：

//1.連結清單為空，提示并傳回；

//2.連結清單非空，需要循環查找直到指針為空，若存在，則bfound=true；否則查找至最後bfound=預設false。

template <class elemType>
boolbSearchTreeType<elemType>::search(const elemType& searchItem)
{
       nodeType<elemType>*current = new nodeType<elemType>;
       boolbFound = false;
 
       if(root== NULL)
       {
              cout<< "The bSearchTree is NULL\n";       //case1: 連結清單為空!
              returnfalse;
       }
       else
       {
              current= root;
              while(current!= NULL && !bFound) //case2:在連結清單中查找,根據大小鎖定左、右子樹.
              {
                     if(current->info== searchItem)
                     {
                            bFound= true;
                     }
                     elseif(current->info > searchItem)
                     {
                            current= current->llink;              //左子樹
                     }
                     elseif(current->info < searchItem)
                     {
                            current= current->rlink;             //右子樹
                     }
              }
       }
 
       returnbFound;
}
5.      二叉排序樹的插入存在以下幾種情況：

//1.連結清單為空，插入元素即為根節點；

//2.連結清單非空，需要尋找插入位置後插入。

//2.1插入元素已經存在，則提示出錯。

//2.2總能找到大于或小于某節點的位置，記錄trailcurrent完成插入操作。


template <class elemType>
voidbSearchTreeType<elemType>::insert(const elemType& insertItem)
{
       nodeType<elemType>*newNode = new nodeType<elemType>;
       nodeType<elemType>*current;
       nodeType<elemType>*trailCurrent;
 
       newNode->info= insertItem;
       newNode->llink= NULL;
       newNode->rlink= NULL;
 
       if(root== NULL)
       {
              root= newNode;                                //case1:樹為空.
       }
       else
       {
              current= root;
              while(current!= NULL)                          //case2,3,4搜尋才知道!
              {
                     trailCurrent= current;
                     if(current->info== insertItem)
                     {
                            cout<< "the elem is already exist!\n";  //case2:元素已經存在
                            return;
                     }
                     else
                     {
                            if(current->info> insertItem)
                            {
                                   current= current->llink;           //case3:鎖定左側位置...
                            }
                            else
                            {
                                   current= current->rlink;           //case4:鎖定右側位置...
                            }
                     }
              }//endwhile
 
              //case3,4根據大小進行連結
              if(trailCurrent->info< insertItem)           
              {
                     trailCurrent->rlink= newNode;
              }
              else
              {
                     trailCurrent->llink= newNode;
              }
 
       }//end else
}

6.      二叉排序樹的删除存在以下幾種情況【此處可能複雜些】：
//删除一個節點，要首先判斷元素值在二叉排序樹中是否存在，

//若不存在則傳回；

//若存在則需要鎖定其對應位置為1根節點；2葉節點；3其餘節點。

//根據要删除的節點是否含有左右子樹的不同，分為4種情況考慮，

//見deleteFromTree()函數。


template <class elemType>
voidbSearchTreeType<elemType>::deleteNode(const elemType& deleteItem)
{
       //1.查找節點
       //2.1找不到，不存在;
       //2.2找到，删除，調用函數
       nodeType<elemType>*current;
       nodeType<elemType>*trailCurrent;
       boolbFound = false;
 
       if(root== NULL)
       {
              cout<< "Can't delete an Empty BST" << endl;
              return;
       }
       else
       {
              current= root;
              trailCurrent= root;
              while(current != NULL && !bFound)
              {
                     if(current->info== deleteItem)
                     {
                            bFound= true;
                     }
                     elseif(current->info > deleteItem)
                     {
                            trailCurrent= current;
                            current= current->llink;    //左
                     }
                     else
                     {
                            trailCurrent= current;
                            current= current->rlink;   //右
                     }
              }//endwhile
 
              if(current== NULL)
              {
                     cout<< deleteItem << " is not Exist in the BST!\n" <<endl;
              }
              elseif(bFound)
              {
                     if(current== root)
                     {
                            deleteFromTree(root);                  //可能是根節點
                     }
                     elseif(trailCurrent->info > deleteItem)
                     {
                            deleteFromTree(trailCurrent->llink);//左半分支，調整trailCurrent的指向
                     }
                     elseif(trailCurrent->info < deleteItem)
                     {
                            deleteFromTree(trailCurrent->rlink);  //右半分支，調整trailCurrent的指向
                     }
              }//endif bFound
         }//end else
}


//[原理]:某節點的前驅是該節點左子樹的最右端的節點（中序周遊的結果）


template <class elemType>
voidbSearchTreeType<elemType>::deleteFromTree(nodeType<elemType>*&p)
{
       nodeType<elemType>*temp;
       nodeType<elemType>*current;
       nodeType<elemType>*trailCurrent;
 
       if(p== NULL)
       {
              cout<< "The BST is NULL!" << endl;
              return;
       }
       if(p->llink== NULL && p->rlink == NULL)      //情況1,左右節點都為空（葉節點）
       {
              temp= p;
              p= NULL;
              deletetemp;
       }
       elseif( p->rlink == NULL)                     //情況2,右子樹為空，左非空
       {
              temp= p;
              p= temp->llink;
              deletetemp;
       }
       elseif(p->llink == NULL)                      //情況3,左子樹為空，右非空
       {
              temp= p;
              p= temp->rlink;
              deletetemp;
       }
       else                           //情況4,左右都非空[用中序周遊的前一個節點替換]
       {
              current= p->llink;
              trailCurrent= NULL;
 
              while(current->rlink!= NULL)
              {
                     trailCurrent= current;   //trailCurrent最終指向準備删除節點的前一個節點
                     current= current->rlink;
              }
 
              p->info= current->info;                //資訊指派
 
              if(trailCurrent== NULL)              //僅一個左孩子節點
              {
                     p->rlink = current->llink;         
              }
              else
              {
                     trailCurrent->rlink= current->llink; //給删除前點的前面一個節點調整指針指向
              }
              deletecurrent;
       }
 
}

作者：銘毅天下

來源：CSDN

原文：

https://blog.csdn.net/laoyang360/article/details/7884449

資料結構面試之六——二叉樹的常見操作2（非遞歸周遊&二叉排序樹)

題注

1. 非遞歸中序周遊

2. 非遞歸先序周遊

3. 非遞歸後序周遊

4. 二叉排序樹的搜尋操作

繼續閱讀

資料結構————哈夫曼樹資料結構——哈夫曼樹

資料結構——二叉排序樹include

資料結構面試之五—二叉樹的常見操作（遞歸實作部分）

【雲栖号案例 | 交通&物流】運滿滿雲企業網上雲案例

雲計算招聘崗位全方位需求解析+學習路徑指南

健壯且靈活的混合雲網絡—— Series1：組網建設1 什麼是混合雲2 建構混合雲應具備的條件3 組網建設

阿裡雲ACE認證雲計算架構師考試内容範圍有哪些？

17歲你還在埋頭數理化，他已經玩轉雲計算興趣是最好的老師——遊戲聯機平台需求是探索的動力——個人部落格鑽研是進步的階梯——小程式他為自己代言

結構與算法(05)：二叉樹與多叉樹一、樹狀結構二、二叉樹模型三、二叉樹編碼四、多叉樹五、源代碼位址

03月18直播預告｜基于DDH+MyBase降本合規最佳實踐

阿裡雲acp認證考試報名方法阿裡雲acp認證題庫試題分享

阿裡雲acp考試費用提升我們在職場上的競争力

阿裡雲acp認證考試條件普通學曆也能獲得高薪

阿裡雲acp全稱阿裡雲acp認證的學習指導和建議

資料結構面試之六——二叉樹的常見操作2（非遞歸周遊&二叉排序樹)

資料結構之判斷一棵樹是不是完全二叉樹

資料結構面試之六——二叉樹的常見操作2（非遞歸周遊&amp;二叉排序樹)

題注

1. 非遞歸中序周遊

2. 非遞歸先序周遊

3. 非遞歸後序周遊

4. 二叉排序樹的搜尋操作

繼續閱讀

資料結構面試之六——二叉樹的常見操作2（非遞歸周遊&二叉排序樹)