【译】JavaScript数据结构（4）：树

摘要：遍历树是访问树的每个节点的正式方式。想象一下，我们要将包含奇数数据的任何节点记录到控制台，并使用遍历树中的每个节点。第三个参数，是这个方法中用来遍历树的类型。与类似，移除将遍历树以查找包含第二个参数的节点，现在为。

翻译：疯狂的技术宅
英文：https://code.tutsplus.com/art...
说明：本文翻译自系列文章《Data Structures With JavaScript》，总共为四篇，原作者是在美国硅谷工作的工程师 Cho S. Kim。这是本系列的第四篇。

说明：本专栏文章首发于公众号：jingchengyideng 。

树是 web 开发中最常用的数据结构之一。 这种说法对开发者和用户都是正确的。每个编写HTML的开发者，只要把网页载入浏览器就会创建一个树，树通常被称为文档对象模型（DOM）。相应地，每个在互联网上浏览信息的人，也都是以DOM树的形式接受信息。 每个编写HTML并且将其加载到Web浏览器的Web开发人员都创建了一个树，这被称为文档对象模型（DOM）。互联网上的所有用户，在获取信息时，都是以树的形式收——即DOM。

现在，高潮来了：你正在读的本文在浏览器中就是以树的形式进行渲染的。文字由

元素进行表示；

元素又嵌套在元素中；元素又嵌套在元素中。 您正在阅读的段落表示为

元素中的文本；

元素嵌套在元素中；元素嵌套在元素中。

这些嵌套数据和家族数类似。 是父元素，是子元素，

又是的子元素 如果这个比喻对你有点用的话，你将会发现在我们介绍树的时候会用到更多的类比。

在本文中，我们将会通过两种不同的遍历方式来创建一个树：深度优先(DFS)和广度优先(BFS)。 （如果你对遍历这个词感到比较陌生，不妨将他想象成访问树中的每一个节点。） 这两种类型的遍历强调了与树交互的不同方式， DFS和BFS分别用栈和队列来访问节点。 这听起来很酷！

在计算机科学中，树是一种用节点来模拟分层数据的数据结构。每个树节点都包含他本身的数据及指向其他节点的指针。

节点和指针这些术语可能对一些读者来说比较陌生，所以让我们用类比来进一步描述他们。 让我们将树与组织图结构图进行比较。 这个结构图有一个顶级位置（根节点），比如CEO。 在这个节点下面还有一些其他的节点，比如副总裁(VP)。

为了表示这种关系，我们用箭头从CEO指向VP。 一个位置，比如CEO，是一个节点；我们创建的CEO到VP的关系是一个指针。 在我们的组织结构图中去创建更多的关系，我们只要重复这些步骤即可---我们让一个节点指向另一个节点。

在概念层次上，我希望节点和指针有意义。 在实际中，我们能从更科学的实例中获取收益。 让我们来思考DOM。 DOM有元素作为其顶级位置（根节点）。 这个节点指向元素和元素。 这些步骤在DOM的所有节点中重复。

这种设计的一个优点是能够嵌套节点：例如：一个

