关于C语言计算二叉树深度的问题

显示全部楼层 · 2016-8-6 23:20:57

typedef struct tree//二叉树的定义
{ char data; struct tree *lchild,*rchild; }TREE,*Tree;
int deep(Tree t)//深度算法
{ if(!t) return 0; else { ld=deep(t->lchild); rd=deep(t->rchild);
if(ld>rd) return rd+1; else return ld+1;
在深度的算法中，只有ld=deep(t->lchild)，并没有count++之类的计数，那最后深度的值是怎么知道的？请高手详细地讲解一下！

千问 · 2016-8-6 23:20:57

这里其实有个很有去的问题，上帝终于把自己搬起来了。在c中函数可以自己调用自己递归，所以在deep的函数里面还有deep。在第一次运行后，rd+1（如果rd较大）被赋值给了deep，然后rd=deep，所以rd就被+1了，要是一直有next就一直做下去，知道最后，每次+1.加的：比如从头节点开始，第一个结点为A，最开始T为指向都结点的指针，然后在if（！t）中判断，因为t不为NULL（在ASCII中的值为0）所以！t为假，所以运行else，ld和rd在初始化时为1，然后运行id=deep（t->lchild）=1和rd=deep（t->rchild）=1此时的t->lchild将被带回到t中，下次运行时此处变为t->lchild-...

千问 · 2016-8-6 23:20:57

有返回值表示以当前节点为根的子树的深度，rd为该节点的右子树的深度，ld为该节点的左子树的深度，其中较大者+1位以当前节点为根的子树的深度，作为返回值给调用它的函数...

千问 · 2016-8-6 23:20:57

这是递归函数，从叶子开始算起，会返回0:return 0; 然后往函数堆栈的上面回溯，每次都加一:return rd+1...