Question

如何用非递归算法求二叉树的高度

Answer 1

if（T＝＝null）

return0；

intfront＝－1，

rear＝－1；

／／front出队指针

rear入队指针intlast＝0，

level＝0；

／／last每一层的最右指针

（front＝＝last时候一层遍历结束level＋＋）BiTreeQ［Maxsize］；

／／模拟队列Q［＋＋rear］＝T；

BiTreep；

while(front<rear){
   

p＝Q［＋＋front］；／／开始出队

因为front要赶到lash

实现level＋＋

if(p->lchild)
 

Q[++rear] = p->lchild;  

 if(p->rchild)
  

Q[++rear] = p->rchild;   

if（front＝＝last）｛

level＋＋；

last＝rear；／／last指向下层节点｝

｝

扩展资料

非递归算法思想：

（1）设置一个栈S存放所经过的根结点（指针）信息；初始化S；

（2）第一次访问到根结点并不访问，而是入栈；

（3）中序遍历它的左子树，左子树遍历结束后，第二次遇到根结点，就将根结点（指针）退栈，并且访问根结点；然后中序遍历它的右子树。

（4）当需要退栈时，如果栈为空则结束。

Answer 2

如果是结点的定义中有深度这个属性，那么用一个队列就可以了。
队首放节点 队尾取出节点
比如：根节点放入队列 （开始只有这个一个节点在队列中）
然后呢 从队尾取出这个根节点 然后打散 把他的左右孩子放入对首（这时候有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就是最后一层了。

Answer 3

遍历一下,不用递归就广度遍历就好了