Java实现二叉搜索树（BST）节点插入的两种方法

宋时安

发布时间：2026-10-16| 5人浏览过

原创

在Java开发中，二叉搜索树（BST）是常见的基础数据结构。向BST插入新值需遵循“左小右大”原则。本文以LeetCode第701题为案例，深入剖析迭代与递归两种实现方式，提供可直接运行的完整代码。

问题背景与BST核心规则

二叉搜索树（Binary Search Tree）具有特定的排序属性：对于任意节点，其左子树上所有节点的值均小于该节点的值，而其右子树上所有节点的值均大于该节点的值。这一特性使得数据的查找、插入和删除效率较高。

我们需要解决的问题通常如LeetCode第701题：给定二叉搜索树的根节点和要插入的值，将值插入二叉搜索树，并返回插入后的根节点。题目保证新值与树中原有值不同。

数据结构准备

在进行算法逻辑编写前，首先需要明确二叉树节点的Java结构定义。每个节点包含一个整型值以及指向左右子节点的引用。

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

这种结构与链表类似，但二叉树是每个节点有两个分支（左右），而链表只有一个next指针。因此，在插入时，我们需要定位到最后一个非空节点的父级，并将其left或right指针指向新创建的节点。

解法一：递归实现（推荐）

递归是最直观的实现方式。逻辑如下：

基准情况：如果当前传入的节点为空（root == null），说明找到了插入位置，直接创建一个新节点并返回。
递归移动：
- 如果当前节点值小于待插入值（root.val < val），说明新节点应位于右侧，递归调用右子树。root.right = insertIntoBST(root.right, val)
- 否则，新节点应位于左侧，递归调用左子树。root.left = insertIntoBST(root.left, val)
返回根节点：递归结束后，始终返回当前的root，以保持树结构的连接。

public TreeNode insertIntoBST(TreeNode root, int val) {
    // 1. 找到空位，创建新节点
    if (root == null) {
        return new TreeNode(val);
    }
    
    // 2. 比较大小，决定向左还是向右递归
    if (root.val < val) {
        // 值较大，去右边找位置
        root.right = insertIntoBST(root.right, val);
    } else {
        // 值较小，去左边找位置
        root.left = insertIntoBST(root.left, val);
    }
    
    // 3. 返回当前根节点，维持链路
    return root;
}

解法二：迭代实现（循环）

如果不希望使用递归栈空间，可以使用迭代法。核心思路是遍历树寻找插入点的父节点。

处理空树：如果根节点为空，直接返回新创建的节点。
寻找父节点：使用两个指针，parent用于记录上一个访问的节点，cur（或p）用于向下移动。
- 当cur不为空时，先更新parent = cur。
- 根据值的大小移动cur：若cur.val < val，则往右走（cur.right）；否则往左走（cur.left）。
- 当cur变为null时，循环结束，此时parent即为需要链接新节点的父节点。
执行插入：比较parent.val与val的大小，决定新建的TreeNode(val)是作为parent.left还是parent.right。

// 解法2：循环判断
public TreeNode insertBST2(TreeNode root, int val) {
    if (root == null) {
        return new TreeNode(val);
    }
    
    TreeNode parent = root;
    TreeNode p = root;
    
    // 循环寻找最后一个非空节点的父级
    while (p != null) {
        parent = p; // 记录上一个节点
        // 比较大小并移动指针
        p = (p.val > val) ? p.left : p.right;
    }
    
    // 此时 p 为 null，parent 为目标位置的父节点
    if (parent.val > val) {
        parent.left = new TreeNode(val); // 插在左边
    } else {
        parent.right = new TreeNode(val); // 插在右边
    }
    
    return root;
}

完整代码整合

以下是包含TreeNode定义及上述两种解法的完整类结构，可直接用于本地测试或提交至在线OJ平台。

package LeetCode; // 请根据实际包名修改

class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode() {}
      TreeNode(int val) { this.val = val; }
      TreeNode(int val, TreeNode left, TreeNode right) {
          this.val = val;
          this.left = left;
          this.right = right;
      }
}

class Solution {

    /**
     * 方法1：递归实现
     */
    public TreeNode insertIntoBST(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        if (root.val < val) {
            root.right = insertIntoBST(root.right, val);
        } else {
            root.left = insertIntoBST(root.left, val);
        }
        return root;
    }

    /**
     * 方法2：迭代实现
     */
    public TreeNode insertBST2(TreeNode root, int val) {
        if (root == null) {
            return new TreeNode(val);
        }
        
        TreeNode parent = root;
        TreeNode p = root;
        
        while (p != null) {
            parent = p;
            p = (p.val > val) ? p.left : p.right;
        }
        
        if (parent.val > val) {
            parent.left = new TreeNode(val);
        } else {
            parent.right = new TreeNode(val);
        }
        return root;
    }
}

总结

二叉搜索树的插入操作充分利用了其有序性。递归写法代码简洁，易于理解，但在树极不平衡时可能面临栈溢出风险；迭代写法虽然代码稍长，但空间复杂度稳定为O(1)。在实际面试或工程应用中，可根据具体场景选择。以上就是Java二叉搜索树节点插入算法的详细内容，更多关于Java数据结构与算法的资料请关注本站其它相关文章！