JavaScript实现二叉搜索树中序遍历结果不符合预期问题求助

核心错误原因 #

• 数据类型导致比较逻辑错误：你调用add方法时传入的是字符串类型的数字（如"10"、"5"），BST逻辑中直接用</>运算符比较时，会按字符串字典序而非数值大小比对：
  例如字符串"5"和"10"比较时，第一个字符'5'的ASCII码远大于'1'，会判定"5" > "10"，导致原本应该放在根节点左子树的5被错误插入到右子树，整棵树的结构完全不符合预期，中序遍历自然不会输出升序序列。
• findMaxHeight方法实现错误：方法内部递归调用的是findMinHeight而非自身，导致高度计算逻辑完全错误。
• isBalanced方法逻辑错误：当前写的this.findMaxHeight() >= this.findMaxHeight() - 1永远为真，无法实现平衡校验的功能。

修复代码 #

1. 修正数据类型问题 #

要么调用add时直接传数值（去掉引号）：

var tree = new BST();
tree.add(10);
tree.add(19);
tree.add(17);
tree.add(21);
tree.add(5);
tree.add(1);
tree.add(6);

要么在add方法开头统一转换为数值：

add(data) {
    data = Number(data); // 新增类型转换
    // 原有逻辑不变
}

2. 修复findMaxHeight方法 #

findMaxHeight(node = this.root) {
    if (node == null) {
        return -1;
    };
    // 将原有调用findMinHeight改为调用findMaxHeight
    let left = this.findMaxHeight(node.left);
    let right = this.findMaxHeight(node.right);
    if (left > right) {
        return left + 1;
    } else {
        return right + 1;
    };
};

3. 修复isBalanced方法 #

isBalanced() {
    // 平衡判定逻辑为最大高度与最小高度差值不超过1
    return (this.findMaxHeight() - this.findMinHeight() <= 1);
}

验证结果 #

修复后调用console.log(tree.inOrder())会输出预期的升序序列：

[1, 5, 6, 10, 17, 19, 21]

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