元素能够包含很多个
• 元素；此外，每个
• 元素能拥有兄弟
• 元素。这很怪异，但是确实真实有趣！
  操作树

  由于每个树都包含节点，其可以是来自树的多带带构造器，我们将概述两个构造函数的操作：Node和Tree

  节点

  data 存储值。

  parent 指向节点的父节点。

  children 指向列表中的下一个节点。

  树

  _root 指向一个树的根节点。

  traverseDF(callback) 对树进行DFS遍历。

  traverseBF(callback) 对树进行BFS遍历。

  contains(data, traversal) 搜索树中的节点。

  add(data, toData, traverse) 向树中添加节点。

  remove(child, parent) 移除树中的节点。

  实现树

  现在开始写树的代码！

  节点的属性

  在实现中，我们首先定义一个叫做Node的函数，然后构造一个Tree。

  function Node(data) {
      this.data = data;
      this.parent = null;
      this.children = [];
  }

  每一个Node的实例都包含三个属性：data，parant，和children。 第一个属性保存与节点相关联的数据。 第二个属性指向一个节点。 第三个属性指向许多子节点。

  树的属性

  现在让我们来定义Tree的构造函数，其中包括Node构造函数的定义：

  function Tree(data) {
      var node = new Node(data);
      this._root = node;
  }

  Tree包含两行代码。 第一行创建了一个Node的新实例；第二行让node等于树的根节点。

  Tree和Node的定义只需要几行代码。 但是，通过这几行足以帮助我们模拟分层数据。 为了证明这一点，让我们用一些示例数据去创建Tree的示例（和间接的Node）。

  var tree = new Tree("CEO");
   
  // {data: "CEO", parent: null, children: []}
  tree._root;

  幸好有parent和children的存在，我们可以为_root添加子节点和让这些子节点的父节点等于_root。 换一种说法，我们可以模拟分层数据的创建。

  Tree的方法

  接下来我们将要创建以下五种方法。

  树

  traverseDF(callback)

  traverseBF(callback)

  contains(data, traversal)

  add(child, parent)

  remove(node, parent)

  因为每种方法都需要遍历一个树，所以我们首先要实现一个方法去定义不同的树遍历。 （遍历树是访问树的每个节点的正式方式。）

  方法1/5: traverseDF(callback)

  这种方法以深度优先方式遍历树。

  Tree.prototype.traverseDF = function(callback) {
   
      // this is a recurse and immediately-invoking function 
      (function recurse(currentNode) {
          // step 2
          for (var i = 0, length = currentNode.children.length; i < length; i++) {
              // step 3
              recurse(currentNode.children[i]);
          }
   
          // step 4
          callback(currentNode);
           
          // step 1
      })(this._root);
   
  };

  traverseDF(callback)有一个参数callback。 如果对这个名字不明白，callback被假定是一个函数，将在后面被traverseDF(callback)调用。

  traverseDF(callback)的函数体含有另一个叫做recurse的函数。 这个函数是一个递归函数！ 换句话说，它是自我调用和自我终止。 使用recurse的注释中提到的步骤，我将描述递归用来recurse整个树的一般过程。

  这里是步骤：

  立即使用树的根节点作为其参数调用recurse。 此时，currentNode指向当前节点。

  进入for循环并且从第一个子节点开始，每一个子节点都迭代一次currentNode函数。

  在for循环体内，使用currentNode的子元素调用递归。 确切的子节点取决于当前for循环的当前迭代。

  当currentNode不存在子节点时，我们退出for循环并callback我们在调用traverseDF（callback）期间传递的回调。

  步骤2（自终止），3（自调用）和4（回调）重复，直到我们遍历树的每个节点。

  递归是一个非常困难的话题，需要一个完整的文章来充分解释它。由于递归的解释不是本文的重点 —— 重点是实现一棵树 —— 我建议任何读者没有很好地掌握递归做以下两件事。

  首先，实验我们当前的traverseDF(callback)实现，并尝试一定程度上理解它是如何工作的。 第二，如果你想要我写一篇关于递归的文章，那么请在本文的评论中请求它。

  以下示例演示如何使用traverseDF(callback)遍历树。要遍历树，我将在下面的示例中创建一个。我现在使用的方法不是罪理想的，但它能很好的工作。 一个更好的方法是使用add(value)，我们将在第4步和第5步中实现。

  var tree = new Tree("one");
   
  tree._root.children.push(new Node("two"));
  tree._root.children[0].parent = tree;
   
  tree._root.children.push(new Node("three"));
  tree._root.children[1].parent = tree;
   
  tree._root.children.push(new Node("four"));
  tree._root.children[2].parent = tree;
   
  tree._root.children[0].children.push(new Node("five"));
  tree._root.children[0].children[0].parent = tree._root.children[0];
   
  tree._root.children[0].children.push(new Node("six"));
  tree._root.children[0].children[1].parent = tree._root.children[0];
   
  tree._root.children[2].children.push(new Node("seven"));
  tree._root.children[2].children[0].parent = tree._root.children[2];
   
  /*
   
  creates this tree
   
   one
   ├── two
   │   ├── five
   │   └── six
   ├── three
   └── four
       └── seven
   
  */

  现在，让我们调用traverseDF(callback)。

  tree.traverseDF(function(node) {
      console.log(node.data)
  });
   
  /*
   
  logs the following strings to the console
   
  "five"
  "six"
  "two"
  "three"
  "seven"
  "four"
  "one"
   
  */

  方法2/5: traverseBF(callback)

  这个方法使用深度优先搜索去遍历树

  深度优先搜索和广度优先搜索之间的差别涉及树的节点访问的序列。 为了说明这一点，让我们使用traverseDF(callback)创建的树。

  /* 
   tree
   
   one (depth: 0)
   ├── two (depth: 1)
   │   ├── five (depth: 2)
   │   └── six (depth: 2)
   ├── three (depth: 1)
   └── four (depth: 1)
       └── seven (depth: 2)
   */

  现在，让我们传递traverseBF(callback)和我们用于traverseDF（callback）的回调。

  tree.traverseBF(function(node) {
      console.log(node.data)
  });
   
  /*
   
  logs the following strings to the console
   
  "one"
  "two"
  "three"
  "four"
  "five"
  "six"
  "seven"
   
  */

  来自控制台的日志和我们的树的图显示了关于广度优先搜索的模式。从根节点开始；然后行进一个深度并访问该深度从左到右的每个节点。重复此过程，直到没有更多的深度要移动。

  由于我们有一个广度优先搜索的概念模型，现在让我们实现使我们的示例工作的代码。

  Tree.prototype.traverseBF = function(callback) {
      var queue = new Queue();
       
      queue.enqueue(this._root);
   
      currentTree = queue.dequeue();
   
      while(currentTree){
          for (var i = 0, length = currentTree.children.length; i < length; i++) {
              queue.enqueue(currentTree.children[i]);
          }
   
          callback(currentTree);
          currentTree = queue.dequeue();
      }
  };

  我们对traverseBF(callback)的定义包含了很多逻辑。 因此，我会用下面的步骤解释这些逻辑：

  创建 Queue的实例。

  调用traverseBF(callback)产生的节点添加到Queue的实例。

  定义一个变量currentNode并且将其值初始化为刚才添加到队列里的node

  当currentNode指向一个节点时，执行wille循环里面的代码。

  用for循环去迭代currentNode的子节点。

  在for循环体内，将每个子元素加入队列。

  获取currentNode并将其作为callback的参数传递。

  将currentNode重新分配给正从队列中删除的节点。

  直到currentNode不再指向任何节点——也就是说树中的每个节点都访问过了——重复4-8步。

  方法3/5 contains(callback, traversal)

  让我们定义一个方法，可以在树中搜索一个特定的值。去使用我们创建的任意一种树的遍历方法，我们已经定义了contains(callback, traversal)接收两个参数：搜索的数据和遍历的类型。

  Tree.prototype.contains = function(callback, traversal) {
      traversal.call(this, callback);
  };

  在contains(callback, traversal)函数体内，我们用call方法去传递this和callback。 第一个参数将traversal绑定到被调用的树contains（callback，traversal）；第二个参数是在树中每个节点上调用的函数。

  想象一下，我们要将包含奇数数据的任何节点记录到控制台，并使用BFS遍历树中的每个节点。 我们可以这么写代码：

  // tree is an example of a root node
  tree.contains(function(node){
      if (node.data === "two") {
          console.log(node);
      }
  }, tree.traverseBF);
  add(data, toData, traversal) 

  方法4/5: add(data, toData, traversal)

  现在有了一个可以搜索树中特定节点的方法。 让我们定义一个允许向指定节点添加节点的方法。

  Tree.prototype.add = function(data, toData, traversal) {
      var child = new Node(data),
          parent = null,
          callback = function(node) {
              if (node.data === toData) {
                  parent = node;
              }
          };
   
      this.contains(callback, traversal);
   
      if (parent) {
          parent.children.push(child);
          child.parent = parent;
      } else {
          throw new Error("Cannot add node to a non-existent parent.");
      }
  };

  add(data, toData, traversal)定义了三个参数。 第一个参数data用来创建一个Node的新实例。 第二个参数toData用来比较树中的每个节点。 第三个参数traversal，是这个方法中用来遍历树的类型。

  在add(data, toData, traversal)函数体内，我们声明了三个变量。 第一个变量child代表初始化的Node实例。 第二个变量parent初始化为null；但是将来会指向匹配toData值的树中的任意节点。parent的重新分配发生在我们声明的第三个变量，这就是callback。

  callback是一个将toData和每一个节点的data属性做比较的函数。 如果if语句的值是true，那么parent将被赋值给if语句中匹配比较的节点。

  每个节点的toData在contains(callback, traversal)中进行比较。遍历类型和callback必须作为contains(callback, traversal)的参数进行传递。

  最后，如果parent不存在于树中，我们将child推入parent.children； 同时也要将parent赋值给child的父级。否则，将抛出错误。

  让我们用add(data, toData, traversal)做个例子：

  var tree = new Tree("CEO");
   
  tree.add("VP of Happiness", "CEO", tree.traverseBF);
   
  /*
   
  our tree
   
  "CEO"
  └── "VP of Happiness"
   
  */

  这里是add(addData, toData, traversal)的更加复杂的例子：

  var tree = new Tree("CEO");
   
  tree.add("VP of Happiness", "CEO", tree.traverseBF);
  tree.add("VP of Finance", "CEO", tree.traverseBF);
  tree.add("VP of Sadness", "CEO", tree.traverseBF);
   
  tree.add("Director of Puppies", "VP of Finance", tree.traverseBF);
  tree.add("Manager of Puppies", "Director of Puppies", tree.traverseBF);
   
  /*
   
   tree
   
   "CEO"
   ├── "VP of Happiness"
   ├── "VP of Finance"
   │   ├── "Director of Puppies"
   │   └── "Manager of Puppies"
   └── "VP of Sadness"
   
   */

  方法5/5:remove(data, fromData, traversal)

  为了完成Tree的实现，我们将添加一个叫做remove(data, fromData, traversal)的方法。 跟从DOM里面移除节点类似，这个方法将移除一个节点和他的所有子级。

  Tree.prototype.remove = function(data, fromData, traversal) {
      var tree = this,
          parent = null,
          childToRemove = null,
          index;
   
      var callback = function(node) {
          if (node.data === fromData) {
              parent = node;
          }
      };
   
      this.contains(callback, traversal);
   
      if (parent) {
          index = findIndex(parent.children, data);
   
          if (index === undefined) {
              throw new Error("Node to remove does not exist.");
          } else {
              childToRemove = parent.children.splice(index, 1);
          }
      } else {
          throw new Error("Parent does not exist.");
      }
   
      return childToRemove;
  };

  与add(data, toData, traversal)类似，移除将遍历树以查找包含第二个参数的节点，现在为fromData。 如果这个节点被发现了，那么parent将指向它。

  在这时候，我们到达了第一个if语句。 如果parent不存在，将抛出错误。 如果parent不存在，我们使用parent.children调用findIndex（）和我们要从parent节点的子节点中删除的数据 （findIndex（）是一个帮助方法，我将在下面定义。）

  function findIndex(arr, data) {
      var index;
   
      for (var i = 0; i < arr.length; i++) {
          if (arr[i].data === data) {
              index = i;
          }
      }
   
      return index;
  }

  在findIndex()里面，以下逻辑将发生。 如果parent.children中的任意一个节点包含匹配data值的数据,那么变量index赋值为一个整数。 如果没有子级的数值属性匹配data，那么index保留他的默认值undefined。 在最后一行的findIndex()方法，我们返回一个index。

  我们现在去remove(data, fromData, traversal) 如果index的值是undefined，将会抛出错误。 如果index的值存在，我们用它来拼接我们想从parent的子节点中删除的节点。同样我们给删除的子级赋值为childToRemove。

  最后，我们返回childToRemove。

  树的的完整实现

  到此为止Tree已经完全实现。回过头看看，我们到底完成了多少工作：

  function Node(data) {
      this.data = data;
      this.parent = null;
      this.children = [];
  }
   
  function Tree(data) {
      var node = new Node(data);
      this._root = node;
  }
   
  Tree.prototype.traverseDF = function(callback) {
   
      // this is a recurse and immediately-invoking function
      (function recurse(currentNode) {
          // step 2
          for (var i = 0, length = currentNode.children.length; i < length; i++) {
              // step 3
              recurse(currentNode.children[i]);
          }
   
          // step 4
          callback(currentNode);
   
          // step 1
      })(this._root);
   
  };
   
  Tree.prototype.traverseBF = function(callback) {
      var queue = new Queue();
   
      queue.enqueue(this._root);
   
      currentTree = queue.dequeue();
   
      while(currentTree){
          for (var i = 0, length = currentTree.children.length; i < length; i++) {
              queue.enqueue(currentTree.children[i]);
          }
   
          callback(currentTree);
          currentTree = queue.dequeue();
      }
  };
   
  Tree.prototype.contains = function(callback, traversal) {
      traversal.call(this, callback);
  };
   
  Tree.prototype.add = function(data, toData, traversal) {
      var child = new Node(data),
          parent = null,
          callback = function(node) {
              if (node.data === toData) {
                  parent = node;
              }
          };
   
      this.contains(callback, traversal);
   
      if (parent) {
          parent.children.push(child);
          child.parent = parent;
      } else {
          throw new Error("Cannot add node to a non-existent parent.");
      }
  };
   
  Tree.prototype.remove = function(data, fromData, traversal) {
      var tree = this,
          parent = null,
          childToRemove = null,
          index;
   
      var callback = function(node) {
          if (node.data === fromData) {
              parent = node;
          }
      };
   
      this.contains(callback, traversal);
   
      if (parent) {
          index = findIndex(parent.children, data);
   
          if (index === undefined) {
              throw new Error("Node to remove does not exist.");
          } else {
              childToRemove = parent.children.splice(index, 1);
          }
      } else {
          throw new Error("Parent does not exist.");
      }
   
      return childToRemove;
  };
   
  function findIndex(arr, data) {
      var index;
   
      for (var i = 0; i < arr.length; i++) {
          if (arr[i].data === data) {
              index = i;
          }
      }
   
      return index;
  }

  总结

  树可以用来模拟分层数据。我们周围有许多类似这种类型的层次结构，例如网页和族谱。当你发现自己需要使用层次结构来结构化数据时，可以考虑使用树。

  欢迎扫描二维码关注公众号，每天推送我翻译的技术文章。