Files
freeCodeCamp/curriculum/challenges/chinese/10-coding-interview-prep/data-structures/add-a-new-element-to-a-binary-search-tree.md

7.0 KiB
Raw Permalink Blame History

id, title, challengeType, forumTopicId, dashedName
id title challengeType forumTopicId dashedName
587d8257367417b2b2512c7b 将新元素添加到二叉搜索树 1 301618 add-a-new-element-to-a-binary-search-tree

--description--

这一系列的挑战将介绍树形数据结构。 树是计算机科学中一个重要的、通用的数据结构。 当然,它们的名称来自这样一个事实:当可视化时,它们看起来很像我们在自然界中熟悉的树木。 树数据结构从一个节点(通常称为根)开始,并从此处分支到其他节点,每个节点可能具有更多的子节点,依此类推。 数据结构通常以根节点为顶点进行可视化;你可以把它想象成一棵倒过来的自然树。

首先,让我们描述一下我们将遇到的关于树的一些常见术语。 根节点root是树的顶部。 树中的数据点称为节点node。 分支通向其他节点的节点称为分支通向的节点(即子节点)的父节点。 如你所料,其他更复杂的家庭术语也适用。 子树指的是某一特定节点的所有后代,分支可称为边,而叶子节点是位于树的末端的且没有子节点的节点。 最后,请注意,树本质上是递归的数据结构。 也就是说,一个节点的任何子节点都是其自己的子树的父节点,依此类推。 在为常见的树操作设计算法时,树的递归性质很重要。

首先,我们将讨论树的一个特殊类型,即二叉树。 实际上,我们将讨论特定的二叉树,即二叉搜索树。 让我们来看看这意味着什么。 虽然树形数据结构在一个节点上可以有任意数量的分支,但二叉树每个节点只能有两个分支。 此外,一个二叉搜索树相对于其子子树是有序的,即对于一个节点而言,其左子树中每个节点的值都小于或等于该节点的值,而其右子树中每个节点的值都大于或等于该节点的值。 为了更好地理解这种关系,将这种关系形象化是非常有帮助的:

现在,这种有序的关系是非常容易看到的。 注意,根节点 8 左边的每个值都小于 8右边的每个值都大于 8。 还要注意的是,这种关系也适用于每个子树。 例如,第一个左孩子节点是一个子树。 3 是父节点,它正好有两个子节点——根据二进制搜索树的规则,我们甚至不用看就知道这个节点的左子节点(以及它的任何子节点)都将小于 3右子节点以及它的任何子节点都将大于 3但也小于根结点的值依此类推。

二叉搜索树是非常常见且有用的数据结构,因为它们在几种常见操作(例如查找、插入和删除)的平均情况下提供对数的时间复杂度。

--instructions--

我们将从简单的内容开始。 我们在这里定义了一个二叉搜索树结构的骨架,此外还有一个为我们的树创建节点的函数。 注意观察每个节点可能有一个左值和右值。 如果子树存在,它们将被分配给对应的子树。 在我们的二叉搜索树中,你将创建一个方法来向我们的二叉搜索树添加新的值。 该方法应该被称为add ,它应该接受一个整数值来添加到树中。 注意保持二叉搜索树的不变量:每个左子项中的值应小于或等于父值,并且每个右子项中的值应大于或等于父值。 在这里,让我们确保我们的树不会含有重复的值。 如果我们尝试添加已存在的值,则该方法应返回null 。 否则,如果添加成功,则应返回undefined

提示: 树是自然的递归数据结构!

--hints--

存在 BinarySearchTree 的数据结构。

assert(
  (function () {
    var test = false;
    if (typeof BinarySearchTree !== 'undefined') {
      test = new BinarySearchTree();
    }
    return typeof test == 'object';
  })()
);

二叉搜索树应该有一个名为 add 的方法。

assert(
  (function () {
    var test = false;
    if (typeof BinarySearchTree !== 'undefined') {
      test = new BinarySearchTree();
    } else {
      return false;
    }
    return typeof test.add == 'function';
  })()
);

添加的方法应该根据二叉搜索树的规则来添加元素。

assert(
  (function () {
    var test = false;
    if (typeof BinarySearchTree !== 'undefined') {
      test = new BinarySearchTree();
    } else {
      return false;
    }
    if (typeof test.add !== 'function') {
      return false;
    }
    test.add(4);
    test.add(1);
    test.add(7);
    test.add(87);
    test.add(34);
    test.add(45);
    test.add(73);
    test.add(8);
    const expectedResult = [1, 4, 7, 8, 34, 45, 73, 87];
    const result = test.inOrder();
    return expectedResult.toString() === result.toString();
  })()
);

添加一个已经存在的元素应该返回 null

assert(
  (function () {
    var test = false;
    if (typeof BinarySearchTree !== 'undefined') {
      test = new BinarySearchTree();
    } else {
      return false;
    }
    if (typeof test.add !== 'function') {
      return false;
    }
    test.add(4);
    return test.add(4) == null;
  })()
);

--seed--

--after-user-code--

BinarySearchTree.prototype = Object.assign(
  BinarySearchTree.prototype,
  {
    inOrder() {
      if (!this.root) {
        return null;
      }
      var result = new Array();
      function traverseInOrder(node) {
        node.left && traverseInOrder(node.left);
        result.push(node.value);
        node.right && traverseInOrder(node.right);
      }
      traverseInOrder(this.root);
      return result;
    }
  }
);

--seed-contents--

var displayTree = tree => console.log(JSON.stringify(tree, null, 2));
function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
function BinarySearchTree() {
  this.root = null;
  // Only change code below this line

  // Only change code above this line
}

--solutions--

function Node(value) {
  this.value = value;
  this.left = null;
  this.right = null;
}
function BinarySearchTree() {
  this.root = null;
  this.add = function(element) {
    let current = this.root;
    if (!current) {
      this.root = new Node(element);
      return;
    } else {
      const searchTree = function(current) {
        if (current.value > element) {
          if (current.left) {
            return searchTree(current.left);
          } else {
            current.left = new Node(element);
            return;
          }
        } else if (current.value < element) {
          if (current.right) {
            return searchTree(current.right);
          } else {
            current.right = new Node(element);
            return;
          }
        } else {
          return null;
        }
      };
      return searchTree(current);
    }
  };
}