データ構造学習のツリー

public class TreeNode implements Cloneable {

	private Object data;
	private TreeNode leftChild;
	private TreeNode rightChild;
	private TreeNode parent;
	private int level;
	private int lLevel;
	private int rLevel;
	
	public TreeNode(Object data){
		this(data, null, null, null);
	}
	public TreeNode(Object data, TreeNode lc, TreeNode rc, TreeNode p){
		this.data = data;
		this.leftChild = lc;
		this.rightChild = rc;
		this.parent = p;
	}

	public Object clone(){
		return new TreeNode(this.data);
	}
	
	public Object getData() {
		return data;
	}

	public void setData(Object data) {
		this.data = data;
	}

	public TreeNode getLeftChild() {
		return leftChild;
	}

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

	public TreeNode getRightChild() {
		return rightChild;
	}

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

	public TreeNode getParent() {
		return parent;
	}

	public void setParent(TreeNode parent) {
		this.parent = parent;
	}
	public int getLevel() {
		return level;
	}
	public void setLevel(int level) {
		this.level = level;
	}
	public int getlLevel() {
		return lLevel;
	}
	public void setlLevel(int lLevel) {
		this.lLevel = lLevel;
	}
	public int getrLevel() {
		return rLevel;
	}
	public void setrLevel(int rLevel) {
		this.rLevel = rLevel;
	}
}

public class BinaryTree {
	public static final boolean LEFT = true;
	public static final boolean RIGHT = false;
	private TreeNode root  = null;
	private int level = 0;//  
	private int lLevel = 0;//   
	private int rLevel = 0;//   
	private int nodeNumber = 0;//   
	private List<TreeNode> preOrderList = new ArrayList<TreeNode>();
	private List<TreeNode> inOrderList = new ArrayList<TreeNode>();
	private List<TreeNode> postOrderList = new ArrayList<TreeNode>();
	private List<TreeNode> levelOrderList = new ArrayList<TreeNode>();
	private List<TreeNode> levelQueue = new ArrayList<TreeNode>();
	
	public TreeNode getRoot() {
		return root;
	}

	public int getLevel() {
		return level;
	}

	public int getNodeNumber() {
		return nodeNumber;
	}
	
	public int getlLevel() {
		return lLevel;
	}

	public int getrLevel() {
		return rLevel;
	}

	public List<TreeNode> getPreOrderList() {
		return preOrderList;
	}

	public List<TreeNode> getInOrderList() {
		return inOrderList;
	}

	public List<TreeNode> getPostOrderList() {
		return postOrderList;
	}

	public List<TreeNode> getLevelOrderList() {
		return levelOrderList;
	}

	/**
	 *     ,                   ，
	 *                                
	 *   parent  ，           
	 * @param parent    
	 * @param node    
	 * @param flag true-    false-   
	 */
	public void insertNode(TreeNode parent, TreeNode node, boolean flag){
		if(parent  == null){
			this.root = node;
			node.setLevel(1);
			this.nodeNumber++;//     1
			this.level++;//    1
			return;
		}
		if(flag == BinaryTree.LEFT){
			TreeNode parentLeftChild = parent.getLeftChild();
			if(parentLeftChild == null){
				parent.setLeftChild(node);
				node.setParent(parent);
			}else{
				insertNode(parentLeftChild, node, flag);
			}
		}else{
			TreeNode parentRightChild = parent.getRightChild();
			if(parentRightChild == null){
				parent.setRightChild(node);
				node.setParent(parent);
			}else{
				insertNode(parentRightChild, node, flag);
			}
		}
		node.setLevel(parent.getLevel()+1);
		this.nodeNumber++;//     1
		this.level = node.getLevel()>this.level ? node.getLevel() : this.level;
	}
	
	/**
	 *     
	 * @return
	 */
	public void preOrderTraverse(TreeNode node){
		if(node==null) return;
		this.preOrderList.add((TreeNode)node.clone());
		preOrderTraverse(node.getLeftChild());
		preOrderTraverse(node.getRightChild());
	}
	
	/**
	 *     
	 * @return
	 */
	public void inOrderTraverse(TreeNode node){
		if(node==null) return;
		inOrderTraverse(node.getLeftChild());
		this.inOrderList.add((TreeNode)node.clone());
		inOrderTraverse(node.getRightChild());
	}
	
	/**
	 *     
	 * @return
	 */
	public void postOrderTraverse(TreeNode node){
		if(node==null) return;
		postOrderTraverse(node.getLeftChild());
		postOrderTraverse(node.getRightChild());
		this.postOrderList.add((TreeNode)node.clone());
	}
	
	/**
	 *     
	 * @return
	 */
	public void levelOrderTraverse(TreeNode node){
		if(node == null) return;
		if(node.getLeftChild()!=null) 
			this.levelQueue.add(node.getLeftChild());
		if(node.getRightChild()!=null) 
			this.levelQueue.add(node.getRightChild());
		this.levelOrderList.add((TreeNode)node.clone());
		if(levelQueue.size()>0)
			levelOrderTraverse(levelQueue.remove(0));
	}
}

public class BinaryTreeMain {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		TreeNode a = new TreeNode("a");
		TreeNode b = new TreeNode("b");
		TreeNode c = new TreeNode("c");
		TreeNode d = new TreeNode("d");
		TreeNode e = new TreeNode("e");
		TreeNode f = new TreeNode("f");
		TreeNode g = new TreeNode("g");
		BinaryTree tree = new BinaryTree();
		tree.insertNode(null, a, BinaryTree.LEFT);
		tree.insertNode(a, b, BinaryTree.LEFT);
		tree.insertNode(b, c, BinaryTree.LEFT);
		tree.insertNode(b, d, BinaryTree.RIGHT);
		tree.insertNode(d, e, BinaryTree.LEFT);
		tree.insertNode(d, f, BinaryTree.RIGHT);
		tree.insertNode(e, g, BinaryTree.RIGHT);
		int level = tree.getLevel();
		int number = tree.getNodeNumber();
		tree.inOrderTraverse(tree.getRoot());
		tree.preOrderTraverse(tree.getRoot());
		tree.postOrderTraverse(tree.getRoot());
		tree.levelOrderTraverse(tree.getRoot());
		List<TreeNode> pre = tree.getPreOrderList();
		List<TreeNode> in = tree.getInOrderList();
		List<TreeNode> post = tree.getPostOrderList();
		List<TreeNode> levelList = tree.getLevelOrderList();
		System.out.println("----------------");
	}
}