使用JavaScript的数据结构：Tree

使用JavaScript的数据结构：Tree 第1张

树是Web开发中最常用的数据结构之一。此声明适用于开发人员和用户。每个编写 html 并将其加载到 Web 浏览器中的 Web 开发人员都创建了一个树，称为文档对象模型 (dom)。反过来，每个在 Internet 上消费信息的 Internet 用户都以树的形式收到了信息——DOM。

没错，此时您正在阅读的文章在您的浏览器中呈现为一棵树！您正在阅读的段落表示为<p>元素中的文本；该<p>元素嵌套在一个<body>元素内；并且<body>元素嵌套在<html>元素内。

使用JavaScript的数据结构：Tree 第2张 HTML 页面的文档对象模型

数据的嵌套类似于家谱。<html>元素是父元素，<body>元素是子元素，元素<p>是元素的子<body>元素。如果树的这种类比对您有用，那么您会感到欣慰的是，在我们实现树的过程中将使用更多的类比。

在本文中，我们将使用两种不同的树遍历方法来创建树：深度优先搜索 (DFS) 和广度优先搜索 (BFS)。（如果您对遍历这个词不熟悉，可以认为它表示访问树的每个节点。）这两种遍历都突出了与树交互的不同方式。此外，这两次旅行都包含了我们在本系列中介绍的数据结构的使用。DFS 使用堆栈，BFS 使用队列访问节点。这很酷！

使用深度优先搜索和广度优先搜索遍历树

在计算机科学中，树是一种用节点模拟分层数据的数据结构。树的每个节点都有自己的数据和指向其他节点的指针。

节点和指针的术语对一些读者来说可能是新的，所以让我们用一个类比来进一步描述它们。让我们将树与组织结构图进行比较。图表有一个顶级职位（根节点），例如 CEO。该职位的正下方是其他职位，例如副总裁 (VP)。

使用JavaScript的数据结构：Tree 第3张组织树

为了表示这种关系，我们使用从 CEO 到 VP 的箭头。一个职位，比如CEO，就是一个节点；我们从 CEO 到 VP 建立的关系是一个指针。为了在我们的组织结构图中创建更多关系，我们只需重复这个过程——我们有一个节点指向另一个节点。

在概念层面上，我希望节点和指针有意义。在实践层面上，我们可以从使用更多技术示例中受益。让我们考虑一下 DOM。DOM 有一个<html>元素作为其顶级位置（根节点）。这个节点指向一个<head>元素和一个<body>元素。对 DOM 中的所有节点重复此结构。

这种设计的优点之一是嵌套节点的能力：<ul>例如，一个元素可以在其中<li>嵌套许多元素；此外，每个<li>元素都可以有兄弟<li>节点。

深度优先搜索 (DFS)

深度优先搜索或 DFS 从初始节点开始并深入到树中，直到找到所需的元素或没有子元素的元素（叶子）。然后，它从叶节点回溯并访问尚未探索的最新节点。

使用JavaScript的数据结构：Tree 第4张深度优先搜索

广度优先搜索 (BFS)

在广度优先搜索中，树遍历从根节点开始，首先遍历所有相邻节点。然后，它选择最近的节点并探索新节点。对每个节点重复此方法，直到它到达目的地。

使用JavaScript的数据结构：Tree 第5张广度优先搜索

树的操作

由于每棵树都包含节点，这些节点可以是与树分开的构造函数，我们将概述这两个构造函数的操作：node和Tree。

节点

data存储一个值
parent指向节点的父节点
children指向列表中的下一个节点

树

_root指向树的根节点
find(data): 返回包含给定数据的节点
add(data, parentData)：向包含给定数据的父节点添加一个新节点
remove(data)：删除包含给定数据的节点
forEach(callback): 在树的每个节点上以深度优先顺序运行回调
forEachBreathFirst(callback)：以广度优先顺序在树的每个节点上运行回调

