JS中DepthFirstInOrder递归遍历测试失败，无法正确输出节点值

我在BinaryTree类中实现了递归的深度优先中序遍历方法traverseDepthFirstInOrder，但不清楚该在哪里添加当前节点的处理逻辑，才能让测试代码正确获取左右子节点的值。试了所有可能的位置都没成功，调试时只能拿到值或者[Function (anonymous)]。

方法代码：

traverseDepthFirstInOrder(fn) {
    //handle left child (if exists)
    if (this.left) {
        this.left.traverseDepthFirstInOrder(fn);
    }
    //handle right child (if exists)
    if (this.right) {
        this.right.traverseDepthFirstInOrder(fn);
    }
}

测试代码：

test("should call the fn on left nodes, center nodes, then right nodes", () => {
    let test = [];
    binaryTree.add(4);
    binaryTree.add(14);
    binaryTree.add(6);
    binaryTree.add(16);
    binaryTree.add(2);
    binaryTree.add(12);
    binaryTree.traverseDepthFirstInOrder(e => test.push(e.value));
    expect(test).toEqual([2, 4, 6, 10, 12, 14, 16]);
});

终端报错：

• Expected - 9
  • Received + 1

解决方案 #

中序遍历的核心顺序是左子树 → 当前节点 → 右子树，你现在的代码只递归处理了左右子树，完全漏掉了当前节点的回调调用。正确的做法是在处理完左子树之后，调用fn(this)把当前节点传给回调函数，再去处理右子树。

修正后的代码：

traverseDepthFirstInOrder(fn) {
    // 先处理左子树
    if (this.left) {
        this.left.traverseDepthFirstInOrder(fn);
    }
    // 处理当前节点，将节点对象传给回调
    fn(this);
    // 最后处理右子树
    if (this.right) {
        this.right.traverseDepthFirstInOrder(fn);
    }
}

这样调整后，测试代码里的回调e => test.push(e.value)就能正确拿到每个节点的value，最终test数组的顺序会符合中序遍历的预期。另外注意测试预期里的10，你添加的节点中并没有这个值，可能是测试用例的笔误，需要对应调整。

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