二叉搜索树insert函数无法添加节点问题排查求助

核心问题分析 #

你的二叉搜索树insert函数存在多个关键错误，同时根节点引用同步也有问题：

1. 迭代版insert的致命错误 #

• 错误的比较逻辑：代码中value < current是将数值与节点对象直接比较，而不是节点存储的data值，应该改为value < current.data。
• 未挂载新节点到树结构：循环结束后current = Node(value)只是创建了节点，但没有将其挂载到父节点的left或right属性上——循环过程中丢失了父节点的引用，新节点完全游离于树外。
• 未声明局部变量：current = root没有用let/const声明，会导致current成为全局变量，引发不可预期的副作用。

2. 递归版insert的错误 #

• 同样的比较逻辑错误：value < current应改为value < current.data，否则是在比较数值与对象，逻辑完全错误。
• 根节点引用不同步：Tree函数返回的{root, ...}中的root属性是初始值的副本（空树时为null），而insert修改的是Tree内部的root变量。这导致你通过d.root访问的是过时的初始值，但prettyPrint用的是内部实时的root变量，所以出现console.log(d.root)为null但打印显示根节点的矛盾现象。

3. 额外的排序逻辑问题 #

原mergeSort函数中merge(mergeSort(rightArr), mergeSort(leftArr))的参数顺序颠倒，会导致排序结果反向，需修正为merge(mergeSort(leftArr), mergeSort(rightArr))。

修复后的完整代码 #

方案1：迭代版insert（推荐） #

const Node = (data, left = null, right = null) => {
    return { data, left, right };
};

const Tree = array => {
    const remDupsAndSort = array => {
        const mergeSort = array => {
            if (array.length <= 1) return array;
            let leftArr = array.slice(0, array.length / 2);
            let rightArr = array.slice(array.length / 2);
            // 修正排序参数顺序
            return merge(mergeSort(leftArr), mergeSort(rightArr));
        };
        
        const merge = (leftArr, rightArr) => {
            let sorted = [];
            while (leftArr.length && rightArr.length) {
                if (leftArr[0] < rightArr[0]) {
                    sorted.push(leftArr.shift());
                } else {
                    sorted.push(rightArr.shift());
                }
            }
            return [...sorted, ...leftArr, ...rightArr];
        };
        return mergeSort([...new Set(array)]);
    };

    array = remDupsAndSort(array);

    const buildTree = (array, start, end) => {
        if (start > end) return null;
        let mid = Math.floor((start + end) / 2);
        let node = Node(array[mid]);
        node.left = buildTree(array, start, mid - 1);
        node.right = buildTree(array, mid + 1, end);
        return node;
    };
    
    // 用对象存储根节点，保证外部访问的是实时引用
    const state = {
        root: buildTree(array, 0, array.length - 1)
    };
    
    const insert = value => {
        if (!state.root) {
            state.root = Node(value);
            return state.root;
        }
        let current = state.root;
        let parent = null;
        // 遍历找到父节点
        while (current) {
            parent = current;
            if (value < current.data) {
                current = current.left;
            } else if (value > current.data) {
                current = current.right;
            } else {
                // 重复值直接返回，不插入
                return state.root;
            }
        }
        // 将新节点挂载到父节点的对应位置
        if (value < parent.data) {
            parent.left = Node(value);
        } else {
            parent.right = Node(value);
        }
        return state.root;
    };
    
    const prettyPrint = (node = state.root, prefix = '', isLeft = true) => {
        if (node) {
            if (node.right !== null) {
                prettyPrint(node.right, `${prefix}${isLeft ? '│   ' : '    '}`, false);
            }
            console.log(`${prefix}${isLeft ? '└── ' : '┌── '}${node.data}`);
            if (node.left !== null) {
                prettyPrint(node.left, `${prefix}${isLeft ? '    ' : '│   '}`, true);
            }
        } else {
            console.log(node);
        }
    };
    
    // 用getter返回实时根节点，避免引用过时
    return {
        get root() { return state.root; },
        prettyPrint,
        insert
    };
};

// 测试代码
let b = [];
let d = Tree(b);
d.insert(4);
d.insert(8);
d.prettyPrint(); // 正常显示4和8的树结构
console.log(d.root); // 正确返回根节点对象

let a = [2,4,5,3,9,7,3,8,5];
let f = Tree(a);
f.insert(1);
f.prettyPrint(); // 正常插入1到树中

方案2：递归版insert #

如果偏好递归实现，替换上述insert函数为：

const insert = value => {
    const insertNode = (current, value) => {
        if (!current) {
            return Node(value);
        }
        if (value < current.data) {
            current.left = insertNode(current.left, value);
        } else if (value > current.data) {
            current.right = insertNode(current.right, value);
        }
        // 重复值不处理
        return current;
    };
    state.root = insertNode(state.root, value);
    return state.root;
};

关键修复点总结 #

1. 正确比较节点值：所有节点比较必须使用current.data，而非节点对象本身。
2. 挂载新节点：迭代版需跟踪父节点，递归版通过返回值赋值给父节点的left/right属性。
3. 根节点引用同步：用对象存储根节点并通过getter暴露，确保外部获取的始终是最新的根节点。
4. 处理重复值：插入时判断值是否已存在，避免重复插入破坏二叉搜索树结构。
5. 修正排序逻辑：调整mergeSort的参数顺序，保证数组正确排序。

内容的提问来源于stack exchange，提问作者Farzam