二叉树求深度的递归的详细分析
二叉树求深度递归算法源码
》数据结构：
typedef struct BINODE
{
TELEMETYPE data;
struct BINODE *lchild,*rchild;
}BiNode,*BiTtree;
》递归函数
int GetTreeDeep(BiTtree T) //计算二叉树的深度
{
if(T==NULL)
return 0;
else{
int a = GetTreeDeep(T->lchild);
int b = GetTreeDeep(T->rchild);
return (a>b)?(a+1):(b+1);
}
}
如(a)图，假设给出创建了这个二叉树，使用如上给出的递归实现的经典算法，这个递归过程是怎样的呢？
递归过程中GetTreeDeep这个函数被自身多次调用，让我们给它们标号：
函数 返回值 做什么？ 步骤
GetTreeDeep ----》进入函数 ----》访问A 0
int a = GetTreeDeep(T->lchild); 1 ----》访问B 1
int a = GetTreeDeep(T->lchild); 0 ----》访问B的左空节点 2
int b = GetTreeDeep(T->rchild); 0 ----》访问B的右空节点 3
此时标号2,3函数完成，得到a=0，由步骤2,3得到步骤1函数的a值为1，再由步骤1得到步骤0对应的返回值为2，此时计算到树的高度为2，这只是根节点左部的子树高度，此时运行到刚开始进入函数内的第二个GetTreeDeep，所以接下来该访问右部子树：
int b = GetTreeDeep(T->rchild); ------ 》访问C 4
int a = GetTreeDeep(T->lchild); 2 ------》访问D 5
int a = GetTreeDeep(T->lchild); 1 ------》访问F 6
int a = GetTreeDeep(T->lchild); 0 ------》访问F的左空节点 7
int b = GetTreeDeep(T->rchild); 0 ------》访问F的右空节点 8
步骤7,8的返回值为0，由此得到步骤6的返回值为1，步骤4对应的返回值为2，接下来，运行到该访问C的右节点：
int b = GetTreeDeep(T->rchild); ------》访问E 9
int a = GetTreeDeep(T->lchild); 1 ------》访问G 10
int a = GetTreeDeep(T->lchild); 0 ------》访问G的左空节点 11
int b = GetTreeDeep(T->rchild); 0 ------》访问G的右空节点 12
以此类推：可知步骤8的返回值为1，现在该访问E的右节点：
int b = GetTreeDeep(T->rchild); 1 ------》访问H 13
int a = GetTreeDeep(T->lchild); 0 ------》访问H的左空节点 14
int b = GetTreeDeep(T->rchild); 0 ------》访问H的右空节点 15
现在开始返回，比较各个节点的返回值孰大孰小
1， 首先比较的是步骤13和步骤10的返回值，二者一样大，返回1+1，步骤9得返回值2
2， 比较步骤9和5，二者同样为2，故步骤4的返回值为2+1，为3
3， 比较步骤4和步骤1，前者为3，后者为1，取前者，所以最后返回3+1，得步骤0的返回值为4,，即为最终结果。