赞
踩
注:本文中二叉树通过二叉链表构建。
节点类型定义如下:
struct node{
char data;
node *lchild;
node *rchild;
};
思路一(自上向下):每下一层,就和当前暂存的最大的深度作比较并取最大值
对二叉树做遍历操作,最简单可以用递归的方式实现。
这就需要我们对递归进行下一层的时候,需要记录下一层的深度等于当前深度+1。
通过递归实现后的代码如下:
int maxDeep = 0; //暂存的最大深度
void MaxDeep(node* root, int nowDeep){
if (root == NULL){//递归结束条件,说明这一层已经不是二叉树的节点,也就不需要使nowDeep和maxDeep进行比较
return;
}
maxDeep = max(maxDeep, nowDeep);//取较大值
MaxDeep(root->lchild, nowDeep+1);//递归处理左子树
MaxDeep(root->rchild, nowDeep+1);//递归处理右子树
}
需要注意的是,调用时,根节点的深度为一,即nowDeep传1。
思路二(自下向上):当前树的最大深度等于其子树的最大深度+1
在第一种思路中,我们需要借助一个额外的变量maxDeep去记录当前处理过的最大深度,这是一个外部变量,当然可以放到形参里面,但是一个对递归没有什么作用的数作为一个形参出现就会显得有些奇怪,用起来也不方便。
为了方便使用,我们可以换一种思路:
既然自上向下的路走不通,可以反过来走。
对于一棵二叉树,可以根据有无父节点分为“根节点”和“非根节点”,对于每个“非根节点”又可以作为一棵新的树的根节点。那么这种思路反过来,就有了:
当前树的最大深度等于其子树的最大深度+1。这里的“1”是根节点自己还有一层深度需要加上。
以这种思路实现的代码:
int maxDeep(node* root){
if(root == NULL){//递归到叶子节点的“子树”,不存在,其深度为0,递归结束。
return 0;
}
return max(maxDeep(root->lchild),maxDeep(root->rchild))+1;//如果有子树,其深度为左右子树的最大值+1。
}
这个代码还可以简写成:
int maxDeep(node* root){
return root == NULL ? 0 : max(maxDeep(root->lchild),maxDeep(root->rchild))+1;
}
深度优先的方式是一路走到黑,记录路径长度。
那么广度优先的方式就是真真正正的计算层次来得到二叉树的深度了。
这里用到了二叉树的层次遍历的思路
实现代码:
struct que{//只是封装了队列节点类型,并没有自己封装队列,可以使用STL的queue进行操作 node* root; int index; }; int maxDeep(node* root){ que q[505]; for (int i = 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; while (head != 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;//做到最后就是最深的一层,即为二叉树的深度 }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。