数据结构面试之六——二叉树的常见操作2（非递归遍历&二叉排序树)

六、二叉树的基本操作（非递归遍历）&二叉排序树的操作

       接上一节第五部分，主要分析二叉树的非递归遍历和二叉排序树的操作。

1.      非递归中序遍历

//1.依次将根节点root的左子树入栈,直到lchild=NULL,执行2

//2.将栈的元素出栈、访问；将当前指针指向节点的rchild，循环遍历。直到栈空为止！

     

Cpp代码 
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;  
      } 

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.      非递归先序遍历

       //在中序遍历的基础上，访问次序发生变化;

       //先序遍历，需要先逐个遍历根节点，然后依次处理其左、右孩子节点。

    

Cpp代码 
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;  
     } 

  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。

       //后序非递归遍历比较复杂..

    

Cpp代码 
template<typenameelemType>  
idbinaryTreeType<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;  
            }      
     } 

  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。


Cpp代码 
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;  
} 

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完成插入操作。


Cpp代码 
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  
} 

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()函数。


Cpp代码 
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>::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
}



//[原理]:某节点的前驱是该节点左子树的最右端的节点（中序遍历的结果）


Cpp代码 
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;  
       }  
   
}