什么是二叉排序树？
二叉排序树（binary search tree，bst）是一种特殊的二叉树，其中每个节点具有一个键值，并且满足一下两个要求：
对于任何节点x,其左子树上所有节点的关键字值小于x的关键字值。
对于任何节点x,其有子树上所有节点的关键字值大于x的关键字值。
由于以上这两个性质，因此二叉排序树也被称为有序二叉树。在执行查找，**，删除等操作时，二叉排序树都可以保持平衡，使得时间复杂度变为o(log n)级别，极大的提高了操作效率。
二叉排序树原理
- 二叉排序树中每个结点最多有两个子树，且左子树的所有关键字（节点值）小于当前结点的关键字，右子树的所有关键字大于当前结点的关键字。
- 左右子树也都是二叉排序树。
- 当某个结点被查找时，比较待查找关键字与当前结点的关键字大小，若相等，则说明查找成功；否则根据大小关系向左或向右子树递归查找，直到找到对应的结点或者确认结点不存在。
- 当一个新的结点时，从根结点开始将待结点与当前结点进行比较，根据大小关系向左或向右递归到叶子结点停止。然后把新结点**到该叶子结点的左或右子树上。
- 当删除一个结点时，按照查找的方式找到需要删除的结点，如果该结点没有子结点，则直接删除即可；如果只有左子树或右子树，则将左子树或右子树直接替换到该结点位置；如果既有左子树又有右子树，则找到该结点的前驱或后继（中序遍历时大于当前结点的最小节点或者小于当前结点的最大节点），然后用其值来替换需要删除的结点的值，并删除前驱或后继。
使用Java实现二叉树排序的示例代码：
// 节点类
class Node {
int value;
Node left, right;
public Node(int item) {
value = item;
left = right = null;
}
}
public class BinaryTree {
Node root;
public BinaryTree() {
root = null;
}
// 将给定节点的值插入到二叉树中
private Node insertNode(Node root, int value) {
if (root == null) {
root = new Node(value);
return root;
}
if (value < root.value) {
root.left = insertNode(root.left, value);
} else if (value > root.value) {
root.right = insertNode(root.right, value);
}
return root;
}
// 中序遍历，将节点的值按升序返回。
private void traverseInOrder(Node root, List<Integer> values) {
if (root != null) {
traverseInOrder(root.left, values);
values.add(root.value);
traverseInOrder(root.right, values);
}
}
// 对外的排序方法，接收一个整数数组并返回升序排列后的结果。
public List<Integer> sort(int[] arr) {
for (int i : arr) {
root = insertNode(root, i);
}
List<Integer> sortedList = new ArrayList<>();
traverseInOrder(root, sortedList);
return sortedList;
}
// 测试代码
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
int[] arr = {
5, 3, 7, 1, 9};
List<Integer> sortedList = tree.sort(arr);
System.out.println(sortedList); // Output: [1, 3, 5, 7, 9]
}
}
该示例中，我们使用节点类Node表示二叉树中的每个节点。二叉树类BinaryTree包含插入节点、中序遍历和排序三个方法
C 语言实现二叉搜索树排序（Binary Search Tree Sorting）的示例代码：
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构体
struct Node {
int data; // 数据
struct Node* left; // 左子节点指针
struct Node* right; // 右子节点指针
};
// 创建新节点
struct Node* newNode(int data) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
// 插入节点
struct Node* insert(struct Node* node, int data) {
if(node == NULL)
return newNode(data);
if(data < node->data)
node->left = insert(node->left, data);
else if(data > node->data)
node->right = insert(node->right, data);
return node;
}
// 遍历节点并按序排列输出结果
void inorderTraversal(struct Node* node) {
if(node != NULL) {
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
}
// 测试示例
int main() {
int arr[] = {
7, 5, 1, 8, 3, 6, 0, 9, 4, 2};
int n = sizeof(arr)/sizeof(arr[0]);
struct Node* root = NULL;
for(int i=0; i<n; i++)
root = insert(root, arr[i]);
inorderTraversal(root);
return 0;
}
以上是一个简单的二叉搜索树排序的实现，可以根据需要进行修改和优化。
