二叉树求深度算法求二叉树深度方法一、深度优先扫描方式方法二、广度优先扫描方式总结
求二叉树的深度
注：本论文中二叉树由二叉树链表构建。
节点类型定义如下：
struct node{char data； node *lchild； node *rchild； (； 方法一：深度优先遍历方式思路一（自上向下）：每下一层，就和当前暂存的最大的深度作比较并取最大值
遍历二叉树的操作可以最简单地递归实现。
这意味着在递归前进到下一个层次时，必须记录下一个层次的深度等于当前深度1。
递归实现的代码如下：
int maxDeep=0； //暂存的最大深度voidmaxDeep(node*root，int nowDeep ) if ) root==null ) /递归终止条件指示该层不再是二叉树节点，nowDeep和maxdeep //大值maxdeep(root-lchild，nowDeep 1)； //递归处理左子木max deep (root-rchild，nowDeep 1)； //递归处理右部分树}调用时，需要注意根节点的深度为1，也就是nowDeep传递1。
思路二（自下向上）：当前树的最大深度等于其子树的最大深度+1
第一种思路要求使用其他变量maxDeep来记录当前处理的最大深度。 这是一个外部变量，当然可以放在形参数中，但是对递归贡献不大的数作为形参数出现会显得有点奇怪，很难使用。
为了方便使用，可以改变想法。
既然从上到下的路不通，可以反过来走。
在一棵二叉树的情况下，根据父节点的有无可以划分为"根节点"和"非根节点"，每个"非根节点"可以作为新树的根节点。 这个想法相反，如下。
当前树的最大深度与子树的最大深度1相同。 这里的“1”需要在根节点自身上增加一个深度。
用这样的想法实现的代码：
不存在intmaxdeep(node*root ) if ) root==null递归到叶节点的“子树”，其深度为0，递归结束。 返回0； }returnmax(maxdeep(root-lchild )，max deep (root-rchild ) ) 1； //如果有子树，其深度为左右子树的最大值1。 }此代码还可以缩短为：
intmaxdeep(node*root ) {return root==NULL？ 0:最大深度(root-rchild )、最大深度(root-rchild ) ) 1； (方法2 )广度优先的遍历方式深度优先的方式，进行到黑色，记录路径的长度。
广度优先的方式是在真正的计算水平上得到二叉树的深度。
这里使用了二叉树的分层扫描思路
实现代码：
struct que{//只是封装了队列节点类型，而不是自己封装队列。 可以使用STL queue操作node* root； 索引； (； intmaxdeep(node*root ) {que q[505]； for(intI=0； i 505； I ) (/初始化q(I ).root=null； q[i].index=0； (//分层遍历int head=0； int tail=1； q[tail].root=root； //根节点入伍q[tail].index=1； 头儿！=tail}{head； //当然是环形队列方式IF(Q[Head].Root-Lchild！=null(//其左子树为非空tail； q [ tail ].root=q [ head ].root-lchild； //左子树入伍q[tail].index=q[head].index 1； //其左侧子树的根节点所在的层数为该节点的层数1(if(q[head].root-rchild！=null(//其右侧的子树为非空tail； q [ tail ].root=q [ head ].root-rchild； //右子树入伍q[tail].index=q[head].index 1； //将其右边子树的根节点所在的层数记录为该节点的层数1}}return q[tail].index； //走到最后就是最深层，也就是二叉树的深度(两种方法归纳起来各有优劣，深度优先的方法是递归实现的，时间空间消耗大，但编码复杂度极低。 广度优先的方法相反，时间空间消耗少，但编码复杂度高。 深度优先的方式可以不应用递归的方式进行，需要手动在堆栈上进行伪递归，虽然可以改善系统的时间和空间消耗，但提高了编码复杂度，需要自己进行取舍。 在广度优先方式的实现中，不封装队列，可以使用C STL的queue来实现。