二、求二叉树的深度
二叉树的深度的定义和树的深度的定义相同，在6.1中曾定义树的深度为树中叶子结点所在层次的最大值。而结点的层次需从根结点起递推，根结点为第一层的结点，第 k 层结点的子树根在第 k+1 层。由此需要在先序遍历二叉树的过程中求每个结点的层次数，并将其中的最大值设为二叉树的深度。
算法6.4void BiTreeDepth(BiTree T, int level, int &depth)
{
// T指向二叉树的根，level 为 T 所指结点所在层次，
// 其初值为1，depth 为当前求得的最大层次,其初值为0
if (T){
if (level>depth) depth=level;
BiTreeDepth(T->Lchild, level+1, depth);
BiTreeDepth(T->Rchild, level+1, depth);
}// if
}// BiTreeDepth
假设在主函数中定义一个 BiTree 型的变量 r，则主函数中求 r 所指二叉树的深度的语句为：
H=0;
BiTreeDepth(r,1,H);
若 r 所指为空树，则算法6.4什么也不做就结束，则 d 仍然等于0；对于非空树，算法6.4执行的过程如动画所示。
|
|||
|
如果对二叉树的深度类似于上例计数的分析，即分析二叉树的深度和它的左右子树的深度之间的关系，那么求深度的算法应该在哪个序的遍历下进行？