二叉树的非递归先序，中序，后序遍历

叁歲伎倆 2022-05-12 10:38 186阅读 0赞

### 前几天面试美团的java后台岗位，第一题就是手写二叉树非递归先序遍历，当时我就不乐意了。然后其实能想出来的，但是没私底下实现过，还真没把握给面试官，最后挂了。所以痛定思痛，我们来手写一下二叉树的非递归先序，中序和后序遍历，并对其中的逻辑部分进行步骤的讲解，我觉得一切的东西你只要给他赋予一定的规则，那么它就没那么难了（后面的部分不适合对数据结构不熟悉的同学） ###

/**
        	 * 非递归先序遍历
        	 * @param root
        	 */
            public void depthOrderTraversal(BinTree root){
            	if(root==null){
            		System.out.println("null");
            		return;
            	}
            	ArrayDeque<BinTree> stack=new ArrayDeque<BinTree>();
            	stack.push(root);
            	while(stack.isEmpty()==false){
            		BinTree node = stack.pop();
            		System.out.print(node.getData()+" ");
            		if(node.rChild!=null)
            			stack.push(node.rChild);
            		if(node.lChild!=null)
            			stack.push(node.lChild);
            	}
            }

非递归先序遍历需要借用栈（后进先出）这种数据结构，下面我梳理一下这个过程，分步骤ABC

A：将根节点传入进方法中，也就是当作参数传递过来，你可以在节点类中写一个getRoot()方法，返回他的节点对象

B：判断节点是否为空，为空就返回return;（什么都不用返回）。因为return;这样这个方法就结束了；（(●'◡'●)）

接下来的C-D我们讲解一下从栈到实现先序遍历的整个过程的逻辑梳理

C：创建一个栈，并将根节点率先加入到栈中(这里为什么用ArrayDeque来创建栈呢？因为网上说用做栈的时候性能比Stack好)

D：这里我们思考一个问题，到底用什么来做循环的条件，首先我们现在有两个东西在手里，一个栈，一个根节点数据，能改变的貌似也只有栈的size()了，所以我们通过判断栈是否为空来循环我们的先序遍历的逻辑部分

E-G我们就用三句话来简短的叙述一下过程

E：栈顶出栈并输出

F：“出栈”右孩子入栈(E中出栈的那个元素称为出栈)

G：”出栈“左孩子入栈

然后E-F整个过程包括在while循环当中，当栈中元素全部出栈的时候循环结束。

### 接下来我们讲一下二叉树非递归中序遍历 ###

/**
        	 * 非递归中序遍历
        	 * @param root
        	 */
            public void depthMidTraversal(BinTree root) {
                Stack<BinTree> s = new Stack<BinTree>();
                BinTree p = root;
                while(p != null || !s.empty()) {
                    while (p != null) {
                       s.push(p);
                       p = p.lChild;
                    }
                    p = s.pop();
                    System.out.print(p.getData()+" ");
                    if (p.rChild != null) {
                        p = p.rChild;
                    }
                    else p = null;
               } 
            }

下面我还是通过A-F的步骤讲解一下非递归中序遍历的过程

A：首先创建一个栈s (BinTree p = root 方便后序编写，我没试过直接用root来写行不行，我感觉应该按道理，逻辑来说应该不行)

B：确定循环条件，p节点不为空或者栈不为空

C-F：中间这个步骤我统一说一下，其实我支持大家通过Dubug来看一下这个过程，我想了想要用语言阐述太为难我这个理科生了，中间逻辑大家看代码吧。

### 非递归后序遍历 ###

/**
        	 * 非递归后序遍历
        	 * @param root
        	 */
            public void depthAfterTraversal(BinTree root){
        		Stack<BinTree> s = new Stack<BinTree>();
        		BinTree p = root;
        		while (p != null || !s.empty()) {
        			while(p != null) {
        				s.push(p);
        				p = p.lChild;
        			}
        			p = s.pop();
        			System.out.print(p.getData()+" ");
        			//这里需要判断一下，当前p是否为栈顶的左子树，如果是的话那么还需要先访问右子树才能访问根节点
        			//如果已经是不是左子树的话，那么说明左右子书都已经访问完毕，可以访问根节点了，所以讲p复制为NULL
        			//取根节点
        			if (!s.empty() && p == s.peek().lChild) {
        				p = s.peek().rChild;
        			}
        			else p = null;
        		}
            }

我把全部代码粘贴供大家参考，其中也有递归实现先序，中序，后序的方法，大家加油

