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

发表于 | 分类于
字数统计: 177 word | 阅读时长 ≈ 1 min
递归：
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%