在 javascript 中实现树

现在让我们编写一棵树的代码！

`Node` 班级_

对于我们的实现，我们将首先定义一个名为的类Node，然后定义一个名为的构造函数Tree。

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

Node 的每个实例都包含三个属性：data、parent和children。第一个属性保存与节点关联的数据——树的有效负载。parent指向该节点是其子节点的单个节点。children指向该节点的所有子节点。

`Tree`班级_

现在，让我们为定义我们Tree的构造函数，它的定义中包含Node构造函数：

class Tree {
    constructor(data) {
      let node = new Node(data);
      this._root = node;
    }
    
    //other Tree methods...
  }

Tree包含两行代码。第一行创建一个 ; 的新实例Node。第二行指定node为树的根。

Tree和的定义Node只需要几行代码。然而，这些线足以帮助我们模拟分层数据。为了证明这一点，让我们使用一些示例数据来创建Tree（并且，间接地，Node）的实例。

let tree = new Tree('CEO');

  // {data: 'CEO', parent: null, children: []}
  tree._root;

由于 and 的存在parent，children我们可以将节点添加为这些节点的子节点，_root也可以将其分配_root为这些节点的父节点。换句话说，我们可以模拟分层数据的创建。

方法`Tree`

接下来，我们将创建以下五个方法：

find(data): 返回包含给定数据的节点
add(data, parentData)：向包含给定数据的父节点添加一个新节点
remove(data)：删除包含给定数据的节点
forEach(callback): 在树的每个节点上以深度优先顺序运行回调
forEachBreathFirst(callback)：以广度优先顺序在树的每个节点上运行回调

由于 add 和 remove 方法需要我们找到一个特定的节点，我们将从该方法开始，使用深度优先搜索。

深度优先搜索`find(data)`

此方法使用深度优先搜索遍历树。

   //returns the node that has the given data, or null
    //use a depth-first search 
    find(data, node = this._root) {
        //if the current node matches the data, return it
        if (node.data == data)
            return node;

        //recurse on each child node
        for (let child of node.children) {
            //if the data is found in any child node it will be returned here 
            if (this.find(data, child))
                return child;
        }   
        
        //otherwise, the data was not found
        return null;
    }

find()是一个递归函数，带有一个参数，用于查找要查找的数据和要在其下搜索的节点。find还有一个当前节点的参数——它从树根开始，后来用于递归子节点。

for迭代的每个孩子，node从第一个孩子开始。在for循环体中，我们find()用那个孩子递归地调用函数。当找到数据时，它将通过整个函数调用堆栈返回，终止搜索。

如果没有找到匹配的节点，最终会返回 null。

请注意，这是一种深度优先搜索——find 将递归地向下钻取到树的叶节点并向上工作。

理解递归

递归是一个很难教授的话题，需要整篇文章来充分解释它。由于递归的解释不是本文的重点——重点是实现一棵树——我建议任何对递归缺乏很好理解的读者尝试我们的实现find() 并尝试理解它是如何工作的。

我将在下面包含一个实时示例，以便您尝试一下。

向树中添加元素

下面是我们add方法的实现：

  //create a new node with the given data and add it to the specified parent node
    add(data, parentData) {
        let node = new Node(data);
        let parent = this.find(parentData);

        //if the parent exists, add this node
        if (parent) {
            parent.children.push(node);
            node.parent = parent;

            //return this node
            return node;
        }
        //otherwise throw an error
        else {
            throw new Error(`Cannot add node: parent with data ${parentData} not found.`);
        }
    }

该add方法允许我们指定新节点的数据，以及我们想要添加它的父节点。

首先我们用给定的数据搜索父节点。如果找到，我们会将新节点添加到父节点的子节点列表中。我们还将父节点链接到新节点。现在新节点被链接到它在树中的位置。

从树中删除元素

