|
代码实例：
package tree;
?
/**
* 基于二叉树结构实现排序的排序器
*/
?
public class BinaryTreeSort<E extends Integer> {
?
? ?/**
? ? * 定义结点内部类
? ? */
? ?class Node<E extends Integer>{
? ? ? ?private E item;
? ? ? ?private Node left;
? ? ? ?private Node right;
? ? ? ?Node(E item){
? ? ? ? ? ?this.item = item;
? ? ? }
?
? ? ? ?/**
? ? ? ? * 添加结点
? ? ? ? */
? ? ? ?public void addNode(Node node) {
? ? ? ? ? ?//完成新结点元素与当前结点元素的比较
? ? ? ? ? ?//如果新结点的元素小于当前结点的元素，则把新结点添加到当前结点的左子树
? ? ? ? ? ?if (node.item.intValue() <= this.item.intValue()) {
? ? ? ? ? ? ? ?if (this.left == null) { ? ? //当前结点没有左子树
? ? ? ? ? ? ? ? ? ?this.left = node;
? ? ? ? ? ? ? } else { ? ? ?//当前结点有左子树，那直接扔给左子树递归
? ? ? ? ? ? ? ? ? ?this.left.addNode(node);
? ? ? ? ? ? ? }
? ? ? ? ? }else{
? ? ? ? ? ? ? ?//如果新结点的元素大于当前结点的元素，则把新结点添加到当前结点的右子树
? ? ? ? ? ? ? ?if(this.right == null){ ? ? //右子树为空
? ? ? ? ? ? ? ? ? ?this.right = node;
? ? ? ? ? ? ? } else { ? ? //当前结点有右子树直接扔给右子树递归
? ? ? ? ? ? ? ? ? ?this.right.addNode(node);
? ? ? ? ? ? ? }
? ? ? ? ? }
? ? ? }
?
? ? ? ?/**
? ? ? ? * 使用中序遍历二叉树
? ? ? ? */
? ? ? ?public void inorderTraversal(){
? ? ? ? ? ?//找到二叉树最左侧的结点
? ? ? ? ? ?if(this.left != null) this.left.inorderTraversal();
? ? ? ? ? ?System.out.println(this.item);
? ? ? ? ? ?if (this.right != null) this.right.inorderTraversal();
? ? ? }
? }
?
? ?private Node root; ?//存放根节点
?
? ?/**
? ? * 添加元素到排序器中的方法
? ? * @param element
? ? */
? ?public void add(E element){
? ? ? ?//实例化结点对象
? ? ? ?Node<E> node = new Node<>(element);
? ? ? ?//将将结点添加到二叉树
? ? ? ?if (this.root == null) ?//判断是否为空树
? ? ? ? ? ?root = node;
? ? ? ?else
? ? ? ? ? ?this.root.addNode(node);
?
? }
?
? ?/**
? ? * 进行排序的方法
? ? */
? ?public void sort(){
? ? ? ?if ( this.root == null) return;
? ? ? ?else
? ? ? ? ? ?this.root.inorderTraversal();
? }
?
?
? ?public static void main(String[] args) {
? ? ? ?BinaryTreeSort<Integer> binaryTreeSort = new BinaryTreeSort<>();
? ? ? ?binaryTreeSort.add(20);
? ? ? ?binaryTreeSort.add(3);
? ? ? ?binaryTreeSort.add(9);
? ? ? ?binaryTreeSort.add(7);
? ? ? ?binaryTreeSort.add(4);
? ? ? ?binaryTreeSort.sort();
? }
?
}
运行结果
3 4 7 9 20
|