非递归实现二叉树的层次遍历

妖狐艹你老母 2022-08-09 06:30 234阅读 0赞

非递归的层次遍历其实很简单。利用了队列先进先出的特点。
先将根节点入队。如果队列不为空，那么获得队首元素，对其访问。如果它的左子树不为空，那么加入队列，如果它的右子树不为空，那么加入队列

  1. /**
  2.      * 层次遍历
  3.      * @param root
  4.      */
  5.     public void levelOrder(Node root){
  6.         if(root==null){
  7.             return;
  8.         }
  9.         Queue<Node> queue=new LinkedList<Node>();
  10.         Node node=root;
  11.         queue.add(node);
  12.         while(!queue.isEmpty()){
  13.             node=queue.poll();
  14.             visted(node);
  15.             if(node.leftChild!=null){
  16.                 queue.add(node.leftChild);
  17.             }
  18.             if(node.rightChild!=null){
  19.                 queue.add(node.rightChild);
  20.             }
  21.         }
  22.     }

发表评论

表情：
评论列表 （有 0 条评论，234人围观）

还没有评论，来说两句吧...

相关阅读