二叉树的遍历

 

用递归和非递归的方法遍历二叉树.

先建立一个二叉树:

代码如下：

 

 

static class Node {
		Node left;
		Node right;
		String value;
		public Node(String value, Node left, Node right){
			this.value = value;
			this.left = left;
			this.right = right;
		}
	}
	public static Node creatTree(){
		//左子树
		Node k = new Node("k", null, null);
		Node l = new Node("l", null, null);
		Node h = new Node("h", k, l);
		Node i = new Node("i", null, null);
		Node e = new Node("e", h, i);
		Node d = new Node("d", null, null);
		Node b = new Node("b", d, e);
		//右子树
		Node j = new Node("j", null, null);
		Node g = new Node("g", null, j);
		Node f = new Node("f", null, null);
		Node c = new Node("c", f, g);
		Node a = new Node("a", b, c);
		
		return a;
	}
	/**
	 * 深度优先，递归遍历（前序，中序，后续）
	 * @param root 
	 */
	public static void recursionDepthFirst(Node node){
		if(node == null){
		return;
		}
		//前序System.out.println(node.value);
		recursionDepthFirst(node.left);
		//中序System.out.println(node.value);
		recursionDepthFirst(node.right);
		//后序System.out.println(node.value);
	}
	/**
	 * 深度优先，非递归遍历（前序，中序）
	 * @param node
	 */
	public static void inOrPreOrderDepthFirst(Node node){
		Stack<Node> stack = new Stack<Node>();
		while(node != null || !stack.isEmpty()){
			while(node != null){
				//前序System.out.println(node.value);
				stack.push(node);
				node = node.left;
			}
			if(!stack.isEmpty()){
				node = stack.pop();
				//中序System.out.println(node.value);
				node = node.right;
			}
		}
	}
	/**
	 * 深度优先，非递归遍历（后序）
	 * @param node
	 */
	public static void postOrderDepthFirst(Node node){
		Stack<Node> stack = new Stack<Node>();
		//待实现
	}
	/**
	 * 宽度优先遍历
	 */
	public static void breadthFirst(Node node){
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(node);
		while(!queue.isEmpty()){
			Node n = queue.poll();
			System.out.println(n.value);
			if(n.left != null){
				queue.add(n.left);
			}
			if(n.right != null){
				queue.add(n.right);
			}
		}
	}

 

 

其中非递归方式遍历有很多写法，可以看 http://robinsoncrusoe.iteye.com/blog/808526