下面是我们将如何实现我们的 remove 方法：

    //removes the node with the specified data from the tree
    remove(data) {
        //find the node
        let node = this.find(data)

        //if the node exists, remove it from its parent
        if (node) {
            //find the index of this node in its parent
            let parent = node.parent;
            let indexOfNode = parent.children.indexOf(node);
            //and delete it from the parent
            parent.children.splice(indexOfNode, 1);
        }
        //otherwise throw an error
        else {
            throw new Error(`Cannot remove node: node with data ${data} not found.`);
        }
    }

就像add方法一样，首先我们搜索具有给定数据的节点。当我们找到它时，我们可以通过从其父节点中删除该节点及其所有子节点来从树中删除它。在这里，我们使用indexOf()在父级的子级列表中查找节点，然后我们使用splice()从该列表中删除它。

深度优先树遍历`forEach()`

接下来，我们将向forEach()我们的树添加一个方法，以便我们可以遍历它并对每个节点应用自定义回调。

    //depth-first tree traversal
    //starts at the root
    forEach(callback, node = this._root) {
        //recurse on each child node
        for (let child of node.children) {
            //if the data is found in any child node it will be returned here 
            this.forEach(callback, child);
        }   
        
        //otherwise, the data was not found
        callback(node);
    }

就像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
CEO

广度优先遍历`forEachBreadthFirst()`

对于大多数用途，深度优先搜索更简单且同样有效，但有时需要广度优先遍历。这是我们Tree类的最终方法。

    //breadth-first tree traversal
    forEachBreadthFirst(callback) {
        //start with the root node
        let queue = [];
        queue.push(this._root);
    
        //while the queue is not empty
        while (queue.length > 0) {
            //take the next node from the queue  
            let node = queue.shift();
            
            //visit it
            callback(node);

            //and enqueue its children
            for (let child of node.children) {
                queue.push(child);
            }
        }
    }

深度优先遍历使用递归搜索树，广度优先遍历使用队列结构。当每个节点被访问时，它的子节点被推到队列的后面。下一个要访问的节点取自队列的最前面，这确保了更高级别的节点在其子节点之前被访问。

使用与上面相同的树，如果我们用遍历树forEachBreadthFirst()，我们将以不同的顺序访问节点。这是代码：

t.forEachBreadthFirst(node => console.log(node.data));

这是它产生的遍历：

CEO
VP Finance
VP Sales
Accountant
Bookkeeper
Salesperson

如您所见，这一次节点是从上到下遍历的。

JavaScript 树结构的交互式示例

这是一个包含这篇文章中所有代码的交互式示例。您可以尝试创建不同的树并修改或遍历它们。

结论

树模拟分层数据。我们周围的大部分世界都类似于这种层次结构，例如网页和我们的家庭。每当您发现自己需要使用层次结构来构建数据时，请考虑使用树！

文章目录

使用深度优先搜索和广度优先搜索遍历树

深度优先搜索 (DFS)
广度优先搜索 (BFS)
树的操作
- 节点
- 树

在 javascript 中实现树

Node 班级_
Tree班级_

方法Tree

深度优先搜索find(data)
- 理解递归
向树中添加元素
从树中删除元素
深度优先树遍历forEach()
广度优先遍历forEachBreadthFirst()

JavaScript 树结构的交互式示例

结论

使用深度优先搜索和广度优先搜索遍历树

深度优先搜索 (DFS)

广度优先搜索 (BFS)

树的操作

节点

树

在 javascript 中实现树

Node 班级_

Tree班级_

方法Tree

深度优先搜索find(data)

理解递归

向树中添加元素

从树中删除元素

深度优先树遍历forEach()

广度优先遍历forEachBreadthFirst()

JavaScript 树结构的交互式示例

结论

相关推荐

最新文章 | 热门文章 | 随机文章

`Node` 班级_

`Tree`班级_

方法`Tree`

深度优先搜索`find(data)`

深度优先树遍历`forEach()`

广度优先遍历`forEachBreadthFirst()`