二叉树的三种遍历java实现

        二叉树的遍历主要有三种：分别是前序遍历，中序遍历，后序遍历。

BSATree.java

package com.bijian.study;

public abstract class BSATree<T extends Comparable<T>> {

	protected BSTNode<T> aRoot; // 根结点

	/**
	 * 节点
	 */
	protected class BSTNode<E> {
		E key; // 关键字(键值)
		BSTNode<E> left; // 左孩子
		BSTNode<E> right; // 右孩子
		BSTNode<E> parent; // 父结点

		public BSTNode(E key, BSTNode<E> parent, BSTNode<E> left, BSTNode<E> right) {
			this.key = key;
			this.parent = parent;
			this.left = left;
			this.right = right;
		}

		public BSTNode(E key, BSATree<T>.BSTNode<E> parent) {
			super();
			this.key = key;
			this.parent = parent;
		}
	}

	/**
	 * 创建二叉树
	 */
	protected abstract void createBSTree();

	/**
	 * 记录节点
	 * @param key
	 */
	private void takeNode(T key) {
		System.out.print(key + " ");
	}

	/**
	 * 前序遍历
	 * @param node
	 */
	private void preOrder(BSTNode<T> node) {
		if (node != null) {
			takeNode(node.key);
			preOrder(node.left);
			preOrder(node.right);
		}
	}

	protected void preOrder() {
		preOrder(aRoot);
	}

	/**
	 * 中序遍历
	 * @param node
	 */
	private void inOrder(BSTNode<T> node) {
		if (node != null) {
			inOrder(node.left);
			takeNode(node.key);
			inOrder(node.right);
		}
	}

	protected void inOrder() {
		inOrder(aRoot);
	}

	/**
	 * 后续遍历
	 * @param node
	 */
	private void postOrder(BSTNode<T> node) {
		if (node != null) {
			postOrder(node.left);
			postOrder(node.right);
			takeNode(node.key);
		}
	}

	protected void postOrder() {
		postOrder(aRoot);
	}
}

BSTree.java

package com.bijian.study;

public class BSTree extends BSATree<String> {

	@Override
	public void createBSTree() {
		
		aRoot = new BSTNode<String>("A", null);
		
		BSTNode<String> bNode = new BSTNode<String>("B", aRoot);
		BSTNode<String> cNode = new BSTNode<String>("C", aRoot);
		BSTNode<String> dNode = new BSTNode<String>("D", bNode);
		BSTNode<String> eNode = new BSTNode<String>("E", bNode);
		BSTNode<String> fNode = new BSTNode<String>("F", cNode);
		BSTNode<String> gNode = new BSTNode<String>("G", cNode);
		BSTNode<String> hNode = new BSTNode<String>("H", dNode);
		BSTNode<String> iNode = new BSTNode<String>("I", dNode);
		BSTNode<String> jNode = new BSTNode<String>("J", eNode);
		BSTNode<String> kNode = new BSTNode<String>("K", fNode);
		
		aRoot.left = bNode;
		aRoot.right = cNode;
		bNode.left = dNode;
		bNode.right = eNode;
		cNode.left = fNode;
		cNode.right = gNode;
		dNode.left = hNode;
		dNode.right = iNode;
		eNode.right = jNode;
		fNode.right = kNode;
	}

	public static void main(String[] args) {
		
		BSTree b = new BSTree();
		b.createBSTree();
		System.out.println("********************** 前序遍历 **********************");
		b.preOrder();
		System.out.println();
		System.out.println("********************** 中序遍历 **********************");
		b.inOrder();
		System.out.println();
		System.out.println("********************** 后序遍历 **********************");
		b.postOrder();
		System.out.println();
	}
}

运行结果：

********************** 前序遍历 **********************
A B D H I E J C F K G 
********************** 中序遍历 **********************
H D I B E J A F K C G 
********************** 后序遍历 **********************
H I D J E B K F G C A 

前序遍历：

中序遍历：

后序遍历：

文章来源：http://smallbug-vip.iteye.com/blog/2280781