数据结构学习之二叉树

TreeNode.java

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;
	}
}

BinaryTree.java

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));
	}
}

BinaryTreeMain.java

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("----------------");
	}
}