二分搜索树实现depthFirstTraversal运行无输出问题咨询

问题原因 #

你的代码存在两处核心问题导致无输出、也无法得到升序结果：

• 首先，depthFirstTraversel方法全程没有调用你传入的iteratorFunc回调函数，自然不会执行console.log打印任何内容，控制台就是空白的。
• 其次，你要实现的升序遍历对应二叉搜索树的中序遍历，执行顺序是「遍历左子树 → 处理当前节点值 → 遍历右子树」，你的代码只写了左右子树的遍历逻辑，漏掉了当前节点值的处理步骤，就算补上回调调用，顺序也不对。

修复后的代码 #

class BST {
  constructor(value) {
    this.left = null;
    this.right = null;
    this.value = value;
  }

  insert(value) {
    if (value <= this.value) {
      if (!this.left) this.left = new BST(value);
      else this.left.insert(value);
    } else if (value > this.value) {
      if (!this.right) this.right = new BST(value);
      else this.right.insert(value);
    }
  }

  depthFirstTraversel = (iteratorFunc) => {    
    if (this.left) this.left.depthFirstTraversel(iteratorFunc);
    // 补上当前节点的回调调用，放在左子树遍历之后、右子树遍历之前，就是中序遍历
    iteratorFunc(this.value);
    if (this.right) this.right.depthFirstTraversel(iteratorFunc);
  };
}

function log(value) {
  console.log(value);
}

const bst = new BST(50);
bst.insert(30);
bst.insert(70);
bst.insert(100);
bst.insert(60);
bst.insert(59);
bst.insert(20);
bst.insert(45);
bst.insert(35);
bst.insert(85);
bst.insert(105);
bst.insert(10);

bst.depthFirstTraversel(log);

运行修复后的代码就会按升序依次输出10、20、30、35、45、50、59、60、70、85、100、105。

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