java实现按层遍历二叉树

柔情只为你懂 2021-09-15 00:32 280阅读 0赞

按层实现遍历二叉树可以通过队列来实现。其主要思路如下：

> 1、先将根节点放入队列中
> 
> 2、每次都从队列中取出一个结点打印该结点的值
> 
> 3、若这个结点有子结点，则将它的子结点放入队列尾，知道队列为空。

实现代码如下：

import java.util.LinkedList;
    import java.util.Queue;
    
    public class LayerTranverse {
    
    	//按层遍历二叉树
    	public static void main(String[] args) {
    		BinaryTree1 biTree1=new BinaryTree1();
    		int[] data={2,8,7,4,9,3,1,6,5};
    		biTree1.buildTree1(data);
    		biTree1.layerTranverse();
    	}
    
    }
    class Node1{
    	public int data;
    	public Node1 left;
    	public Node1 right;
    	public Node1(int data){
    		this.data=data;
    		this.left=null;
    		this.right=null;
    	}	
    }
    class BinaryTree1{
    	private Node1 root;
    	public BinaryTree1(){
    		root=null;
    	}
    	//将data数据插入到排序的二叉树中
    	public void insert1(int data){
    		Node1 newNode1=new Node1(data);
    		if(root==null){
    			root=newNode1;
    		}else{
    			Node1 current=root;
    			Node1 parent;
    			while(true){
    				parent=current;
    				if(data<current.data){
    					current=current.left;
    					if(current==null){
    						parent.left=newNode1;
    						return;
    					}
    				}else{
    						current=current.right;
    						if(current==null){
    							parent.right=newNode1;
    							return;
    					}
    				}
    			}
    			
    		}
    	}
    	public void buildTree1(int[] data){
    		for(int i=0;i<data.length;i++){
    			insert1(data[i]);
    		}
    	}
    	public void layerTranverse(){
    		if(this.root==null){
    			return;
    		}
    		Queue<Node1> q=new LinkedList<Node1>();
    		q.add(this.root);
    		while(!q.isEmpty()){
    			Node1 n=q.poll();
    			System.out.print(n.data);
    			System.out.print(" ");
    			if(n.left!=null){
    				q.add(n.left);
    			}
    			if(n.right!=null){
    				q.add(n.right);
    			}
    		}
    	}
    }

运行结果为：

> 2 1 8 7 9 4 3 6 5