UC知道数据结构的二叉树求深度的问题。。
来源：百度知道 编辑：UC知道 时间：2024/05/26 16:58:59
typedef struct node
{ char data;
struct node *lchild,*rchild;
}JD;
int BiTreeDepth(JD *T)
{ /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild); //递归求左子树的深度
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild); //递归求右子树的深度
else
j=0;
return i>j?i+1:j+1; //取深度值大者加1作为该树的深度
}
疑问是。。。。这个算法中的求深度的语句： i=BiTreeDepth(T->lchild)
为什么递归结束后i就等于深度了呢？为什么每递归一次i就加上了1呢？。。。。十分奇怪！
谢谢了！！！！
{ char data;
struct node *lchild,*rchild;
}JD;
int BiTreeDepth(JD *T)
{ /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int i,j;
if(!T)
return 0;
if(T->lchild)
i=BiTreeDepth(T->lchild); //递归求左子树的深度
else
i=0;
if(T->rchild)
j=BiTreeDepth(T->rchild); //递归求右子树的深度
else
j=0;
return i>j?i+1:j+1; //取深度值大者加1作为该树的深度
}
疑问是。。。。这个算法中的求深度的语句： i=BiTreeDepth(T->lchild)
为什么递归结束后i就等于深度了呢？为什么每递归一次i就加上了1呢？。。。。十分奇怪！
谢谢了！！！！
那你说为什么不＋1呢？
return i>j?i+1:j+1;
每次回调的时候都会比较i和j的值，即左子树的深度和右子树的深度，选较大者加1后作为以自己为根节点的树的深度
很简单的问题啊！
如果这棵二叉树不空，它的高度必然是从1计算的啊！+1就在这里。为什么递归h后+1你不理解是因为你还不了解递归的真正含义，在最后的return语句后的值大者又被传给了它的父节点中的i，i+1的操作就使它加了1.不知道你是否懂？？
个人建议，对一个比较简单的如三层二叉树进行递归跟踪，就能理解了。