二叉树建立 二叉树遍历 二叉树 递归 非递归 先序 中序 后序 层序遍历

给定树结构和先序序列

二叉树递归创建：本质上和二叉树递归遍历一样，但是需要知道何时节点孩子为空，因此这里用#做分隔符。

先序建立：先给当前节点分配数据，然后创建左子树，然后创建又子树。

	public Node createTree(){//递归先序创建树
		if(index >= input.length){
			return null;
		}
		if(input[index]=='#'){
			index++;
			return null;
		}
		Node node = new Node();
		node.data = input[index++];
		node.left = createTree();//创建左子树
		node.right = createTree();//创建右子树
		return node;
	}

二叉树递归遍历比较简单，这里不在累述。

	public void preOrderTraverseRec(Node root){
		if(root==null){
			System.out.print("#");
			return;
		}
		System.out.print(root.data);
		preOrderTraverseRec(root.left);
		preOrderTraverseRec(root.right);
	}
	public void inOrderTraverseRec(Node root){
		if(root==null){
			System.out.print("#");
			return;
		}
		inOrderTraverseRec(root.left);
		System.out.print(root.data);
		inOrderTraverseRec(root.right);
	}
	public void postOrderTraverseRec(Node  root){
		if(root==null){
			System.out.print("#");
			return;
		}
		postOrderTraverseRec(root.left);
		postOrderTraverseRec(root.right);
		System.out.print(root.data);
	}

二叉树非递归先序1：从根节点开始，如果当前要访问的结点不为空就访问，然后将节点压入栈，开始遍历节点的左孩子；否则，从栈中弹出一个节点，弹出节点时就开始遍历节点的右孩子（因为当前节点和左孩子都访问过了）。

	public void preOrderTraverse1(Node root){
		Stack<Node> stack = new Stack<Node>();
		if(root == null){
			return;
		}
		Node node = root;
		while(!stack.empty()||node!=null){
			if(node != null){//当前要访问的结点不为空就访问，然后将节点压入栈，访问节点的左孩子
				System.out.print(node.data);
				stack.push(node);
				node = node.left;
			}else{
				node = stack.pop();
				node = node.right;
			}

		}
	}

二叉树非递归先序2：从根节点开始，根节点入栈。每次都弹出一个节点访问，因为栈是后进先出的，所以先看右孩子是否为空，不为空就进栈，然后同理检查左孩子。

	public void preOrderTraverse2(Node root){
		Stack<Node> stack = new Stack<Node>();
		if(root == null){
			return;
		}
		
		Node node = root;
		stack.push(node);
		while(!stack.empty()){
			node = stack.pop();
			System.out.print(node.data);
			if(node.right!=null){
				stack.push(node.right);
			}
			if(node.left != null){
				stack.push(node.left);
			}
		}
	}

二叉树中序非递归遍历：从根节点开始。从当前节点直接走到最左边，然后弹出的时候访问，访问完开始遍历右子树。

	public void inOrderTraverse(Node root){
		Stack<Node> stack = new Stack<Node>();
		Node node = root;
		while(!stack.empty()||node!=null){
			while(node != null){
				stack.push(node);
				node = node.left;
			}
			node = stack.pop();
			System.out.print(node.data);
			node = node.right;
		}
	}

二叉树后序非递归遍历：因为判断当前结点是否需要访问，需要根据上一个节点是不是它的孩子，所以需要用一个pre节点指向上次访问的节点。从根节点开始：1.首先判断左边孩子是否需要访问，如果当前结点左孩子不为空，并且上次访问的节点不是左孩子也不是右孩子，需要先访问左孩子。2.然后判断右边孩子是否需要访问，如果当前结点右孩子不为空，并且上次访问的节点不是右孩子，需要访问右孩子。3.如果以上都不需要访问，说明左右孩子都访问过了，可以访问当前结点。

	public void postOrderTraverse(Node root){
		Stack<Node> stack = new Stack<Node>();
		Node cur = root;
		Node pre = root;
		stack.push(cur);
		while(!stack.empty()){
			cur = stack.peek();
			if(cur.left !=null && pre!=cur.left&&pre!=cur.right){
				stack.push(cur.left);
			}else if(cur.right != null && pre!=cur.right){
				stack.push(cur.right);
			}else{
				cur = stack.pop();
				System.out.print(cur.data);
				pre = cur;
			}
		}
	}

二叉树层序非递归遍历：直接使用一个队列，每次先访问当前结点，然后出队，访问完看是否有左孩子，有就入队；然后看是否有右孩子，有也入队。（可以这样理解，当前层，从左往右访问，访问的时候当前节点左右孩子入队，这样下一层的顺序就是从左向右按顺序的）

	public void levelOrderTraverse(Node root){
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(root);
		Node node = root;
		while(!queue.isEmpty()){
			node = queue.poll();
			System.out.print(node.data);
			if(node.left != null){
				queue.add(node.left);
			}
			if(node.right != null){
				queue.add(node.right);
			}
		}
	}

