java二叉树深度不用递归,非递归实现

KLQ 2020-07-14 09:40:51 java常见问答 5754

之前给大家带来了java二叉树中所有距离为K的结点的相关内容,那么下面要给大家带来的就是java二叉树深度非递归实现的内容,一起来看看吧。

递归实现

利用层次遍历算法,设置变量level记录当前节点所在的层数,设置变量last指向当前层的最后一个节点,当处理完当前层的最后一个节点,让level指向+1操作。

设置变量cur记录当前层已经访问的节点的个数,在cur等于last的时候,该层访问结束。

层次遍历在求树的宽度、输出某一层节点,某一层节点个数,每一层节点个数都能够采用类似的算法。

树的宽度:

在树的深度算法的基础上面,加上一个记录访问过的层节点个数最多的变量max。

在访问每层前max和last比较,假如,max比较大,max不变,假如max小于last,将last赋值给max。

代码实现:

import java.util.LinkedList;
public class Deep
{
    //非递归实现  
    public int findDeep2(BiTree root)
    {
        if (root == null)
            return 0;
        BiTree current = null;
        LinkedList < BiTree > queue = new LinkedList < BiTree > ();
        queue.offer(root);
        int cur, last;
        int level = 0;
        while (!queue.isEmpty())
        {
            cur = 0; //记录本层已经遍历的节点个数  
            last = queue.size(); //当遍历完当前层以后,队列里元素全是下一层的元素,队列的长度是这一层的节点的个数  
            while (cur < last) //当还没有遍历到本层最后一个节点时循环  
            {
                current = queue.poll(); //出队一个元素  
                cur++;
                //把当前节点的左右节点入队(如果存在的话)  
                if (current.left != null)
                {
                    queue.offer(current.left);
                }
                if (current.right != null)
                {
                    queue.offer(current.right);
                }
            }
            level++; //每遍历完一层level+1  
        }
        return level;
    }
    public static void main(String[] args)
    {
        BiTree root = BiTree.buildTree();
        Deep deep = new Deep();
        System.out.println(deep.findDeep(root));
        System.out.println(deep.findDeep1(root));
        System.out.println(deep.findDeep2(root));
    }
}

java二叉树深度非递归的相关内容就给你介绍到这里了,你都了解了吗?更多二叉树java经典实例,可以继续来奇Q工具网了解哦。

推荐阅读:

java二叉树和为某一个值的路径如何实现?思路分享

java二叉树前序中序后序如何实现递归与非递归?

将二叉树变换为源二叉树的镜像如何实现?思路和实现