JavaScript数据结构（4）：树

柔情只为你懂 2022-06-11 02:45 140阅读 0赞

> **翻译**：疯狂的技术宅  
> **说明**：本文翻译自系列文章《Data Structures With JavaScript》，总共为四篇，原作者是在美国硅谷工作的工程师 Cho S. Kim 。这是本系列的第四篇。  
> **原文**：[https://code.tutsplus.com/articles/data-structures-with-javascript-singly-linked-list-and-doubly-linked-list–cms-23393][https_code.tutsplus.com_articles_data-structures-with-javascript-singly-linked-list-and-doubly-linked-list_cms-23393]

![data-structures-4-of-4.jpg][]

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

现在，高潮来了：你正在读的本文在浏览器中就是以树的形式进行渲染的。文字由``元素进行表示；``元素又嵌套在`<body>`元素中；`<body>`元素又嵌套在`<html>`元素中。 您正在阅读的段落表示为``元素中的文本；``元素嵌套在`<body>`元素中；`<body>`元素嵌套在`<html>`元素中。

这些嵌套数据和家族数类似。 `<heml>`是父元素，`<body>`是子元素，``又是`<body>`的子元素 如果这个比喻对你有点用的话，你将会发现在我们介绍树的时候会用到更多的类比。

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

# **树（深度搜索和广度搜索）** #

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

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

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

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

这种设计的一个优点是能够嵌套节点：例如：一个`<ul>`元素能够包含很多个`<li>`元素；此外，每个`<li>`元素能拥有兄弟`<li>`元素。这很怪异，但是确实真实有趣！

## **操作树** ##

由于每个树都包含节点，其可以是来自树的单独构造器，我们将概述两个构造函数的操作：`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的方法** ###

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

#### **树** ####

1.  `traverseDF(callback)`
2.  `traverseBF(callback)`
3.  `contains(data, traversal)`
4.  `add(child, parent)`
5.  `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`整个树的一般过程。

这里是步骤：

1.  立即使用树的根节点作为其参数调用`recurse`。 此时，`currentNode`指向当前节点。
2.  进入`for`循环并且从第一个子节点开始，每一个子节点都迭代一次`currentNode`函数。
3.  在`for`循环体内，使用`currentNode`的子元素调用递归。 确切的子节点取决于当前`for`循环的当前迭代。
4.  当`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)`的定义包含了很多逻辑。 因此，我会用下面的步骤解释这些逻辑：

1.  创建 `Queue`的实例。
2.  调用`traverseBF(callback)`产生的节点添加到`Queue`的实例。
3.  定义一个变量`currentNode`并且将其值初始化为刚才添加到队列里的`node`
4.  当`currentNode`指向一个节点时，执行`wille`循环里面的代码。
5.  用`for`循环去迭代`currentNode`的子节点。
6.  在`for`循环体内，将每个子元素加入队列。
7.  获取`currentNode`并将其作为`callback`的参数传递。
8.  将`currentNode`重新分配给正从队列中删除的节点。
9.  直到`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`已经完全实现。回过头看看，我们到底完成了多少工作：

# **总结** #

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

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

![这里写图片描述][SouthEast]

[https_code.tutsplus.com_articles_data-structures-with-javascript-singly-linked-list-and-doubly-linked-list_cms-23393]: https://code.tutsplus.com/articles/data-structures-with-javascript-singly-linked-list-and-doubly-linked-list--cms-23393
[data-structures-4-of-4.jpg]: https://cms-assets.tutsplus.com/uploads/users/423/posts/23393/final_image/data-structures-4-of-4.jpg
[SouthEast]: /images/20220611/205ba8999aa24b0b8f68bc0788f809e6.png