简单说下二叉树排序

Original 倪升武程序员私房菜 2018-12-04

阅读本文大概需要5分钟

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

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

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

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;
  }
}