什么是二叉排序树
二叉排序树又称二叉查找树，是一种特殊的二叉树，它的每个节点都包含一个数据域，且具有以下特点：
若左子树不为空，则左子树上所有节点的值均小于它的根节点的值
若右子树不为空，则右子树上所有节点的值均大于它的根节点的值
左、右子树也分别为二叉排序树
这种结构使得二叉排序树具有高效的查找、插入和删除操作特性。
二叉排序树的节点结构
二叉排序树由节点组成，每个节点包含三个部分：数据域、左子树指针和右子树指针。在 Java 中，我们可以用类来定义节点：
public class TreeNode {
public TreeNode lChild; // 左子树指针
public TreeNode rChild; // 右子树指针
public Integer data; // 数据域
// 构造方法，初始化数据
public TreeNode(Integer data){
this.data = data;
}
}
二叉排序树的构建
构建思路
构建二叉排序树的核心是插入操作，插入过程遵循以下规则：
若树为空，则新节点作为根节点
若树不为空，则从根节点开始比较：
若新节点值小于当前节点值，则向左子树移动
若新节点值大于当前节点值，则向右子树移动
重复上述过程，直到找到合适的空位置插入新节点
public class BinaryTree {
// 根节点指针
TreeNode root;
// 插入节点方法
public void create(Integer value){
// 1. 创建新节点
TreeNode newNode = new TreeNode(value);
// 若根节点为空，直接作为根节点
if(root == null){
root = newNode;
return;
}
// 定义当前节点指针，从根节点开始
TreeNode curNode = root;
// 循环查找插入位置
while(true){
// 新节点值大于当前节点值，向右子树查找
if(curNode.data < newNode.data){
if(curNode.rChild == null){
curNode.rChild = newNode;
return;
}
curNode = curNode.rChild;
}else{
// 新节点值小于当前节点值，向左子树查找
if(curNode.lChild == null){
curNode.lChild = newNode;
return;
}
curNode = curNode.lChild;
}
}
}
// 后续代码省略...
}
二叉排序树的遍历
二叉排序树的遍历分为深度优先遍历和广度优先遍历两大类。
深度优先遍历（递归实现）
深度优先遍历包括先序遍历、中序遍历和后序遍历，它们的区别在于访问根节点的时机不同。
先序遍历（根左右）
// 先序遍历：根 -> 左 -> 右
void beforeOrder(TreeNode root){
if(root == null){
return;
}
System.out.println(root.data); // 访问根节点
beforeOrder(root.lChild); // 遍历左子树
beforeOrder(root.rChild); // 遍历右子树
}
中序遍历（左根右）
// 中序遍历：左 -> 根 -> 右
void inOrder(TreeNode root){
if(root == null){
return;
}
inOrder(root.lChild); // 遍历左子树
System.out.println(root.data); // 访问根节点
inOrder(root.rChild); // 遍历右子树
}
注意：二叉排序树的中序遍历结果是一个有序序列，这是其重要特性
后序遍历（左右根）
// 后序遍历：左 -> 右 -> 根
void afterOrder(TreeNode root){
if(root == null){
return;
}
afterOrder(root.lChild); // 遍历左子树
afterOrder(root.rChild); // 遍历右子树
System.out.println(root.data); // 访问根节点
}
广度优先遍历（层次遍历）
层次遍历按照树的层次依次访问每个节点，需要借助队列来实现：
// 层次遍历
void levelOrder(TreeNode root){
LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while(!queue.isEmpty()){
root = queue.pop(); // 出队
System.out.println(root.data); // 访问节点
// 左子树不为空则入队
if(root.lChild != null){
queue.add(root.lChild);
}
// 右子树不为空则入队
if(root.rChild != null){
queue.add(root.rChild);
}
}
}
测试示例
我们可以通过以下代码测试二叉排序树的功能：
public class Test {
public static void main(String[] args) {
BinaryTree tree = new BinaryTree();
// 插入节点
tree.create(5);
tree.create(3);
tree.create(7);
tree.create(0);
tree.create(4);
tree.create(6);
tree.create(9);
System.out.println("先序遍历：");
tree.beforeOrder(tree.root);
)