下面贴一下总体的代码：

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class BinaryTree {
	/*
	 *           A
	 *          / \
	 *         /   \
	 *        /     \
	 *       /       \
	 *      B         C
	 *     / \       / \
	 *    D   E     F   G
	 *   /     \   / \ / \
	 *  H       I J   KL  M
	 */
	static class Node{
		char data;
		Node left;
		Node right;
	}
	
	String str  = "ABDH###E#I##CFJ##K##GL##M##";
	int index = 0;
	char [] input = str.toCharArray();
	
	public static void main(String[] args) {
		BinaryTree bt = new BinaryTree();
		Node root = bt.createTree();
		System.out.println("-----递归先序遍历------");
		bt.preOrderTraverseRec(root);
		System.out.println("\n-----递归中序遍历------");
		bt.inOrderTraverseRec(root);
		System.out.println("\n-----递归后序遍历------");
		bt.postOrderTraverseRec(root);
		System.out.println();
		
		System.out.println("\n-----非递归先序遍历1------");
		bt.preOrderTraverse1(root);
		System.out.println("\n-----非递归先序遍历3------");
		bt.preOrderTraverse2(root);
		System.out.println("\n-----非递归中序遍历------");
		bt.inOrderTraverse(root);
		System.out.println("\n-----非递归后序遍历------");
		bt.postOrderTraverse(root);
		System.out.println("\n-----非递归层序遍历------");
		bt.levelOrderTraverse(root);
		
	}

	public Node createTree(){//递归先序创建树
		if(index >= input.length){
			return null;
		}
		if(input[index]=='#'){
			index++;
			return null;
		}
		Node node = new Node();
		node.data = input[index++];
		node.left = createTree();//创建左子树
		node.right = createTree();//创建右子树
		return node;
	}
	
	
	public void preOrderTraverseRec(Node root){
		if(root==null){
			System.out.print("#");
			return;
		}
		System.out.print(root.data);
		preOrderTraverseRec(root.left);
		preOrderTraverseRec(root.right);
	}
	public void inOrderTraverseRec(Node root){
		if(root==null){
			System.out.print("#");
			return;
		}
		inOrderTraverseRec(root.left);
		System.out.print(root.data);
		inOrderTraverseRec(root.right);
	}
	public void postOrderTraverseRec(Node  root){
		if(root==null){
			System.out.print("#");
			return;
		}
		postOrderTraverseRec(root.left);
		postOrderTraverseRec(root.right);
		System.out.print(root.data);
	}
	
	public void preOrderTraverse1(Node root){
		Stack<Node> stack = new Stack<Node>();
		if(root == null){
			return;
		}
		Node node = root;
		while(!stack.empty()||node!=null){
			if(node != null){//当前要访问的结点不为空就访问，然后将节点压入栈，访问节点的左孩子
				System.out.print(node.data);
				stack.push(node);
				node = node.left;
			}else{
				node = stack.pop();
				node = node.right;
			}

		}
	}
	
	public void preOrderTraverse2(Node root){
		Stack<Node> stack = new Stack<Node>();
		if(root == null){
			return;
		}
		
		Node node = root;
		stack.push(node);
		while(!stack.empty()){
			node = stack.pop();
			System.out.print(node.data);
			if(node.right!=null){
				stack.push(node.right);
			}
			if(node.left != null){
				stack.push(node.left);
			}
		}
	}
	
	public void inOrderTraverse(Node root){
		Stack<Node> stack = new Stack<Node>();
		Node node = root;
		while(!stack.empty()||node!=null){
			while(node != null){
				stack.push(node);
				node = node.left;
			}
			node = stack.pop();
			System.out.print(node.data);
			node = node.right;
		}
	}
	
	public void postOrderTraverse(Node root){
		Stack<Node> stack = new Stack<Node>();
		Node cur = root;
		Node pre = root;
		stack.push(cur);
		while(!stack.empty()){
			cur = stack.peek();
			if(cur.left !=null && pre!=cur.left&&pre!=cur.right){
				stack.push(cur.left);
			}else if(cur.right != null && pre!=cur.right){
				stack.push(cur.right);
			}else{
				cur = stack.pop();
				System.out.print(cur.data);
				pre = cur;
			}
		}
	}
	
	public void levelOrderTraverse(Node root){
		Queue<Node> queue = new LinkedList<Node>();
		queue.add(root);
		Node node = root;
		while(!queue.isEmpty()){
			node = queue.poll();
			System.out.print(node.data);
			if(node.left != null){
				queue.add(node.left);
			}
			if(node.right != null){
				queue.add(node.right);
			}
		}
	}
}