本教程介绍了如何用Java编写Tree排序程序。树排序使用二进制搜索树(BST)对元素进行排序。

什么是二叉搜索树

二进制搜索树(BST)是一种特殊的二进制树，其中节点的左子节点的值小于其父节点的值，而节点的右子节点的值大于或者等于其父节点的值。

下图显示了带有节点的二叉搜索树。如我们所见，左子树的节点值小于根节点，右子树的节点值大于根节点。

树排序算法

树排序工作如下

• 使用输入数组中的元素创建二元搜索树。
• 对BST进行有序遍历以按排序顺序获取元素。通过先访问左子树节点，然后依次访问根节点和右子树节点，可以完成有序遍历。

树排序Java程序

要表示一个BST节点，需要一个Node类，该类具有两个引用。这些参考分别指左孩子和右孩子。此类Node用于创建BST的节点。

class Node{
  int value;
  Node left;
  Node right;
  Node(int value){
    this.value = value;
    left = null;
    right = null;        
  }
}

树排序

// Class for tree nodes
class Node{
  int value;
  Node left;
  Node right;
  Node(int value){
    this.value = value;
    left = null;
    right = null;        
  }
}
// Class for Binary Search Tree
class BST{
  Node node;
  BST(int value){
    node = new Node(value);
  }
  public Node insert(Node node, int value){
    if(node == null){
      return new Node(value);
    }
    // Move to left for value less than parent node
    if(value < node.value){
      node.left = insert(node.left, value);
    }
    // Move to right for value greater than parent node
    else if(value > node.value){
      node.right = insert(node.right, value);
    }
    return node;
  }
    
  // For traversing in order
  public void inOrder(Node node){
    if(node != null){
      // recursively traverse left subtree
      inOrder(node.left);
      System.out.print(node.value + " ");
      // recursively traverse right subtree
      inOrder(node.right);
    }
  }
}

public class TreeSort {
  public static void main(String[] args) {
    int[] arr = {65, 68, 82, 42, 10, 75, 25, 47, 32, 72};
    System.out.println("Original array- " + Arrays.toString(arr));
    // start creating tree with element at index 0 as root node
    BST bst = new BST(arr[0]);
    for(int num : arr){
      bst.insert(bst.node, num);
    }
    System.out.print("Sorted Array after Tree sort- ");
    bst.inOrder(bst.node);
    System.out.println();
  }
}

输出：

Original array- [65, 68, 82, 42, 10, 75, 25, 47, 32, 72]
Sorted Array after Tree sort- 10 25 32 42 47 65 68 72 75 82

树排序时间和空间复杂度

树排序的平均案例时间复杂度为O(n logn)。

如果树是不平衡的二叉树，则在最坏的情况下添加一项需要O(n)时间。这意味着树排序的最坏情况下的时间复杂度为O(n2)。

由于将为n个元素创建n个节点，因此辅助空间需求为n。因此，树排序的空间复杂度为O(n)。