计算 Height/Depth 的二叉树 Javascript

Question

我只是初学者，如果错误太明显，我深表歉意。

我的两个问题是：

我们学校提供的代码中this.root是什么；
如何实现 .height 方法来测量树的深度。

说明：我们在 class:

中获得了此代码

function BinarySearchTree(value) {
  this.value = value;
  this.right = null;
  this.left = null;
}

BinarySearchTree.prototype.add = function(value) {
  let newLeaf = new BinarySearchTree(value)

  if(value > this.value){
    this.right === null? this.right = newLeaf : this.right.add(value)
  } else {
    this.left === null? this.left = newLeaf : this.left.add(value)
  }
};

我们应该写一个方法来计算二叉树的height/depth。现在，在练习时，我看到了一些奇怪的东西。在创建空二叉树的新节点时，第一个节点最终完全为空，同时它继续在第一个空节点的左侧创建一个新节点。嗯，不是空的，但是它的值是undefined。这是期望的行为吗？

let newTree = new BinarySearchTree
>undefined

newTree.add(7)
>undefined

newTree.add(3)
>undefined

newTree.add(5)
>undefined

newTree
>BinarySearchTree {value: undefined, right: null, left: BinarySearchTree}
  left: BinarySearchTree {value: 7, right: null, left: BinarySearchTree}
  right: null
  value: undefined
  [[Prototype]]: Object

现在，考虑到 .add 方法的测试已经通过，显然我在这种情况下可能是错误的，因为这是 class 中老师提供给我们的代码。这是我一直在网上找到的代码，我对 .heigth 方法的代码没有深入了解的原因是因为我无法实现 this.root:

function Node(val){
  this.value = val;
  this.left = null;
  this.right = null;
}


function BinarySearchTree(){
  this.root = null;
}

我应该如何继续 .height 方法？如果有帮助，这里是测试：

describe('Binary Search Tree', function() {
  var binarySearchTree;

  beforeEach(function() {
    binarySearchTree = new BinarySearchTree(5);
  });

  it('should have methods named "add", "contains", "depthFirstPre", "depthFirstIn", "depthFirstPost", "breadthFirst"', function() {
    expect(binarySearchTree.add).to.be.a("function");
  });

  it('should add values at the correct location in the tree', function(){
    binarySearchTree.add(2);
    binarySearchTree.add(3);
    binarySearchTree.add(7);
    binarySearchTree.add(6);
    expect(binarySearchTree.left.right.value).to.equal(3);
    expect(binarySearchTree.right.left.value).to.equal(6);
  });

  it('height method should return correct height', function() {
    binarySearchTree.left = new BinarySearchTree(3);
    binarySearchTree.left.left = new BinarySearchTree(1);
    expect(binarySearchTree.height()).to.eql(2);

    binarySearchTree.left.left.right = new BinarySearchTree(2);
    expect(binarySearchTree.height()).to.eql(3);

    binarySearchTree.left.left.left = new BinarySearchTree(0);
    expect(binarySearchTree.height()).to.eql(3);

    binarySearchTree.right = new BinarySearchTree(8);
    expect(binarySearchTree.height()).to.eql(3);
  });
}

再次，对于一个很长的问题，我深表歉意。我试图写下关于我的问题的所有相关信息。节日快乐！

Answer 1

What is this.root in our school's provided code

你们学校的模板代码没有管理什么是树的根，所以这必须由驱动程序代码在一个变量中管理。在测试代码中，这个变量被命名为 binarySearchTree，在第二个 (2-class) 实现中它确实被称为 this.root。

Now, while practicing, I've seen something odd. Upon creation of a new node of an empty binary tree, the first node ends up being completely empty [...] Is this a desired behavior?

不，这不是我们想要的行为。模板代码没有提供空二叉树的概念。它期望您创建至少具有一个值的树，该值应作为参数提供给构造函数。调用构造函数时无意省略参数。

2-class 实现提供了空树的概念。但是学校的模板代码没有；如果你想要一棵空树，你只需要声明 binarySearchTree = null 。但缺点很明显：您不能使用 class 的方法为其添加值。获取树中第一个值的唯一方法是调用构造函数并将构造的 object 分配给您的 binarySearchTree 变量。因此，将第一个值添加到树中需要采用与添加其他值不同的方法。这也是您在测试代码中看到的：第一个值作为参数添加到 constructor —— 这是 always 带参数调用的-- 而其他值是通过调用 add 方法添加的。这是一个遗憾，也确实显示了模板代码的局限性。

How can I implement the .height method in order to measure the depth of a Tree.

想法是你使用递归：

如果有左child，通过递归得到左子树的高度。如果有 none，则使用 -1 作为默认值，因为它是一个空子树，并且 empty trees have a height of -1。在右侧做同样的事情。获取这两个值中的最大值，因为只有两者中较高的子树才能确定树的高度。最后向该结果加一以说明当前节点。

BinarySearchTree.prototype.height = function() {
  return 1 + Math.max(
    this.left  !== null ? this.left.height()  : -1,
    this.right !== null ? this.right.height() : -1
  );
};

同样，由于学校模板代码的限制，您只能运行 height 方法生成一棵至少有一个节点的树。

为了完整起见，2-class 等效项会将上述代码放在 Node class 上，并会在 BinarySearchTree class，像这样：

Node.prototype.height = function() {
  return 1 + Math.max(
    this.left  !== null ? this.left.height()  : -1,
    this.right !== null ? this.right.height() : -1
  );
};

BinarySearchTree.prototype.height = function() {
  return this.root === null ? -1 : root.height();
}

计算 Height/Depth 的二叉树 Javascript

Calculate Height/Depth Of Binary Tree Javascript

javascript

binary-tree

nodes