Java基础知识强化58：经典排序之二叉树排序（BinaryTreeSort）

1. 二叉树排序

二叉树排序的描述也是一个递归的描述，所以二叉树排序的构造自然也用递归的：

二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；

（3）左、右子树也分别为二叉排序树；

（4）没有键值相等的结点。

2. 二叉树排序代码实现：

 1 package com.himi.classisort;
 2 
 3 public class BinaryTreeSortDemo {
 4     private int value;// current value
 5     private BinaryTreeSortDemo lChild;// left child
 6     private BinaryTreeSortDemo rChild;// right child
 7 
 8     public BinaryTreeSortDemo(int value, BinaryTreeSortDemo l, BinaryTreeSortDemo r) {
 9         this.value = value;
10         this.lChild = l;
11         this.rChild = r;
12     }
13 
14     public BinaryTreeSortDemo getLChild() {
15         return lChild;
16     }
17 
18     public void setLChild(BinaryTreeSortDemo child) {
19         lChild = child;
20     }
21 
22     public BinaryTreeSortDemo getRChild() {
23         return rChild;
24     }
25 
26     public void setRChild(BinaryTreeSortDemo child) {
27         rChild = child;
28     }
29 
30     public int getValue() {
31         return value;
32     }
33 
34     public void setValue(int value) {
35         this.value = value;
36     }
37 
38     // iterater all node.
39     public static void iterater(BinaryTreeSortDemo root) {
40         // 先迭代遍历根节点的左边
41         if (root.lChild != null) {
42             iterater(root.getLChild());
43         }
44         // 再迭代遍历根节点
45         System.out.print(root.getValue() + " ");
46         
47         // 最后迭代遍历根节点的右边
48         if (root.rChild != null) {
49             iterater(root.getRChild());
50         }
51         
52     }
53 
54     /**
55      * add child to the current node to construct a tree. Time: O( nlog(n) )
56      **/
57     public void addChild(int n) {
58         if (n < value) {
59             if (lChild != null) {
60                 lChild.addChild(n);
61             } else {
62                 lChild = new BinaryTreeSortDemo(n, null, null);
63             }
64             
65         } else {
66             if (rChild != null) {
67                 rChild.addChild(n);
68             } else {
69                 rChild = new BinaryTreeSortDemo(n, null, null);
70             }
71         }
72     }
73 
74     // test case.
75     public static void main(String[] args) {
76         System.out.println();
77         int[] arr = new int[] {23, 54, 1, 65, 9, 3, 100};
78         
79         //创建一个根节点
80         BinaryTreeSortDemo root = new BinaryTreeSortDemo(arr[0], null, null);
81         
82         //将数组以排序二叉树的方式摆放
83         for (int i = 1; i < arr.length; i++) {
84             
85             root.addChild(arr[i]);
86         }
87         
88         //遍历上面形成的排序二叉树
89         BinaryTreeSortDemo.iterater(root);
90     }
91 }

运行效果：