二叉树

大家都知道，要对一个对象进行排序可以利用java提供的Comparable<T>接口和Arrays工具类实现。

在实现Comparable<T>接口时要实现下面的方法

public int compareTo(T t);

 此方法返回1，0和－1。返回1表示升序，－1表示降序。0表示相等。

为什么要这样定义？出于好奇，我查看了源代码，发现此方法是利用了数据结构里面的平衡二叉树的排序原理。

为了巩固以前学过的数据结构知识，我现在通过java来实现下Binary Tree.

/**
 * 二叉树
 */
public class BinaryTree<T> {
	//树的节点
	public class Node {
		//节点上的数据
		Comparable<T> data;
		//左子树
		Node lChild;
		//右子树
		Node rChild;
		
		public Node(Comparable<T> data) {
			this.data = data;
		}
		//添加一个节点
		@SuppressWarnings("unchecked")
		public void addNode(Node node) {
			//若当前节点的数据比添加的节点的数据大,则将新节点放在此节点的左子树上
			if (this.data.compareTo((T)node.data) == 1) {
				//若当前节点的左子树为空，则直接创建新节点，放在其左子树上
				if (this.lChild == null) {
					this.lChild = node;
				} else {
					//递归调用
					this.lChild.addNode(node);
				}				
			} else { //新节点的数据大于等于当前节点的数据，则将其放到当前节点的右子树上
				if (this.rChild == null) {
					this.rChild = node;
				} else {
					this.rChild.addNode(node);
				}
			}
		}
		//中序遍历打印出当前节点为根的所有子节点
		public void printNode() {
			if (this.lChild != null) { //先遍历左子树
				this.lChild.printNode();
			}
			System.out.print(this.data + " "); //打印根节点
			if (this.rChild != null) { //再遍历右子树
				this.rChild.printNode();
			}
		}
	}
	//根节点
	private Node root;
	
	//添加新节点
	public void addNode(Node node) {
		if (root == null) {
			root = node;
		} else {
			root.addNode(node);
		}
	}
	//打印树
	public void printTree() {
		root.printNode();
	}
	
	//测试类
	public static class Test {
		public static void main(String[] args) {
			BinaryTree<Integer> tree = new BinaryTree<Integer>();
			tree.addNode(tree.new Node(1));
			tree.addNode(tree.new Node(10));
			tree.addNode(tree.new Node(13));
			tree.addNode(tree.new Node(111));
			tree.addNode(tree.new Node(32));
			tree.addNode(tree.new Node(19));
			tree.addNode(tree.new Node(1));
			tree.printTree();
		}
	}
}

打印出：

1 1 10 13 19 32 111 

 测试成功！ 

总结：

返回1表示当前节点大于新添加的节点，因此要把新添加的节点放在当前节点的左子树上，反之加到当前节点的右子树上。

然后利用二叉树的中序遍历（先左子树，再根，再右子树）得到排序结果。这也就说明了comparaTo方法返回的-1,0和1的原因。

 

评论

3 楼 yangguo 2010-07-28  

1.确实是二叉树。不是平衡。
2.跟comparaTo返回什么没有什么关系。

2 楼 五月天 2010-05-11  

DAOException 写道

你这只是二叉树吧，不是平衡二叉树

这是平衡二叉树啊~别悠闲我:wink:

1 楼 DAOException 2010-05-07  

你这只是二叉树吧，不是平衡二叉树