二叉查找树的插入

一 点睛

因为二叉查找树的中序遍历存在有序性，所以首先药查找待插入关键字的插入位置，当查找不成功时，在将待插入的关键字作文新的叶子节点称为最后一个查找节点的左孩子或右孩子。

二 算法步骤

1 若二叉查找树为空，则创建一个新的节点 s，将待插入关键字放入新节点数据 域，将 s 节点作为根节点，左右子树均为空。

2 若二叉查找树非空，则将待查找关键字 x 与根节点关键字 T.data 进行比较。

若 x < T.data，则将 x 插入左子树中。

若 x > T.data，则将 x 插入右子树中。

三 图解

1 原始的二叉查找树如下，向其中插入关键字30。

2 在 25 的右子树中查找

3 在69 的左子树中查找

4 在 32的左子树中查找

5 32 的左子树为空，将 30 作为新的叶子节点插入 32 的左子树

四 代码实现

// 二叉排序树的插入
static public TreeNode Insert(TreeNode root, int val) {
    if (root == null) {
        // 树为空树的情况
        return new TreeNode(val);
    }
    // 一个临时节点指向根节点，用于返回值
    TreeNode tmp = root;
    TreeNode pre = root;


    while (root != null && root.val != val) {
        // 保存父节点
        pre = root;
        if (val > root.val) {
            root = root.right;
        } else {
            root = root.left;
        }
    }
    // 通过父节点添加
    if (val > pre.val) {
        pre.right = new TreeNode(val);
    } else {
        pre.left = new TreeNode(val);
    }
    return tmp;
}