如何运用递归思想计算二叉树深度？

本文共计434个文字，预计阅读时间需要2分钟。

从二叉树的深度递归函数中，使用debug调试更深入理解程序的运行过程。

函数：int BTNodeDepth(BTNode *b)功能：求二叉树b的深度

cint BTNodeDepth(BTNode *b) { int leftDepth=0, rightDepth=0; if (b==NULL) { return 0; } // 调试：观察左子树深度 debug(Calculating left subtree depth); leftDepth=BTNodeDepth(b->left); // 调试：观察右子树深度 debug(Calculating right subtree depth); rightDepth=BTNodeDepth(b->right); // 调试：计算当前节点深度 debug(Current node depth: %d, leftDepth + rightDepth + 1); return leftDepth + rightDepth + 1;}

从求二叉树的深度的递归函数中，使用debug调试更深刻的理解程序的运行过程。intBTNodeDepth(BTNode*b)求二叉树b的深度{intlchilddep0,rchil

从求二叉树的深度的递归函数中，使用debug调试更深刻的理解程序的运行过程。 int BTNodeDepth(BTNode *b) //求二叉树b的深度 { int lchilddep = 0 ,rchilddep = 0; if (b==NULL) return(0); //空树的高度为0 else { lchilddep = BTNodeDepth(b->lchild); //求左子树的高度为lchildde rchilddep = BTNodeDepth(b->rchild); //求右子树的高度为rchilddep return (lchilddep>rchilddep)? (lchilddep+1):(rchilddep+1); } }

例如这里使用完函数后再return时，会将return 中的值赋值给lchilddep或lchilddep。 在debug中看到的现象时会回到这个函数（debug箭头指向这个函数，执行的是赋值操作） 在去执行下一个函数。 这里 = 号是得到上一个return里的值。

递归函数变量赋初值问题，为什么不加static？，每次int lchilddep = 0 ,rchilddep = 0;都是新的变量（相当于调用新的函数）创建新的空间这里的被赋值的地方都是上一个return返回的，所以不加。

二这里递归都是反哺上去的值。

对递归有了图表化的认识，想象成二叉树排布的房间，只有一个返回则想象成每一层都只有一个节点的树，两个以上则想象成多叉树。