二叉树排序
二叉树排序？你可能没听过但又很好奇。
先来了解一下二叉树
接下来我们才开始讲解二叉树排序
方法如下：
当然，如果要挂的那边有了节点，那么与那边子树的根节点比较，一直到子树的根节点为空节点，再根据情况挂点。
那么，他好用不？
最好时间复杂度：O(n)
平均时间复杂度：O(nlog2n)
最差时间复杂度：O(n²)
空间复杂度：O(n)
与快速排序的效率差不多，可以用！
源码如下：
1 class BinaryTree{
2 class Node{ //声明一个节点类
3 private Comparable data; //节点的数据类型为Comparable
4 private Node left; //保存左子树
5 private Node right; //保存右子树
6 public Node(Comparable data){ //构造函数
7 this.data = data;
8 }
9 public void addNode(Node newNode){
10 //确定是放在左子树还是右子树
11 if(newNode.data.compareTo(this.data)<0){ //新节点值小于当前节点
12 if(this.left == null){
13 this.left = newNode; //左子树为空的话，新节点设为左子树
14 }else{
15 this.left.addNode(newNode); //否则继续向下判断
16 }
17 }else{ //新节点的值大于或等于当前节点
18 if(this.right == null){
19 this.right = newNode;
20 }else{
21 this.right.addNode(newNode);
22 }
23 }
24 }
25
26 public void printNode(){ //采用中序遍历
27 if(this.left != null){ //如果不为空先输出左子树
28 this.left.printNode();
29 }
30 System.out.print(this.data+"\t"); //输出当前根节点
31 if(this.right != null){ //输出右子树
32 this.right.printNode();
33 }
34 }
35 }
36 private Node root; //表示根元素
37
38 public void add(Comparable data){ //向二叉树中插入元素
39 Node newNode = new Node(data);
40 if(root == null){ //没有根节点
41 root = newNode;
42 }else{
43 root.addNode(newNode); //判断放在左子树还是右子树
44 }
45 }
46
47 public void print(){
48 root.printNode(); //根据根节点输出
49 }
50 }
51
52 public class TestBinaryTreeSort {
53 public static void main(String args[]){
54 BinaryTree bt = new BinaryTree();
55 bt.add(3);
56 bt.add(5);
57 bt.add(4);
58 bt.add(8);
59 bt.add(7);
60 bt.add(8);
61 bt.add(1);
62 bt.print();
63 }
64 }
