数据结构面试之五—二叉树的常见操作（递归实现部分

本文链接：https://blog.csdn.net/mark555/article/details/20766817

数据结构面试之五—二叉树的常见操作（递归实现部分）

题注：《面试宝典》有相关习题，但思路相对不清晰，排版有错误，作者对此参考相关书籍和自己观点进行了重写，供大家参考。

转载请注明：http://blog.csdn.net/wojiushiwo987/article/category/1210932

五、二叉树的基本操作（递归实现）

二叉树是笔试、面试的重点，包括选择题的题型之——求解前、中、后序的遍历结果等。去年（2011秋季）的百度笔试试题就考察了二叉树的后序遍历的非递归实现。

笔者先就下面常考几个题目就递归算法的实现分析如下：

递归的核心就是遍历完根节点后，再依次同样的方法递归左孩子、右孩子节点，直到为空为止！

1.中根遍历

//中序:左->根->右[递归实现]

[cpp]view plaincopy 
   
 template<typename elemType>  
      voidbinaryTreeType<elemType>::inorder(nodeType<elemType> *p)  
      {  
             if( p != NULL )  
             {  
                    inorder(p->llink);  
                    cout << p->info << " ";  
                    inorder(p->rlink);  
             }  
      }  

2.先根遍历

//前序:根->左->右[递归实现]

[cpp]view plaincopy 
   
 template<typename elemType>  
       voidbinaryTreeType<elemType>::preorder(nodeType<elemType> *p)  
       {      
              if( p != NULL )  
              {  
                     cout << p->info << " ";  
                     preorder(p->llink);  
                     preorder(p->rlink);  
              }      
       }  

3.后根遍历

//后序:左->右->根[递归实现]

[cpp]view plaincopy 
   
 template<typename elemType>  
       voidbinaryTreeType<elemType>::postorder(nodeType<elemType> *p)  
       {  
              if( p != NULL )  
              {  
                     postorder(p->llink);  
                     postorder(p->rlink);  
                     cout << p->info << " ";  
              }  
       }  

4.//求树的高度![递归实现]

//等于左右子树的最大高度+1

[cpp]view plaincopy 
   
    template<typename elemType>  
     intbinaryTreeType<elemType>::height(nodeType<elemType> *p)  
     {  
            if( p == NULL)  
            {  
                   return 0;  
            }  
            else  
            {  
                   return 1 + max( height(p->llink),height(p->rlink)); //加上根节点1层..  
            }  
     }  
   
 //辅助max  
     template<typename elemType>  
     int binaryTreeType<elemType>::max(int x, int y)  
     {  
            return ( x >= y ? x : y );  
     }  

5./全部/节点数目统计[递归实现]

[cpp]view plaincopy 
   
 template<typename elemType>  
     int binaryTreeType<elemType>::nodeCount(nodeType<elemType>*p)  
     {      
            if(p == NULL)  
            {  
                   return 0;  
            }  
            else  
            {  
                   return 1 + nodeCount(p->llink) +nodeCount(p->rlink);  
            }  
      
     }  

6.//叶节点数目[递归实现]

//叶子节点的特征就是左右子树为空。

[cpp]view plaincopy 
   
 template<typename elemType>  
   intbinaryTreeType<elemType>::leavesCount(nodeType<elemType> *p)  
   {  
          if(p == NULL)  
          {  
                 return 0;  
          }  
          else if(p->llink == NULL && p->rlink ==NULL)  
          {  
                 return 1; //  
          }  
          else  
          {  
                 return leavesCount(p->llink) +leavesCount(p->rlink);  
          }  
   }  

7.判定两颗二叉树是否相等

【思路】：逐个节点（从根节点开始）进行比对，可能出现二叉树1自根节点左子树与二叉树2自根节点的右子树完全一致的情况，或者反之，这种情况也视为两颗二叉树一致。

分为一下5种情况。

[cpp]view plaincopy 
   
 template<typename elemType>  
        boolbinaryTreeType<elemType>::beTreesEqual(nodeType<elemType> *first,nodeType<elemType> *second)  
        {  
               bool isFirstTreeNull = (first == NULL);  
               bool isSecondTreeNull = (second == NULL);  
    
               //case1: 两者不等.  
               if(isFirstTreeNull != isSecondTreeNull)  
               {  
                      return false;  
               }  
               //case2: 两者都为非空.  
               if(isFirstTreeNull == true &&isSecondTreeNull==true)  
               {  
                      return true;  
               }  
               //case3: 两者都非空，但两者的节点值不等  
               //case4: 两者都非空，但节点值相等，需要考虑左右分支的情况...  
               if(!isFirstTreeNull && !isSecondTreeNull)  
               {  
                      if(first->info != second->info) //节点值是否相等  
                      {  
                             return false;  
                      }  
                      else  
                      {  
                             return((beTreesEqual(first->llink,second->llink) &&beTreesEqual(first->rlink,second->rlink))  
                                       ||(beTreesEqual(first->llink,second->rlink) &&beTreesEqual(first->rlink,second->llink)));  
                      }//  
               }//end if  
               return false;  
        }  