二叉树的先序、中序、后序、层序遍历的递归实现与非递归实现

不念不忘少年蓝@ 2022-04-10 09:30 167阅读 0赞

**1.总结深度优先与广度优先的区别**

1） 二叉树的深度优先遍历的非递归的通用做法是采用栈，广度优先遍历的非递归的通用做法是采用队列。  
2） 深度优先遍历：对每一个可能的分支路径深入到不能再深入为止，而且每个结点只能访问一次。要特别注意的是，二叉树的深度优先遍历比较特殊，可以细分为先序遍历、中序遍历、后序遍历。具体说明如下：  
先序遍历：对任一子树，先访问根，然后遍历其左子树，最后遍历其右子树。  
中序遍历：对任一子树，先遍历其左子树，然后访问根，最后遍历其右子树。  
后序遍历：对任一子树，先遍历其左子树，然后遍历其右子树，最后访问根。  
广度优先遍历：又叫层次遍历，从上往下对每一层依次访问，在每一层中，从左往右（也可以从右往左）访问结点，访问完一层就进入下一层，直到没有结点可以访问为止。　　　  
3）深度优先搜素算法：不全部保留结点，占用空间少；有回溯操作(即有入栈、出栈操作)，运行速度慢。  
广度优先搜索算法：保留全部结点，占用空间大； 无回溯操作(即无入栈、出栈操作)，运行速度快。  
通常 深度优先搜索法不全部保留结点，扩展完的结点从数据库中弹出删去，这样，一般在数据库中存储的结点数就是深度值，因此它占用空间较少。  
所以，当搜索树的结点较多，用其它方法易产生内存溢出时，深度优先搜索不失为一种有效的求解方法。 　  
广度优先搜索算法，一般需存储产生的所有结点，占用的存储空间要比深度优先搜索大得多，因此，程序设计中，必须考虑溢出和节省内存空间的问题。

但广度优先搜索法一般无回溯操作，即入栈和出栈的操作，所以运行速度比深度优先搜索要快些

**2.二叉树的先序、中序、后序、层序遍历的递归实现与非递归实现**

