递归遍历二叉树的所有嵌套子节点Javascript

Question

我在玩二叉树。我正在尝试使用递归来查找所有嵌套的子值并将所有值推送到一个数组中。我从左边的树开始，看看它是否有效。我试图调用 childrenArray() 但控制台显示 childrenArray() 未定义。当我问 if (typeof BinaryTree.prototype.childrenArray === 'function') 时，它 returns true。请教我并告诉我为什么我无法执行我的代码？

var Tree = function(value) {
  if (!(this instanceof Tree)) {
    return new Tree(value);
  }
  this.value = value;
  this.children = [];
};

Tree.prototype.addChild = function(value) {
  var child = new Tree(value);
  this.children.push(child);
};

Tree.prototype.contains = function(value) {
  if (this.value === value) {
    return true;
  } else {
    for (var i = 0; i < this.children.length; i++) {
      if (this.children[i] && this.children[i].contains(value)) {
        return true;
      }
    }
    return false;
  }
};


var BinaryTree = function(value) {
  if (!(this instanceof BinaryTree)) {
    return new BinaryTree(value);
  }
  Tree.call(this, value);
};
BinaryTree.prototype = Object.create(Tree.prototype);

BinaryTree.prototype.addChild = function(value) {
  if (value < this.value) {
    if (this.children[0] === undefined) {
      this.children[0] = new BinaryTree(value);
    }
    this.children[0].addChild(value);
  } else if (value > this.value) {
    if (this.children[1] === undefined) {
      this.children[1] = new BinaryTree(value);
    }
    this.children[1].addChild(value);
  }
};
BinaryTree.prototype.contains = function(value) {
  if (value < this.value) {
    if (this.children[0] === undefined) {
      return false;
    }
    return this.children[0].contains(value);
  } else if (value > this.value) {
    if (this.children[1] === undefined) {
      return false;
    }
    return this.children[1].contains(value);
  }
};

var a = new BinaryTree();
a.value = 10;
a.addChild(4);
a.addChild(11);
a.addChild(3);

BinaryTree.prototype.childrenArray = function() {
  var results = [];

  if (this.value) {
    results.push(this.value);
  }

  if (this.children[0].length === 0) {

    return results;
  }

  for (var i = 0; i < this.children[0].children.length; i++) {
    if (this.children[i].value) {
      results.push(this.children[i].value);
      return this.childrenArray();
    }
  }

};

a.childrenArray();

Answer 1

正如 @melpomene 提到的，您正在调用 childArray 但您没有在任何地方定义它。我假设 return childArray(); 行错误地结束在那里，你可能意味着递归 return childrenArray 为根的左侧 child。

我想提一下你的循环本身（没有递归调用）：

for(var i = 0; i < this.children[0].children.length; i++) { // <-- you are iterating over the children of root's left child
     if(this.children[i].value) { // <-- but you are accessing root's current child
        results.push(this.children[i].value);
     }
}

有点混乱。您正在迭代 root 的左 child children[0].children 的 children，但是在每次迭代中您检查 root 的 children 自己 children[i] 有一个价值，你推动那个价值。这是不正确的，并且会中断，例如，如果根只有一个左 child 并且有两个 children（i 将超出范围）。

以下是解决此问题的方法。在您的案例中打印左树的递归可以分为以下情况：

如果当前节点没有值，return一个空数组

else 如果当前节点没有children，return只包含当前值的数组

否则如果当前节点有左child,运行childrenArray递归并将结果添加到results数组

这是它的样子：

BinaryTree.prototype.childrenArray = function() { var results = []; // case 1: if (this.value === undefined) { return results; } // case 2: results.push(this.value); if (this.children.length === 0) { return results; } // case 3: var leftChild = this.children[0]; if (leftChild) { results = results.concat(leftChild.childrenArray()); } /* add code here for the right child to complete your function */ return results; };

完整示例：

var BinaryTree = function(value) { this.value = value; this.children = []; }; BinaryTree.prototype.addChild = function (value) { if (value < this.value) { if (this.children[0] === undefined) { this.children[0] = new BinaryTree(value); } this.children[0].addChild(value); } else if (value > this.value) { if (this.children[1] === undefined) { this.children[1] = new BinaryTree(value); } this.children[1].addChild(value); } }; BinaryTree.prototype.childrenArray = function() { var results = []; // case 1: if (this.value === undefined) { return results; } // case 2: results.push(this.value); if (this.children.length === 0) { return results; } // case 3: var leftChild = this.children[0]; if (leftChild) { results = results.concat(leftChild.childrenArray()); } /* add code here for the right child to complete your function */ return results; }; var a = new BinaryTree(10); a.addChild(4); a.addChild(11); a.addChild(3); console.log(a.childrenArray()); // [10, 4, 3]

最后一件事，根据您的插入逻辑（如果较小则插入左侧，如果较大则插入右侧），您正在构建一个 Binary Search Tree not a Binary Tree. Binary tree's don't follow any particular insertion logic. Take a look at this question 以进行说明

递归遍历二叉树的所有嵌套子节点Javascript

Recursion to traverse all the nested child nodes of Binary Tree Javascript

javascript

recursion

binary-tree