我的理智小窝~

import junit.framework.TestCase;

public class TreeWalkerTest extends TestCase {

	// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
	// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
	// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n
	public void testSimpleTreeWalk() {

		IVisitor preOrderTraverser= new TreePreOrderTraverser();
		IVisitor inOrderTraverser= new TreeInOrderTraverser();
		IVisitor postOrderTraverser= new TreePostOrderTraverser();
		
		TreeNode a= new TreeNode("a");
		TreeNode b= new TreeNode("b");
		TreeNode c= new TreeNode("c");
		a.setLeftChild(b);
		a.setRightChild(c);
		TreeNode d= new TreeNode("d");
		TreeNode e= new TreeNode("e");
		b.setLeftChild(d);
		b.setRightChild(e);
		
		a.accept(preOrderTraverser);
		assertEquals("abdec",preOrderTraverser.getOutString().toString());
		
		a.accept(inOrderTraverser);
		assertEquals("dbeac",inOrderTraverser.getOutString().toString());
		
		a.accept(postOrderTraverser);
		assertEquals("debca",postOrderTraverser.getOutString().toString());
	}

}

public interface ITreeNode {

	public abstract boolean isLeaf();

	public abstract TreeNode getRightChild();

	public abstract void setRightChild(TreeNode rightChild);

	public abstract TreeNode getLeftChild();

	public abstract void setLeftChild(TreeNode leftChild);

	public abstract String getTreeNodeString();

}

public interface IVisitable {
	public abstract void accept(IVisitor v);
}

public interface IVisitor {
	public abstract void visit(TreeNode node);
	public abstract StringBuffer getOutString();
}

public class TreeInOrderTraverser implements IVisitor {
	// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
	// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
	// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n

	// 基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？
	// 到了后面才明白，这是不同的应用需要的。
	// 例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；
	// 而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
	// 实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。
	// 对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。
	// 利用C++的封装和重载特性，这些遍历方法能很清晰的表达。
	private StringBuffer outString = new StringBuffer();;

	public void visit(TreeNode node) {

		visitChild(node.getLeftChild());
		getOutString().append(node.getTreeNodeString());//visit root
		visitChild(node.getRightChild());

	}
	
	private void visitChild(TreeNode childNode) {
		if ( childNode!= null) {
			childNode.accept(this);
		}
	}
	
	public StringBuffer getOutString() {
		return this.outString;
	}
}

public class TreeNode implements IVisitable, ITreeNode {

	private TreeNode rightChild;
	private TreeNode leftChild;
	protected String treeNodeString;

	public TreeNode() {
		super();
	}

	public TreeNode(String treeNodeString) {
		this.treeNodeString = treeNodeString;
	}

	public boolean equals(Object anotherTreeNode) {
		if (anotherTreeNode instanceof TreeNode) {
			return treeNodeString.equals(((TreeNode) anotherTreeNode)
					.getTreeNodeString());
		} else {
			return false;
		}
	}

	public boolean isLeaf() {
		return getLeftChild() == null && getRightChild() == null;
	}

	public TreeNode getRightChild() {
		return rightChild;
	}

	public void setRightChild(TreeNode rightChild) {
		this.rightChild = rightChild;
	}

	public TreeNode getLeftChild() {
		return leftChild;
	}

	public void setLeftChild(TreeNode leftChild) {
		this.leftChild = leftChild;
	}

	public String getTreeNodeString() {
		return this.treeNodeString;
	}

	public void accept(IVisitor v) {
			v.visit(this);
	}

}

public class TreePostOrderTraverser implements IVisitor {
	// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
	// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
	// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n

	// 基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？
	// 到了后面才明白，这是不同的应用需要的。
	// 例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；
	// 而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
	// 实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。
	// 对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。
	// 利用C++的封装和重载特性，这些遍历方法能很清晰的表达。
	private StringBuffer outString= new StringBuffer();
	
	public void visit(TreeNode node) {

		visitChild(node.getLeftChild());
		visitChild(node.getRightChild());
		getOutString().append(node.getTreeNodeString());
	}
	private void visitChild(TreeNode childNode) {
		if ( childNode!= null) {
			childNode.accept(this);
		}
	}
	public StringBuffer getOutString() {
		return outString;
	}

}

public class TreePreOrderTraverser implements IVisitor {
	// 对T进行前序遍历是先访问树根n,然后依次前序遍历T1,T2,..,Tk。
	// 对T进行中序遍历是先中序遍历T1，然后访问树根n，接着依次对T2,T2,..,Tk进行中序遍历。
	// 对T进行后序遍历是先依次对T1,T2,..,Tk进行后序遍历，最后访问树根n

	// 基本上有4种遍历方法，先、中、后根，逐层。当初我对这个很迷惑，搞这么多干什么？
	// 到了后面才明白，这是不同的应用需要的。
	// 例如，判断两个二叉树是否相等，只要子树根节点不同，那么就不等，显然这时要用先序遍历；
	// 而删除二叉树，必须先删除左右子树，然后才能删除根节点，这时就要用后序遍历。
	// 实际上，搞这么多遍历方法，根本原因是在内存中储存的树是非线性结构。
	// 对于用数组储存的二叉树，这些名目繁多的方法都是没有必要的。
	// 利用C++的封装和重载特性，这些遍历方法能很清晰的表达。
	private StringBuffer outString = new StringBuffer();;

	public void visit(TreeNode node) {
		getOutString().append(node.getTreeNodeString());
		visitChild(node.getLeftChild());
		visitChild(node.getRightChild());
	}

	private void visitChild(TreeNode childNode) {
		if ( childNode!= null) {
			childNode.accept(this);
		}
	}

	public StringBuffer getOutString() {
		return outString;
	}

}