正文

求二叉树深度的算法2011-04-17 11:22:00

【评论】 【打印】 【字体: 】 本文链接:http://blog.pfan.cn/edwardguo/52433.html

分享到:

题目:二叉树用二叉链表表示,编写求二叉树深度的算法。
答案是:
int height(Bitree T)
{
  if (T==NULL) return 0;
  u=height(T->lchild);
  v=height(T->rchild);
   if (u>n) return (u+1)
  return (v+1)
}

关于递归,你可以看成是一句一句往下运行嘛。需要保存状态的时候,系统就会自动用栈帮你保存。就依你说得那个为例:
n为全局变量,初值为0;

第一次调用height(T),假设T!=NULL
由于T!=NULL:跳过if (T==NULL) return 0; 

关键到了u=height(T->lchild); 调用本身的函数:此时的T->lchild保存在栈中,既然是调用就得从函数开头执行:
看下这时候T2(其实就是T->lchild),if (T==NULL) return 0;
这里假设T不是NULL,就继续运行在遇到u=height(T->lchild); 在调这个函数本身——
这里就假设它为T->lchild==NULL吧。这下可好,这个函数执行return 0;

慢着:第二次函数调用u=height(T->lchild)中的函数值已经计算出来啦。这时u=0;

你还记得第二次调用运行到了v=height(T->rchild); 这句话吧?好,这个过程就和u=height(T->lchild)完全一样。
这里也假设得到的v=0

则第二次调用到了if (u>n) return (u+1) 
return (v+1)
得到一个返回值,不如就假设u〉n,于是返回值1;
好,这一波完毕;

你还记得第一次调用的height吧,这时把返回值给u,u=1;
然后执行到第一次调用中的v=height(T->rchild); 了。分析同上。

这个过程的确比较复杂。慢慢琢磨吧。呵呵。
 
基本思路就是如果当前节点还有子节点,则继续访问,递归的找寻子节点直到叶子节点为止。 

procedure tree(a:node,depth:integer); 
begin 
if result<depth then result:=depth; 
if a.leftchild<>nil then tree(a.leftchild,depth+1); 
if a.rightchild<>nil then tree(a.rightchild,depth+1); 
end; 

注:result是全局变量,是结果 


实际上最好不用什么全局变量 
int depth(node *bt) 
{ if (bt==NULL) 
return 0; 
ldepth=depth(bt->left)+1; 
rdepth=depth(bt->right)+1; 
return max(ldepth,rdepth); 
} 

全局变量是bug 
int Height(BiTree T){ 
int m,n; 
if(!T) return(0); 
else 
m=Height(T->lchild); 
n=Height(T->rchild); 
return((m>n?m:n)+1); 
} 

求树深度的递归算法 
// struct bnode{struct bnode *lc,*rc); 
int depth(struct bnode *r) 
{ 
return r==NULL?0:1+max(depth(r->lc),depth(r->rc)); 
} 

阅读(9339) | 评论(2)


版权声明:编程爱好者网站为此博客服务提供商,如本文牵涉到版权问题,编程爱好者网站不承担相关责任,如有版权问题请直接与本文作者联系解决。谢谢!

评论

loading...
您需要登录后才能评论,请 登录 或者 注册