简单说下二叉树排序

之前我写过一篇二叉树的文章：下次面试若再被问到二叉树，希望你能对答如流！这篇文章详细分析了二叉树这种数据结构。

顾名思义，二叉树排序就是利用二叉搜索树的特点进行排序，上面这篇文章提到过二叉搜索树的特点是，左子节点比自己小，右子节点比自己大，那么二叉树排序的思想就是先将待排序序列逐个添加到二叉搜索树中去，再通过中序遍历二叉搜索树就可以将数据从小到大取出来。

没错，这篇文章就写到这，这可能是我目前写过最短的文章了……

public class Tree2Sort {
 private Node root;
 public Tree2Sort() {
   root = null;
 }
 public Node getRoot() {
   return root;
 }
 public void insertSort(int[] source) {
   for(int i = 0; i < source.length; i++) {
     int value = source[i];
     Node node = new Node(value);
     if(root == null) {
       root = node;
     }
     else {
       Node current = root;
       Node parent;
       boolean insertedOK = false;
       while(!insertedOK) {
         parent = current;
         if(value < current.value) {
           current = current.leftChild;
           if(current == null) {
             parent.leftChild = node;
             insertedOK = true;
           }
         }
         else {
           current = current.rightChild;
           if(current == null) {
             parent.rightChild = node;
             insertedOK = true;
           }
         }
       }
       
     }
   }
 }
 //中序遍历
 public void inOrder(Node current) {
   if(current != null) {
     inOrder(current.leftChild);
     System.out.print(current.value + " ");
     inOrder(current.rightChild);
   }
 }
}
class Node {
 public int value;
 Node leftChild;
 Node rightChild;
 public Node(int val) {
   value = val;
 }
}

算法分析： 二叉树的插入时间复杂度为 O(logN)，所以二叉树排序算法的时间复杂度为 O(NlogN)，但是二叉树排序跟归并排序一样，也需要额外的和待排序序列大小相同的存储空间。空间复杂度为 O(N)。