import java.util.ArrayDeque;
    import java.util.ArrayList;
    import java.util.List;
    import java.util.Stack;
    import java.util.Vector;
    
    public class BinTree {
        	private BinTree lChild;//左孩子
        	private BinTree rChild;//右孩子
        	private BinTree root;//根节点
        	private Object data; //数据域
        	private List<BinTree> datas;//存储所有的节点
        	private Vector<Vector<Integer>> vec; 
        	private Vector<Integer> son;
        	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 preorder(BinTree root){
        		if(root!=null){
        			visit(root.getData());
        			preorder(root.lChild);
        			preorder(root.rChild);
        		}
        		
        	}
        	//中序遍历
        	public void inorder(BinTree root){
        		if(root!=null){
        			inorder(root.lChild);
        			visit(root.getData());
        			inorder(root.rChild);
        		}
        		
        	}
        	//后序遍历
        	public void afterorder(BinTree root){
        		if(root!=null){
        			afterorder(root.lChild);
        			afterorder(root.rChild);
        			visit(root.getData());
        		}
        		
        	}
        	
        	/**
        	 * 非递归先序遍历
        	 * @param root
        	 */
            public void depthOrderTraversal(BinTree root){
            	if(root==null){
            		System.out.println("null");
            		return;
            	}
            	ArrayDeque<BinTree> stack=new ArrayDeque<BinTree>();
            	stack.push(root);
            	while(stack.isEmpty()==false){
            		BinTree node = stack.pop();
            		System.out.print(node.getData()+" ");
            		if(node.rChild!=null)
            			stack.push(node.rChild);
            		if(node.lChild!=null)
            			stack.push(node.lChild);
            	}
            }
            	
            	
            /**
        	 * 非递归中序遍历
        	 * @param root
        	 */
            public void depthMidTraversal(BinTree root) {
                Stack<BinTree> s = new Stack<BinTree>();
                BinTree p = root;
                while(p != null || !s.empty()) {
                    while (p != null) {
                       s.push(p);
                       p = p.lChild;
                    }
                    p = s.pop();
                    System.out.print(p.getData()+" ");
                    if (p.rChild != null) {
                        p = p.rChild;
                    }
                    else p = null;
               } 
            }
            
        	/**
        	 * 非递归后序遍历
        	 * @param root
        	 */
            public void depthAfterTraversal(BinTree root){
        		Stack<BinTree> s = new Stack<BinTree>();
        		BinTree p = root;
        		while (p != null || !s.empty()) {
        			while(p != null) {
        				s.push(p);
        				p = p.lChild;
        			}
        			p = s.pop();
        			System.out.print(p.getData()+" ");
        			//这里需要判断一下，当前p是否为栈顶的左子树，如果是的话那么还需要先访问右子树才能访问根节点
        			//如果已经是不是左子树的话，那么说明左右子书都已经访问完毕，可以访问根节点了，所以讲p复制为NULL
        			//取根节点
        			if (!s.empty() && p == s.peek().lChild) {
        				p = s.peek().rChild;
        			}
        			else p = null;
        		}
            }
            
            
        	
        	//层序遍历
    //    	public void levelOrder(BinTree root) {
    //    		if(root!=null){
    //    			
    //    			Queue<Pair<BinTree,Integer>> q = new LinkedList<>();
    //    			Map<BinTree,Integer> record = new HashMap<>();
    //    			record.put(root, 0);
    //    			q.offer(record);
    //    			while(!q.isEmpty()){
    //    				 int level = q.peek().values();
    //    				
    //    			}
    //    		}
    //    		
    //    		
    //    	}
        	private void visit(Object obj) {
        		System.out.print(obj+" ");
        	}
        	public Object getData() {
        		return data;
        	}
        	public BinTree getRoot() {
        		return root;
        	}
        	
        }

下面是调用这个类的main方法，大家加油，用Dubug看一下这个运行过程，比我用语言阐述要强的多

public class TestTree {
    	public static void main(String[] args) {
    		BinTree binTree=new BinTree();
    		Object[] objs={0,1,2,3,4,5,6,7};
    		binTree.createTree(objs);
    //		binTree.preorder(binTree.getRoot()); 先序遍历
    //		binTree.inorder(binTree.getRoot()); 中序遍历
    //		binTree.afterorder(binTree.getRoot()); //后序遍历
    //		binTree.depthOrderTraversal(binTree.getRoot()); //非递归先序遍历
    //		binTree.depthMidTraversal(binTree.getRoot());//非递归中序遍历
    		binTree.depthAfterTraversal(binTree.getRoot());
    	}
    }

觉得比较实在的点个关注，一起加油努力学习

二叉树的非递归先序，中序，后序遍历

发表评论取消回复

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

相关阅读