关于递归算法求二叉树深度算法

用递归求二叉树深度的算法。
答案是：
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)
}
算法具体怎么运行了？u和v有什么作用？怎么能求出深度了啊？谢谢各位大神指导小弟

aiSTxL · 2018-4-30 01:56:31

u,v 分别求出当前节点左子树和右子树的深度（高度），
然后当前节点的深度就等于左右子树里面较大的那个+1.

if (u>n) return (u+1)
return (v+1)
这句就是返回较深的+1.

u=height(T->lchild);
v=height(T->rchild);

这两句就是递归的调用，求深度了。

if (T==NULL) return 0;

这个就是终止条件了，如果没有子节点就返回。

supur · 2018-4-30 01:56:30

int height(Bitree T)
{
if (T==NULL) return 0;
u=height(T->lchild);
v=height(T->rchild);
if (u>n) return (u+1) //n应该是v
return (v+1)
}
if 中的n应该是v。
其思想是，一个节点的深度是他的两个子节点中深度的最大值再加上1。这个算法中u得到其左子数的深度，V获得右子树的深度。则这个节点的深度就是u和v中最大的再加上1。
要想获得树的深度，就先获得这个树中根节点的两个儿子的深度，比较两个儿子的深度，取其中最大值在加上1最终获得树的深度。根节点的两个儿子的深度就通过这个上面的原则递归求得。

关于递归算法求二叉树深度算法

2 个回复