Java中的数据结构（3）----强大的二叉树

简单的排序二叉树

package com.wz.util.tree;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * 排序二叉树
 * 
 * @author NumbCoder
 * 
 */
// 节点
class BinaryNode {
	private int data;
	BinaryNode lChild;
	BinaryNode rChild;

	BinaryNode(int t) {
		setData(t);
		lChild = null;
		rChild = null;
	}

	// 是否为叶子节点
	public boolean isLeaf() {
		if (lChild == null && rChild == null)
			return true;
		else
			return false;
	}

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

	public int getData() {
		return data;
	}
}

// 树
public class BinaryTree {
	private BinaryNode root;

	BinaryTree(BinaryNode root) {
		this.root = root;
		root.lChild = null;
		root.rChild = null;
	}

	// 向二叉树中插入一个节点
	public void insert(BinaryNode n) {
		// 树是空的
		if (root == null)
			root = n;
		else {
			BinaryNode current = root;
			BinaryNode parentNode;
			boolean flag = true;
			while (flag) {
				parentNode = current;
				if (n.getData() > current.getData()) {
					// 要插入的节点为右孩子节点
					current = current.rChild;
					if (current == null) {
						parentNode.rChild = n;
						flag = false;
					}
				} else if (n.getData() < current.getData()) {
					current = current.lChild;
					// 要插入的节点为左孩子节点
					if (current == null) {
						parentNode.lChild = n;
						flag = false;
					}
				}
			}
		}
	}

	// 传入一个裝有节点的ArrayList便可自动生成一棵排序二叉树
	public void creatBinaryTree(BinaryNode root, ArrayList<BinaryNode> aList) {
		Iterator<BinaryNode> it = aList.iterator();
		while (it.hasNext()) {
			insert(it.next());
		}
	}

	// 先序遍历
	public void preOrder(BinaryNode t) {
		if (t != null) {
			System.out.println(t.getData());
			preOrder(t.lChild);
			preOrder(t.rChild);
		}
	}

	// 中序遍历
	public void inOrder(BinaryNode t) {
		if (t != null) {
			inOrder(t.lChild);
			System.out.println(t.getData());
			inOrder(t.rChild);
		}
	}

	// 后序遍历
	public void postOrder(BinaryNode t) {
		if (t != null) {
			postOrder(t.lChild);
			postOrder(t.rChild);
			System.out.println(t.getData());
		}
	}

}

 泛型的排序二叉树（因为是排序的，所以节点必须具有可比性，但具体的比较规则自己定）

package com.wz.util;

import java.util.ArrayList;
import java.util.Iterator;

/**
 * 带泛型的排序二叉树
 * 
 * @author NumbCoder
 * 
 */

 
  class BinaryNode<T> implements Comparable<T>  {
	private T data;
	BinaryNode<T> lChild;
	BinaryNode<T> rChild;

	BinaryNode(T t) {
		setData(t);
		lChild = null;
		rChild = null;
	}

	/**
	 * 根据T的类型自定义比较方法小于、等于或大于n分别返回负-1、0或1 
	 * 必须实现具体compareTo方法
	 */
	@Override
	public int compareTo(T t) {
		
			return 0;
	}
	public void setData(T data) {
		this.data = data;
	}

	public T getData() {
		return data;
	}
//是否为叶子节点
	public boolean isLeaf() {
		if (lChild == null && rChild == null)
			return true;
		else
			return false;
	}

	

	
}
//树
public class BinaryTree<T> {
	private BinaryNode<T> root;

	BinaryTree(BinaryNode<T> root) {
		this.root = root;
		root.lChild = null;
		root.rChild = null;
	}

	// 向二叉树中插入一个节点
	public void insert(BinaryNode<T> n) {
		// 树是空的
		if (root == null)
			root = n;
		else {
			BinaryNode<T> current = root;
			BinaryNode<T> parentNode;
			boolean flag = true;
			while (flag) {
				parentNode = current;
				if (n.compareTo(current.getData()) == 1) {
					// 要插入的节点为右孩子节点
					current = current.rChild;
					if (current == null) {
						parentNode.rChild = n;
						flag = false;
					}
				} else if( n.compareTo(current.getData()) == -1){
					current = current.lChild;
					// 要插入的节点为左孩子节点
					if (current == null) {
						parentNode.lChild = n;
						flag = false;
					}
				}
			}
		}
	}

	// 生成一棵排序二叉树
	public void creatBinaryTree(BinaryNode<T> root,
			ArrayList<BinaryNode<T>> aList) {
		Iterator<BinaryNode<T>> it = aList.iterator();
		while (it.hasNext()) {
			insert(it.next());
		}
	}

	// 先序遍历
	private void preOrder(BinaryNode<T> t, ArrayList<T> list) {
		if (t != null) {
			list.add(t.getData());
			preOrder(t.lChild, list);
			preOrder(t.rChild, list);
		}
	}

	public Iterator<T> itPreOrder() {
		ArrayList<T> list = new ArrayList<T>();
		preOrder(root, list);
		return list.iterator();
	}

	// 中序遍历
	private void inOrder(BinaryNode<T> t, ArrayList<T> list) {
		if (t != null) {
			inOrder(t.lChild, list);
			list.add(t.getData());
			inOrder(t.rChild, list);
		}
	}

	public Iterator<T> itInOrder() {
		ArrayList<T> list = new ArrayList<T>();
		inOrder(root, list);
		return list.iterator();
	}

	// 后序遍历
	private void postOrder(BinaryNode<T> t, ArrayList<T> list) {
		if (t != null) {
			postOrder(t.lChild, list);
			postOrder(t.rChild, list);
			list.add(t.getData());
		}
	}

	public Iterator<T> itPostOrder() {
		ArrayList<T> list = new ArrayList<T>();
		postOrder(root, list);
		return list.iterator();
	}
}