二叉树的高度怎么算 如何用非递归算法求二叉树的高度
以二叉链表为存储结构,写出求二叉树高度和宽度的算法，求二叉树高度，以二叉树链表作为二叉树的存储结构，怎么编写算法计算返回二叉树的高度？如何用非递归算法求二叉树的高度？
本文导航
以二叉链表为存储结构,写出求二叉树高度和宽度的算法
原题：
以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法。所谓宽度是指在二叉树的各层上，具有结点数最多的那一层上的结点总数。
标准答案：
①求树的高度
思想：对非空二叉树，其深度等于左子树的最大深度加1。
Int Depth(BinTree *T)
{
int dep1,dep2;
if(T==Null) return(0);
else
{
dep1=Depth(T->lchild);
dep2=Depth(T->rchild);
if(dep1>dep2) return(dep1+1);
else return(dep2+1);
}
②求树的宽度
思想：按层遍历二叉树，采用一个队列q，让根结点入队列，最后出队列，若有左右子树，则左右子树根结点入队列，如此反复，直到队列为空。
int Width(BinTree *T)
{
int
front=-1,rear=-1;/*
队列初始化*／
int flag=0,count=0,p;
/* p用于指向树中层的最右边的结点，标志flag记录层中结点数的最大值。*／if(T!=Null)
{
rear++;
q[rear]=T;
flag=1;
p=rear;
}
while(front<p)
{
front++;
T=q[front];
if(T->lchild!=Null)
{
rear++;
q[rear]=T->lchild;
count++;
}
if(T->rchild!=Null)
{
rear++;
q[rear]=T->rchild;
count++;
}
if(front==p)
/* 当前层已遍历完毕*/
{
if(flag<count)
flag=count;
count=0;
p=rear; /* p指向下一层最右边的结点*/
}
}
/* endwhile*/
return(flag);
}
求二叉树高度
公式：V0=（V2） +2（ V3）+3 （V4）....(k-1)（Vk）+1 所有的树都满足这个公式，其中v0...vk代表 度为0...K的节点个数。
所有计算度与节点个数的问题无论是几叉树的都必须用这个式子，我建议楼主哥哥记住！
叶子节点就是度为0的节点V0，其他的分支节点度都为m那么就只存在度为0和度为m的节点
代入上面公式：
V0=(m-1)Vm+1
又因为：
Vm+V0=n //因为树总共n个节点
解这个方程组，就得 V0=((m-1)n+1)/m
用计算机计算 ，你可以将它理解成一个层序遍历的过程，使用队列来遍历：
存储结构是
typedef struct Node
{
int data;
struct node *FirstChild;
struct node *NextBrother;
}*Tree;
static int leafnum; //全局函数用于计数叶子节点
void BFSCount(Tree t)
{
int i=0;
SeqQueue *Q;
TreeNode *p;
InitQueue(Q);
if(t==NULL) return;
EnterQueue(Q,t);
While(!Empty(Q))
{
DeleteQueue(Q,p); //出队 然后判断这个节点
if(p->FirstChild==NULL) leafnum++; //如果这个节点一个孩子也没有，则是叶子，计数+1
else{
p=t->FirstChild; //否则开始将它第一个孩子继续进入队
EnterQueue(Q,p);
while(i<=m) //把第一个孩子的下一个兄弟依次入队
{
p=p->NextBrother;
EnterQueue(Q,p);
}
}
}
}
以二叉树链表作为二叉树的存储结构，怎么编写算法计算返回二叉树的高度？
编写方法如下：
高度其实也叫深度，我通俗点说就是 比如根节点 是第一层，根节点的左右孩子为第二层，然后根节点的左右孩子各自的孩子为第三层.....那么二叉树的高度就是这棵树最大的层数。这么说不知道楼主明白了没有，举例就是：如果只有一个根节点，那么高度就是1，如果有一个根节点再加上根节点的两个孩子，或者其中一个孩子，那么高度就是2；
那根据这样 如果用递归的思想，算法就比较好写了，就是统计一下根节点的左右孩子的高对呗，看哪个的高度更大那二叉树高度就是哪个。
具体代码如下：
#include<stdio.h>
#include<stdlib.h> ; ; ; ; //头文件就不用说了吧
typedef struct Node{
char data;
struct Node* lchild;
struct Node* rchild;
}Node,*Tree; ; ; ; ; ; ;//二叉树的定义也不用多说吧那个data的数据类型char可以任意换是吧
int max(int m, int n)
{
if (m > n)
return m;
else
return n;
} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; //这个我想能够看明白 求两个数最大值，为什么要求最大值上面也说了
int TreeHeight(Node *root)
{
if (root == NULL)
return 0; ; ; ; ; ; ; ; ;//如果根节点都没有 那高度肯定就是0了 是吧
else
return 1 + max(TreeHeight(root->lchild), TreeHeight(root->rchild));
} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//否则递归计算他的左右孩子的高度然后在加上根节点的层数1 对吧
int height(Node *t) ; ; ; ; ;//第二个算法（其实和第一个一样）
{
if(t==NULL)
return 0;
else
{
int m=height(t->lchild);
int n=height(t->rchild); ; ; ; ; //递归计算该节点的左右孩子的高度
return(m>n)?m+1:n+1; ; ; ; ;//只不过这里没有用到上面求最大值的那个函数，楼主应该学过C
} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//吧，这就是个逗号表达式，判断？A：B ;判断满足就返回A不满
} ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ; ;//足就返回B 那这句换还是一样就是求m和n的最大值然后加1返 回
如何用非递归算法求二叉树的高度
如果是结点的定义中有深度这个属性，那么用一个队列就可以了。
队首放节点
队尾取出节点
比如:根节点放入队列
(开始只有这个一个节点在队列中)
然后呢
从队尾取出这个根节点
然后打散
把他的左右孩子放入对首(这时候有2个节点
也就是二叉树的第二层)
之后从队伍里取出这2个节点
打散
之后队伍里应该是
二叉树第三层的4个节点
。。。。。
这样就把二叉树层次遍历了
因为有些节点没有孩子节点
也就是叶子
这个队列中的节点
逐渐会越来越少
最后一个取出队列的节点
的深度也就是二叉树的高度
如果结点定义没有深度，我写了一个方法，请楼主参考。
public
static
int
findlevel(BinaryNode
root)
{
ArrayList<LinkedList<BinaryNode>>
result=new
ArrayList<LinkedList<BinaryNode>>();
LinkedList<BinaryNode>
list=new
LinkedList<BinaryNode>();
list.add(root);
result.add(list);
int
level=0;
while(true)
{
list=new
LinkedList<BinaryNode>();
for(int
i=0;i<result.get(level).size();i++)
{
BinaryNode
tmp=result.get(level).get(i);
if(tmp.left!=null)
list.add(tmp.left);
if(tmp.right!=null)
list.add(tmp.right);
}
if(list.size()>0)
result.add(list);
else
break;
level++;
}
return
level;
}
其实思路和刚才说的是大同小异的，用一个level来记录二叉树的层次，最底的层次就是他的高度。
每一层都存在单独的list里，这些list再存在一个arraylist里，这样很容易就能知道每一层有哪些结点，如果这些结点有孩子，就把level++，直到某一层没有任何结点有孩子，这时候level就是最后一层了。
