public class BinaryTree< T extends Comparable< T>> {//二叉树
LinkedList< T> values; //一个链表
private Node root; // 根节点
public void add(T value) {//在树中添加数据
if(root == null) {
root = new Node(value);
} else {
add(value, root);
}
}
// 在树中递归插入一个对象
private void add(T value, Node node) {
int comparison = node.obj.compareTo(value);
if(comparison == 0) {
++node.count;
return;
}
if(comparison > 0) {
if(node.left == null) {
node.left = new Node(value);
} else {
add(value, node.left);
}
} else {
if(node.right == null) {
node.right = new Node(value);
} else {
add(value, node.right);
}
}
}
public LinkedList< T> sort() {//排序
values = new LinkedList< T>();
treeSort(root);
return values;
}
</td>
</tr>
</table>
private void treeSort(Node node) {
if(node != null) {
treeSort(node.left);
// List the duplicate objects for the current node
for(int i = 0 ; i< node.count ; i++) {
values.addItem(node.obj);
}
treeSort(node.right); // Now process the right child
}
}
// 定义节点类
private class Node {
Node(T value) {
obj = value;
count = 1;
}
T obj; // 存储在节点中的对象
int count; // 相同节点的数目
Node left; // 左孩子节点
Node right; // 右孩子点
}
}
二、泛型链表
import java.util.Iterator;
import java.util.NoSuchElementException;
public class LinkedList< T> implements Iterable< T> {//泛型链表
private ListItem start = null; //头节点
private ListItem end = null; //未节点
private ListItem current = null; //当前节点
public LinkedList() {}//构造函数
public LinkedList(T item) {//构造函数
if(item != null) {
current=end=start=new ListItem(item);
}
}
public LinkedList(T[] items) {//构造函数
if(items != null) {
for(T item : items) {
addItem(item);
}
current = start;
}
}
public void addItem(T item) {//往链表中添加节点
ListItem newEnd = new ListItem(item);
if(start == null) {
start = end = newEnd;
} else {
end.next = newEnd;
end = newEnd;
}
}
public T getFirst() {//获取链表中第一个节点的数据
current = start;
return start == null ? null : start.item;
}
public T getNext() { // 获取下一个节点中的数据
if(current != null) {
current = current.next;
}
return current == null ? null : current.item;
}
public Iterator< T> iterator() {//返回链表的一个Iterator对象
return new ListIterator();
}
private class ListIterator implements Iterator< T> {
public ListIterator() {//构造函数
nextElement = start;
}
public boolean hasNext() {//链表中是否还有节点
return nextElement != null;
}
public T next() {//获取链表中的下一个节点
if(nextElement == null) {
throw new java.util.NoSuchElementException();
}
T element = nextElement.item;
nextElement = nextElement.next;
return element;
}
public void remove() {
throw new IllegalStateException();
}
ListItem nextElement; // The next element from the iterator
}
private class ListItem {//节点类
public ListItem(T item) {
this.item = item;
next = null;
}
public String toString() {
return "ListItem " + item ;
}
ListItem next; //下一节点
T item; //节点中的数据
}
}
三、测试
public class TryBinaryTree {
public static void main(String[] args) {
//创建存储到树中的整型数组
int[] numbers = new int[30];
for(int i = 0 ; i< numbers.length ; i++) {
numbers[i] = (int)(1000.0*Math.random()); // 0到999的随机数
}
int count = 0;
System.out.println("Original values are:");
for(int number : numbers) {
System.out.printf("%6d", number);
if(++count%6 == 0) {
System.out.println();
}
}
// 创建树并添加数据
BinaryTree tree = new BinaryTree();
for(int number:numbers) {
tree.add(number);
}
// 获取并输出树中的数据
LinkedList values = tree.sort();
count = 0;
System.out.println("\nSorted values are:");
for(Integer value : values) {
System.out.printf("%6d", value);
if(++count%6 == 0) {
System.out.println();
}
}
//创建存储到树中的字符串数组
String[] words = {"vacillate", "procrastinate", "arboreal", "syzygy", "xenocracy",
"zygote", "mephitic", "soporific", "grisly", "gristly" };
System.out.println("\nOriginal word sequence:");
for(String word : words) {
System.out.printf("%-15s", word);
if(++count%5 == 0) {
System.out.println();
}
}
BinaryTree cache = new BinaryTree();
for(String word : words) {
cache.add(word);
}
//排序
LinkedList sortedWords = cache.sort();
System.out.println("\nSorted word sequence:");
count = 0;
for(String word : sortedWords) {
System.out.printf("%-15s", word);
if(++count%5 == 0) {
System.out.println();
}
}
}
}
运行结果：
C:\Test>java TryBinaryTree
Original values are:
223 874 886 890 177 265
173 906 561 771 470 900
838 999 280 637 697 231
234 735 88 729 449 167
248 425 758 383 543 835
Sorted values are:
88 167 173 177 223 231
234 248 265 280 383 425
449 470 543 561 637 697
729 735 758 771 835 838
874 886 890 900 906 999
Original word sequence:
vacillate procrastinate arboreal syzygy xenocracy
zygote mephitic soporific grisly gristly
Sorted word sequence:
arboreal grisly gristly mephitic procrastinate
soporific syzygy vacillate xenocracy zygote
C:\Test>
</td> </tr> <tr>
↑返回目录
前一篇: composite模式写的二叉树的例子
后一篇: Jshrink的破解过程