二叉搜索树详解：原理、实现与 TreeMap 应用

二叉搜索树简介

二叉搜索树（Binary Search Tree, BST），又称二叉排序树，是一种特殊的二叉树结构。在存储的数据值上含有一定顺序：

• 根节点左子树的所有节点值小于当前根节点值。
• 根节点右子树的所有节点值大于当前根节点值。
• 左右子树也分别为二叉搜索树。

通过中序遍历，可以得到一组升序数据。规定二叉搜索树中通常不包含相同的值，否则节点位置可能不确定。

二叉搜索树的实现

主要围绕查、增、删三个基本操作进行实现。

1. 查找

public TreeNode search(int key) {
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val < key) {
            cur = cur.right;
        } else if (cur.val > key) {
            cur = cur.left;
        } else {
            return cur;
        }
    }
    return null;
}

查找流程：从根节点开始遍历，若当前节点值大于目标值则向左走，小于则向右走，直到找到目标节点或遍历结束返回 null。

2. 插入

public void insert(int val) {
    TreeNode node = new TreeNode(val);
    if (root == null) {
        root = node;
        return;
    }
    TreeNode cur = root;
    TreeNode parent = null;
    while (cur != null) {
         (cur.val < val) {
            parent = cur;
            cur = cur.right;
        }   (cur.val > val) {
            parent = cur;
            cur = cur.left;
        }  {
            ; 
        }
    }
     (parent.val > val) {
        parent.left = node;
    }  {
        parent.right = node;
    }
}