Question

二叉树递归问题

int SumNodes( BiTree T)
{ int i，j；
if( !T) retum 0；
i=SumNodes( T->lchild)；
j=SumNodes( T->rchild);

retum (i+j+1)
；
BiTree是二叉树结构类型
他的功能是返回一棵二叉树的高度，
但是关于递归的问题我不是很明白，
最后数值的累加是不是由返回语句+1作用的？
如果没+1还会有返回值吗？

Answer 1

1. 这个递归算法是求二叉树的结点数之和。
2. 如果不加1，返回值恒为0
这个算法的意思是：
1. 如果当前树T没有结点，返回0
2. 否则求得T的左子树结点数i 和 T的右子树结点数j
3. 返回整个二叉树的结点数（i (左子树的结点数) + j (右子树的结点数) + 1(根结点))

Answer 2

据我所知这应该不是返回高度吧。。这是返回所有节点的和。

追问

对是我搞错了，如果return 没有+1还会有返回值吗 ，还有这里递归能解释一下吗，，麻烦你了！

追答

没有+1的话就没有返回值，搜到最后返回0 然后逐层向上返回0 最后还是0
如果你要求二叉树的高度，代码应该如下：
int SumNodes( BiTree T) {
if(!T)
retun 0;
return (SumNodes( T->lchild) > SumNodes( T->rchild) ?
SumNodes( T->lchild) + 1 : SumNodes( T->rchild) + 1)
}
这两个代码你可以结合理解一下 二叉树的算法也就是这样