import java.util.ArrayList;
    import java.util.LinkedList;
    import java.util.List;
    import java.util.Queue;
    import java.util.Stack;
    
    public class BinTree {
    private BinTree lChild;
    private BinTree rChild;
    private BinTree root;
    private Object data;
    private List<BinTree> datas;
    
    public BinTree(BinTree lChild, BinTree rChild, Object data) {
    	super();
    	this.lChild = lChild;
    	this.rChild = rChild;
    	this.data = data;
    }
    
    public BinTree(Object data) {
    	this(null,null,data);                                                                          
    }
    public BinTree(){
    	super();
    }
    //创建二叉树
    public void createTree(Object[] objs){
    	datas=new ArrayList<BinTree>();
    	for (Object object:objs) {
    		datas.add(new BinTree(object));
    	}
    	root=datas.get(0);
    	for (int i = 0; i < objs.length/2; i++) {
    		datas.get(i).lChild=datas.get(i*2+1);
    		if(i*2+2<datas.size()){
    			datas.get(i).rChild=datas.get(i*2+2);
    		}	
    	}
    }
    //先序遍历非递归方法(递归实现)
    public void preorder1(BinTree root){
    	Stack<BinTree> stack =new Stack<BinTree>();
    	while(root!=null||!stack.isEmpty()){
    		while(root!=null){
    		visit(root.getData());
    		stack.push(root);
    		root=root.lChild;
    		}
    		if(!stack.isEmpty()){
    		root=stack.pop();
    		root=root.rChild;	
    		}
    	}	
    }
    //先序遍历递归方法
    public void preorder(BinTree root){
    	if(root!=null){
    		visit(root.getData());
    		preorder(root.lChild);
    		preorder(root.rChild);	
    	}
    }
    //中序遍历非递归方法(堆栈实现)
    public void inorder1(BinTree root){
    	Stack<BinTree> stack=new Stack<BinTree>();
    	while(root!=null||!stack.isEmpty()){
    	while(root!=null){
    	stack.push(root);
    	root=root.lChild;
    	}
    	if(!stack.isEmpty()){
    	root=stack.pop();
    	visit(root.getData());
    	root=root.rChild;
    	}
    	}
    }
    
    //中序遍历递归方法
    public void inorder(BinTree root){
    	if(root!=null){
    		inorder(root.lChild);
    		visit(root.getData());
    		inorder(root.rChild);		
    	}	
    }
    //后序遍历非递归方法(堆栈实现)
    public void postorder1(BinTree root){
    	Stack<BinTree> stack=new Stack<BinTree>();
    	Stack<Integer> stack1 = new Stack<Integer>();
    	int i=1;
    	while(root!=null||!stack.isEmpty()){
    	while(root!=null){
    	stack.push(root);
    	stack1.push(0);
    	root=root.lChild;
    	}
    	 while(!stack.empty() && stack1.peek() == i)
         {
             stack1.pop();
            visit(stack.pop().getData());
         }
         if(!stack.empty())
         {
             stack1.pop();
             stack1.push(1);
             root = stack.peek();
             root = root.rChild;
         }
      }
    }
    //后序遍历递归方法(广度优先遍历)
    public void postorder(BinTree root){
    	if(root!=null){
    		postorder(root.lChild);
    		postorder(root.rChild);
    		visit(root.data);		
    	}	
    }
    //层序遍历递归方法
    public void levelorder(BinTree root,int i) {
    	if(root!=null&&i!=0){
    	if(i==1){
    	visit(root.getData());
    	}
    	levelorder(root.lChild,i-1);
    	levelorder(root.rChild,i-1);
    	}
    }
    //遍历树的高度
    public void height(BinTree root,Object[] objs){
    	if(root!=null){
    	//求当前节点的高度 
      double a=objs.length;
      int dep= (int) (Math.log(a)/Math.log(2))+2;
      for (int i = 0; i <=dep; i++) {
    	  levelorder(root,i);
    }
    	}
    }
    //层序遍历非递归实现(队列)(广度优先遍历)
    public void levelorder1(BinTree root) {
    	Queue<BinTree> queue = new LinkedList<BinTree>();
    	while(root!=null){
    		visit(root.getData());
    		if(root.lChild!=null)
    		queue.add(root.lChild);	
    		if(root.rChild!=null)
            queue.add(root.rChild);		
    		root=queue.poll();
    	}
    }
    
    //深度优先遍历
    public void visit(Object obj){
    	System.out.print(obj+"");
    }
    public Object getData(){	
    return data;
    }
    public BinTree getRoot(){
    	return root;
    }
    
    
    	public static void main(String[] args) {
    		BinTree binTree=new BinTree();
    		Object[] objs={'a','b','c','d','e','f','g','h'};
    		binTree.createTree(objs);       
    		binTree.postorder(binTree.getRoot());
    		System.out.println("后序遍历");
    		binTree.inorder(binTree.getRoot());
    		System.out.println("中序遍历");
    		binTree.preorder(binTree.getRoot());
    		System.out.println("先序遍历");
    		binTree.height(binTree.getRoot(),objs);
    		System.out.println("层序遍历(广度优先遍历)");
    		binTree.inorder1(binTree.getRoot());
    		System.out.println("中序遍历非递归实现");
    		binTree.preorder1(binTree.getRoot());
    		System.out.println("先序遍历非递归实现");
    		binTree.postorder1(binTree.getRoot());
    		System.out.println("后序遍历非递归实现");
    		binTree.levelorder1(binTree.getRoot());
    		System.out.println("层序遍历非递归实现(广度优先遍历)");
    	}
    	}

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjcxNDYx_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMjcxNDYx_size_16_color_FFFFFF_t_70]: /images/20220401/0103a5121e9c48e98bacdf545f56835c.png