排序二叉树的描述也是一个递归的描述， 所以排序二叉树的构造自然也用递归的：
排序二叉树的3个特征：
1：当前node的所有左孩子的值都小于当前node的值；
2：当前node的所有右孩子的值都大于当前node的值；
3：孩子节点也满足以上两点
1. package test.sort;
2.
3. public class BinaryNode {
4. /**
5. * author: sunxing007,
6. * 转载请注明来自http://blog.csdn.net/sunxing007
7. **/
8. private int value;//current value
9. private BinaryNode lChild;//left child
10. private BinaryNode rChild;//right child
11.
12. public BinaryNode(int value, BinaryNode l, BinaryNode r){
13. this.value = value;
14. this.lChild = l;
15. this.rChild = r;
16. }
17.
18. public BinaryNode getLChild() {
19. return lChild;
20. }
21. public void setLChild(BinaryNode child) {
22. lChild = child;
23. }
24. public BinaryNode getRChild() {
25. return rChild;
26. }
27. public void setRChild(BinaryNode child) {
28. rChild = child;
29. }
30. public int getValue() {
31. return value;
32. }
33. public void setValue(int value) {
34. this.value = value;
35. }
36.
37. //iterate all node.
38. public static void iterate(BinaryNode root){
39. if(root.lChild!=null){
40. iterate(root.getLChild());
41. }
42. System.out.print(root.getValue() + " ");
43. if(root.rChild!=null){
44. iterate(root.getRChild());
45. }
46. }
47.
48. /**
49. * add child to the current node to construct a tree.
50. * Time: O( nlog(n) )
51. * **/
52. public void addChild(int n){
53. if(n<value){
54. if(lChild!=null){
55. lChild.addChild(n);
56. }
57. else{
58. lChild = new BinaryNode(n, null, null);
59. }
60. }
61. else{
62. if(rChild!=null){
63. rChild.addChild(n);
64. }
65. else{
66. rChild = new BinaryNode(n, null, null);
67. }
68. }
69. }
70.
71. //test case.
72. public static void main(String[] args){
73. System.out.println();
74. int[] arr = new int[]{23,54,1,65,9,3,100};
75. BinaryNode root = new BinaryNode(arr[0], null, null);
76. for(int i=1; i<arr.length; i++){
77. root.addChild(arr[i]);
78. }
79. BinaryNode.iterate(root);
80. }
81. }