JAVA实现二叉树的遍历的非递归算法及递归算法（前序，中序，后序，层次）

墨蓝 2022-08-21 13:48 25阅读 0赞

/*遍历是对树的一种最基本的运算，所谓遍历二叉树，就是按一定的规则和顺序走遍二叉树的所有结点，使每一个结点都被访问一次，而且只被访问一次。由于二叉树是非线性结构，因此，树的遍历实质上是将二叉树的各个结点转换成为一个线性序列来表示。 
    　　设L、D、R分别表示遍历左子树、访问根结点和遍历右子树， 则对一棵二叉树的遍历有三种情况：DLR（称为先根次序遍历），LDR（称为中根次序遍历），LRD （称为后根次序遍历）。 
    　　(1)先序遍历 
    　　访问根；按先序遍历左子树；按先序遍历右子树 
    　　(2)中序遍历 
    　　按中序遍历左子树；访问根；按中序遍历右子树 
    　　(3)后序遍历 
    　　按后序遍历左子树；按后序遍历右子树；访问根 
    　　（4）层次遍历 
    　　即按照层次访问，通常用队列来做。访问根，访问子女，再访问子女的子女（越往后的层次越低）（两个子女的级别相同） 
    */

public class BTNode {
    	private char key;
    	private BTNode left, right;
    
    	public BTNode(char key) {
    		this(key, null, null);
    	}
    
    	public BTNode(char key, BTNode left, BTNode right) {
    		this.key = key;
    		this.left = left;
    		this.right = right;
    	}
    
    	public char getKey() {
    		return key;
    	}
    
    	public void setKey(char key) {
    		this.key = key;
    	}
    
    	public BTNode getLeft() {
    		return left;
    	}
    
    	public void setLeft(BTNode left) {
    		this.left = left;
    	}
    
    	public BTNode getRight() {
    		return right;
    	}
    
    	public void setRight(BTNode right) {
    		this.right = right;
    	}
    }

import java.util.LinkedList;
    import java.util.Stack;
    
    public class BinTree {
    	protected BTNode root;
    
    	public BinTree(BTNode root) {
    		this.root = root;
    	}
    
    	public BTNode getRoot() {
    		return root;
    	}
    
    	/** 构造树 */
    	public static BTNode init() {
    		BTNode a = new BTNode('A');
    		BTNode b = new BTNode('B', null, a);
    		BTNode c = new BTNode('C');
    		BTNode d = new BTNode('D', b, c);
    		BTNode e = new BTNode('E');
    		BTNode f = new BTNode('F', e, null);
    		BTNode g = new BTNode('G', null, f);
    		BTNode h = new BTNode('H', d, g);
    		return h;// root
    	}
    
    	/** 访问节点 */
    	public static void visit(BTNode p) {
    		System.out.print(p.getKey() + " ");
    	}
    
    	/** 递归实现前序遍历 */
    	protected static void preorder(BTNode p) {
    		if (p != null) {
    			visit(p);
    			preorder(p.getLeft());
    			preorder(p.getRight());
    		}
    	}
    
    	/** 递归实现中序遍历 */
    	protected static void inorder(BTNode p) {
    		if (p != null) {
    			inorder(p.getLeft());
    			visit(p);
    			inorder(p.getRight());
    		}
    	}
    
    	/** 递归实现后序遍历 */
    	protected static void postorder(BTNode p) {
    		if (p != null) {
    			postorder(p.getLeft());
    			postorder(p.getRight());
    			visit(p);
    		}
    	}
    
    	/** 非递归实现前序遍历 */
    	protected static void iterativePreorder(BTNode p) {
    		Stack<BTNode> stack = new Stack<BTNode>();
    		if (p != null) {
    			stack.push(p);
    			while (!stack.empty()) {
    				p = stack.pop();
    				visit(p);
    				if (p.getRight() != null)
    					stack.push(p.getRight());
    				if (p.getLeft() != null)
    					stack.push(p.getLeft());
    			}
    		}
    	}
    
    	/** 非递归实现后序遍历 */
    	protected static void iterativePostorder(BTNode p) {
    		BTNode q = p;
    		Stack<BTNode> stack = new Stack<BTNode>();
    		while (p != null) {
    			// 左子树入栈
    			for (; p.getLeft() != null; p = p.getLeft())
    				stack.push(p);
    			// 当前节点无右子或右子已经输出
    			while (p != null && (p.getRight() == null || p.getRight() == q)) {
    				visit(p);
    				q = p;// 记录上一个已输出节点
    				if (stack.empty())
    					return;
    				p = stack.pop();
    			}
    			// 处理右子
    			stack.push(p);
    			p = p.getRight();
    		}
    	}
    
    	/** 非递归实现中序遍历 */
    	protected static void iterativeInorder(BTNode p) {
    		Stack<BTNode> stack = new Stack<BTNode>();
    		while (p != null) {
    			while (p != null) {
    				if (p.getRight() != null)
    					stack.push(p.getRight());// 当前节点右子入栈
    				stack.push(p);// 当前节点入栈
    				p = p.getLeft();
    			}
    			p = stack.pop();
    			while (!stack.empty() && p.getRight() == null) {//没有右子树，直接出栈
    				visit(p);
    				p = stack.pop();
    			}
    			visit(p);有右子树，循环
    			if (!stack.empty())
    				p = stack.pop();
    			else
    				p = null;
    		}
    	}
    	
    	 //level order  
        public static void levelOrder(BTNode p){  
            if(p==null)return;  
            LinkedList<BTNode> queue=new LinkedList<BTNode>();  
            queue.add(p);  
            while(!queue.isEmpty()){  
            	BTNode temp=queue.remove();  
               visit(temp);
                if(temp.getLeft()!=null){  
                    queue.add(temp.getLeft());  
                }  
                if(temp.getRight() != null){  
                    queue.add(temp.getRight());  
                }  
            }  
        }  
    
    	public static void main(String[] args) {
    		BinTree tree = new BinTree(init());
    		System.out.print(" Pre-Order:");
    		preorder(tree.getRoot());
    		System.out.println();
    		System.out.print("　In-Order:");
    		inorder(tree.getRoot());
    		System.out.println();
    		System.out.print("Post-Order:");
    		postorder(tree.getRoot());
    		System.out.println();
    		System.out.print(" Pre-Order:");
    		iterativePreorder(tree.getRoot());
    		System.out.println();
    		System.out.print("　In-Order:");
    		iterativeInorder(tree.getRoot());
    		System.out.println();
    		System.out.print("Post-Order:");
    		iterativePostorder(tree.getRoot());
    		System.out.println();
    		System.out.print("level:");
    		levelOrder(tree.getRoot());
    		System.out.println();
    	}
    }