1. 二叉树排序
二叉树排序的描述也是一个递归的描述， 所以二叉树排序的构造自然也用递归的：
二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。
2. 二叉树排序代码实现：
package com.himi.classisort;
public class BinaryTreeSortDemo {
private int value;// current value
private BinaryTreeSortDemo lChild;// left child
private BinaryTreeSortDemo rChild;// right child
public BinaryTreeSortDemo(int value, BinaryTreeSortDemo l, BinaryTreeSortDemo r) {
this.value = value;
this.lChild = l;
this.rChild = r;
}
public BinaryTreeSortDemo getLChild() {
return lChild;
}
public void setLChild(BinaryTreeSortDemo child) {
lChild = child;
}
public BinaryTreeSortDemo getRChild() {
return rChild;
}
public void setRChild(BinaryTreeSortDemo child) {
rChild = child;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
// iterater all node.
public static void iterater(BinaryTreeSortDemo root) {
// 先迭代遍历根节点的左边
if (root.lChild != null) {
iterater(root.getLChild());
}
// 再迭代遍历根节点
System.out.print(root.getValue() + " ");
// 最后迭代遍历根节点的右边
if (root.rChild != null) {
iterater(root.getRChild());
}
}
/**
* add child to the current node to construct a tree. Time: O( nlog(n) )
**/
public void addChild(int n) {
if (n < value) {
if (lChild != null) {
lChild.addChild(n);
} else {
lChild = new BinaryTreeSortDemo(n, null, null);
}
} else {
if (rChild != null) {
rChild.addChild(n);
} else {
rChild = new BinaryTreeSortDemo(n, null, null);
}
}
}
// test case.
public static void main(String[] args) {
System.out.println();
int[] arr = new int[] {23, 54, 1, 65, 9, 3, 100};
//创建一个根节点
BinaryTreeSortDemo root = new BinaryTreeSortDemo(arr[0], null, null);
//将数组以排序二叉树的方式摆放
for (int i = 1; i < arr.length; i++) {
root.addChild(arr[i]);
}
//遍历上面形成的排序二叉树
BinaryTreeSortDemo.iterater(root);
}
}
运行效果：