面試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 閱讀(279) 評論(0) 編輯 收藏 引用 所屬分類: 算法相關


