树是Web开发中最常用的数据结构之一。此声明适用于开发人员和用户。每个编写 HTML 并将其加载到 Web 浏览器中的 Web 开发人员都创建了一个树，称为文档对象模型 (DOM)。反过来，每个在 Internet 上消费信息的 Internet 用户都以树的形式收到了信息——DOM。
没错，此时您正在阅读的文章在您的浏览器中呈现为一棵树！您正在阅读的段落表示为元素中的文本；该元素嵌套在一个元素内；并且元素嵌套在元素内。
HTML 页面的文档对象模型
数据的嵌套类似于家谱。元素是父元素，元素是子元素，元素是元素的子元素。如果树的这种类比对您有用，那么您会感到欣慰的是，在我们实现树的过程中将使用更多的类比。
在本文中，我们将使用两种不同的树遍历方法来创建树：深度优先搜索 (DFS) 和广度优先搜索 (BFS)。（如果您对遍历这个词不熟悉，可以认为它表示访问树的每个节点。）这两种遍历都突出了与树交互的不同方式。此外，这两次旅行都包含了我们在本系列中介绍的数据结构的使用。DFS 使用堆栈，BFS 使用队列访问节点。这很酷！
在计算机科学中，树是一种用节点模拟分层数据的数据结构。树的每个节点都有自己的数据和指向其他节点的指针。
节点和指针的术语对一些读者来说可能是新的，所以让我们用一个类比来进一步描述它们。让我们将树与组织结构图进行比较。图表有一个顶级职位（根节点），例如 CEO。该职位的正下方是其他职位，例如副总裁 (VP)。
组织树
为了表示这种关系，我们使用从 CEO 到 VP 的箭头。一个职位，比如CEO，就是一个节点；我们从 CEO 到 VP 建立的关系是一个指针。为了在我们的组织结构图中创建更多关系，我们只需重复这个过程——我们有一个节点指向另一个节点。
在概念层面上，我希望节点和指针有意义。在实践层面上，我们可以从使用更多技术示例中受益。让我们考虑一下 DOM。DOM 有一个元素作为其顶级位置（根节点）。这个节点指向一个元素和一个元素。对 DOM 中的所有节点重复此结构。
这种设计的优点之一是嵌套节点的能力：例如，一个元素可以在其中嵌套许多元素；此外，每个元素都可以有兄弟节点。
深度优先搜索或 DFS 从初始节点开始并深入到树中，直到找到所需的元素或没有子元素的元素（叶子）。然后，它从叶节点回溯并访问尚未探索的最新节点。
深度优先搜索
在广度优先搜索中，树遍历从根节点开始，首先遍历所有相邻节点。然后，它选择最近的节点并探索新节点。对每个节点重复此方法，直到它到达目的地。
广度优先搜索
由于每棵树都包含节点，这些节点可以是与树分开的构造函数，我们将概述这两个构造函数的操作：Node和Tree。
现在让我们编写一棵树的代码！
对于我们的实现，我们将首先定义一个名为的类Node，然后定义一个名为 的构造函数Tree。
类节点{
构造函数（数据）{
this.data = 数据；
this.parent = null;
this.children = [];
}
}
Node 的每个实例都包含三个属性：data、parent和children。第一个属性保存与节点关联的数据——树的有效负载。parent指向该节点是其子节点的单个节点。children指向该节点的所有子节点。
现在，让我们为 定义我们Tree的构造函数，它的定义中包含Node构造函数：
类树 {
构造函数（数据）{
让节点=新节点（数据）；
this._root = 节点；
}
//其他树方法...
}
Tree包含两行代码。第一行创建一个 ; 的新实例Node。第二行指定node为树的根。
Tree和的定义Node只需要几行代码。然而，这些线足以帮助我们模拟分层数据。为了证明这一点，让我们使用一些示例数据来创建Tree（并且，间接地，Node）的实例。
让 tree = new Tree('CEO');
// {数据：'CEO'，父母：空，孩子：[]}
树._root;
由于 and 的存在parent，children我们可以将节点添加为这些节点的子节点，_root也可以将其分配_root为这些节点的父节点。换句话说，我们可以模拟分层数据的创建。
接下来，我们将创建以下五个方法：
由于 add 和 remove 方法需要我们找到一个特定的节点，我们将从该方法开始，使用深度优先搜索。
此方法使用深度优先搜索遍历树。
//返回具有给定数据的节点，或null
//使用深度优先搜索
查找（数据，节点 = this._root）{
//如果当前节点与数据匹配，则返回
如果（node.data == 数据）
返回节点；
//递归每个子节点
for (let child of node.children) {
//如果在任何子节点中找到数据，将在此处返回
如果（this.find（数据，孩子））
归还孩子；
}
//否则，找不到数据
返回空值；
}
find()是一个递归函数，带有一个参数，用于查找要查找的数据和要在其下搜索的节点。find还有一个当前节点的参数——它从树根开始，后来用于递归子节点。
for迭代 的每个孩子，node从第一个孩子开始。在for循环体中，我们find()用那个孩子递归地调用函数。当找到数据时，它将通过整个函数调用堆栈返回，终止搜索。
如果没有找到匹配的节点，最终会返回 null。
请注意，这是一种深度优先搜索——find 将递归地向下钻取到树的叶节点并向上工作。
递归是一个很难教授的话题，需要整篇文章来充分解释它。由于递归的解释不是本文的重点——重点是实现一棵树——我建议任何对递归缺乏很好理解的读者尝试我们的实现find() 并尝试理解它是如何工作的。
我将在下面包含一个实时示例，以便您尝试一下。
下面是我们add方法的实现：
//使用给定的数据创建一个新节点并将其添加到指定的父节点
添加（数据，父数据）{
让节点=新节点（数据）；
让父母 = this.find(parentData);
//如果父节点存在，添加这个节点
如果（父母）{
parent.children.push(node);
node.parent = 父级；
//返回这个节点
返回节点；
}
//否则抛出错误
别的 {
throw new Error(`Cannot add node: parent with data ${parentData} not found.`);
}
}
该add方法允许我们指定新节点的数据，以及我们想要添加它的父节点。
首先我们用给定的数据搜索父节点。如果找到，我们会将新节点添加到父节点的子节点列表中。我们还将父节点链接到新节点。现在新节点被链接到它在树中的位置。
下面是我们将如何实现我们的 remove 方法：
//从树中删除具有指定数据的节点
删除（数据）{
//找到节点
让节点 = this.find(数据)
//如果节点存在，将其从其父节点中移除
如果（节点）{
//在其父节点中查找该节点的索引
让父 = node.parent;
让 indexOfNode = parent.children.indexOf(node);
//并从父级中删除
parent.children.splice(indexOfNode, 1);
}
//否则抛出错误
别的 {
throw new Error(`Cannot remove node: node with data ${data} not found.`);
}
}
就像add方法一样，首先我们搜索具有给定数据的节点。当我们找到它时，我们可以通过从其父节点中删除该节点及其所有子节点来从树中删除它。在这里，我们使用indexOf()在父级的子级列表中查找节点，然后我们使用splice()从该列表中删除它。
接下来，我们将向forEach()我们的树添加一个方法，以便我们可以遍历它并对每个节点应用自定义回调。
//深度优先树遍历
//从根开始
forEach（回调，节点 = this._root）{
//递归每个子节点
for (let child of node.children) {
//如果在任何子节点中找到数据，将在此处返回
this.forEach(callback, child);
}
//否则，找不到数据
回调（节点）；
}
就像find()方法一样，这是深度优先遍历。这将访问树中的每个节点，从第一个分支的底部开始，遍历整个树。想象一只蚂蚁从一片叶子爬上树枝，然后又回到另一片叶子上，以此类推。
我们可以通过创建如下所示的新树来测试遍历。
let t = new Tree("CEO");
t.add("VP Finance", "CEO");
t.add("VP Sales", "CEO");
t.add("Salesperson", "VP Sales");
t.add("Accountant", "VP Finance");
t.add("Bookkeeper", "VP Finance");
t.forEach(node => console.log(node.data));
在forEach()调用中，我们创建了一个简单的回调，在每个节点被访问时将其记录到控制台。如果我们运行此代码，我们将得到以下输出。
Accountant
Bookkeeper
VP Finance
Salesperson
VP Sales
对于大多数用途，深度优先搜索更简单且同样有效，但有时需要广度优先遍历。这是我们Tree类的最终方法。
//广度优先树遍历
forEachBreadthFirst（回调）{
//从根节点开始
让队列 = [];
queue.push(this._root);
//当队列不为空时
而（队列长度> 0）{
//从队列中取出下一个节点
让节点 = queue.shift();
//访问它
回调（节点）；
//并将其子项入队
for (let child of node.children) {
queue.push(子);
}
}
}
深度优先遍历使用递归搜索树，广度优先遍历使用队列结构。当每个节点被访问时，它的子节点被推到队列的后面。下一个要访问的节点取自队列的最前面，这确保了更高级别的节点在其子节点之前被访问。
使用与上面相同的树，如果我们用 遍历树forEachBreadthFirst()，我们将以不同的顺序访问节点。这是代码：
t.forEachBreadthFirst(node => console.log(node.data));
这是它产生的遍历：
首席执行官
财务副总裁
销售副总裁
会计
会计
销售员
如您所见，这一次节点是从上到下遍历的。
这是一个包含这篇文章中所有代码的交互式示例。您可以尝试创建不同的树并修改或遍历它们。
树模拟分层数据。我们周围的大部分世界都类似于这种层次结构，例如网页和我们的家庭。每当您发现自己需要使用层次结构来构建数据时，请考虑使用树！
| 留言与评论（共有 0 条评论） “” |
