求二叉树的深度,递归和非递归

递归:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int high(Tree t)//求二叉树的高度
{
int n,m;
if(t==NULL)
return 0;
else
{
n=high(t->lchild); //对左子树求高度
m=high(t->rchild); //对右子树求高度
if(n>m) //高度为取两者中大的值+1
return n+1;
else
return m+1;
}
}
非递归(队列):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
int high(Tree t)//求二叉树的高度
{
int depth = 0;
Tree p=NULL;
queue<Tree> q;
q.push(t); //根节点入队
while (!q.empty()){
depth++; //每到新的一层 高度+1
int width = q.size(); //求出本层的结点数
while (width--){ //本层结点全部出队
p = q.front();
q.pop();
if (p->left){
q.push(p->left);
}
if (p->right){
q.push(p->right);
}
}
}
return depth;
}
0%