jake1036

面试100 27二元树的深度

         面试100 27二元树的深度

   一 问题描述：
         二元树的深度，深度定义为二叉树从根到底最长的路径的长度。
       
  二 问题解决方案：
        使用递归解决，最长深度定义为 max(length(p->left)  , length(p->right)) + 1 。
  
  三 代码如下：
       

#include <iostream>
  using namespace std ;
  
 
  struct BinaryNode
  {
     int data ;    
     BinaryNode * left ;
     BinaryNode * right ;         
  } ;
 
  int deep(BinaryNode * r)
  {
      if(r)
      {
         return max(deep(r->left)  , deep(r->right)) + 1 ;            
      }
      else
      return 0 ;
      
      
  }
 
  BinaryNode *  buildTree()
  {
       int data ;
       BinaryNode * r = 0 ;
       cin>>data ; //输入数据      
       if(data > 0)
       {
          r = (BinaryNode *) malloc(sizeof(BinaryNode)) ;
          r->data = data ;
          r->left =  buildTree()  ;
          r->right = buildTree() ;
                            
       }    
       return r ;
       
       
  }
 
 void preOrder(BinaryNode * r) 
 {
   if(r)
   {
     cout<<r->data ;
     preOrder(r->left) ;
     preOrder(r->right) ;     
   }
   
        
 }
 
  int main()
  {
    BinaryNode * root = 0 ;
    root = buildTree() ;
    preOrder(root) ;
    cout<<endl<<deep(root) ;
    system("pause") ;
    return 0 ;    
  }

 

posted on 2011-05-19 13:58 kahn 阅读(237) 评论(0)  编辑 收藏 引用 所属分类: 算法相关


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理