JavaScript数据结构：树

LeoHsiun 发布于2019-08-20 17:50 / 1181人阅读

摘要：第二步自终止，第三步自调用，第四步回调函数会重复进行，直到我们遍历到树的所有节点。执行回调函数，传入赋值为第二层第二个子节点。

</>复制代码 
本文译自Cho S. Kim的文章：Data Structures With JavaScript: Tree

“树”，是web开发中最常用的数据结构之一。这句话对开发者和用户来讲，都适用：开发人员通过HTML创造了一个DOM，用户则通过DOM消费网络信息。

进一步讲，您正在阅读的本文也是以树的形式在浏览器中渲染的。文章中的段落由

标签中的文字所代表；

标签嵌套在元素中，而元素则是的子元素。

数据的嵌套类似一个家谱：元素是一个爹爹，元素是一个孩儿，

元素则是元素的孩儿。如果你感觉这种类比容易理解，那么在接下来实现一棵树的过程中，更多的类比对你来说应该也不成问题。

在本文中，我们将创建一颗有两种遍历方式的树：Depth-First-Search(DFS)深度优先搜索，和Breadth-First-Search(BFS)宽度优先搜索（遍历是指访问树的每一个节点）。这两种遍历方式各自强调了对一颗树操作的不同姿势；而且他们用到了我们之前提过的（ 没翻，去找原文 ）数据结构：DFS用到了栈，BFS用到了队列。

树（DFS 和 BFS）

树，是一种使用节点来模拟分等级（层次）数据的数据结构。节点存储数据，并指向其他节点（每个节点都存储有自身数据，和指向其它节点的指针）。部分读者可能对节点、指针等术语不太熟悉，所以我们这里做一个类比：把一棵树比作一个组织结构。这个组织结构有一个最高负责人（根节点），比如说总经理。紧跟着就是在其之下的职位，比如说一个副总。

我们用一个从老总指向副总的箭头来表示这种关系。老总 → 副总。一个职位（老总），就是一个节点；老总和副总之间的关系（箭头），就是指针。在组织结构图中创建更多的类似关系，只需要重复上面的步骤，一个节点指向另外一个节点。

在概念上，我希望节点和指针能够讲得通。在实践上，我们再可以举一个DOM的栗子。一个DOM的根节点就是，它指向了和。然后重复下去生成一颗DOM树。

这么搞最赞的一点就是它具有嵌套节点的能力：一个

节点，每个
也可以有兄弟

节点。（作者发出了奇怪的赞美）

对树进行操作

树跟节点可以用两个多带带的构造器来描述：Node和Tree。

Node

data存储一个值

parent指向这个节点的父节点

children指向表中的下一个节点（这个可能有一堆，那么可能是一个数组）

Tree

_root指向这个树的根节点

traverseDF(callback)使用DFS遍历树的节点

traverseBF(callback)使用BFS遍历树的节点

contains(data,traversal)在树里面搜索一个节点

add(data,toData,traverse)向树添加一个节点

remove(child,parent)删除树的一个节点

实现一棵树

下面开始写代码！

节点Node的属性

</>复制代码 
function Node(data) {
    this.data = data;
    this.parent = null;
    this.children = [];
}

每个Node的实例都包含三个属性，data，parent和children。第一个属性保存跟这个节点有关的数据，比如“村长”。第二个属性指向一个节点（在js中，就是等于号，比如this.parent = someOtherNode 这个就实现指针了好吧。什么值传递就不细展开了。其他算法中的指针实现也类似。）。

</>复制代码 
function Tree(data) {
    var node = new Node(data);
    this._root = node;
}

Tree包含两行代码，第一行创建了一个Node的实例node，第二行把这个node赋值给了this._root。就是对一个树进行了初始化，给了它一个根节点。
Tree和Node的定义只需要很少的代码，但是这些代码已经足够我们模拟一个有层次的数据结构。为了说明这一点，我们可以通过用一点测试数据来创建Tree的实例（间接也创建了Node的实例）：

</>复制代码 
var tree = new Tree("CEO");
tree._root;
// 返回{data: "CEO", parent: null, children: []}

有parent和children的存在，我们可以把节点添加为_root的子节点，同时把这些子节点的父节点赋值为_root。

树的方法

接下来，我们给树添加下面这5个方法：

Tree

traverseDF(callback)

traverseBF(callback)

contains(data,traversal)

add(child,parent)

remove(node,parent)

这些方法都需要对树进行遍历，我们首先来实现遍历方法（们）。

第一个: traverseDF(callback)

对树进行深度优先遍历：

</>复制代码 
Tree.prototype.traverseDF = function(callback) {
    // 一个递归，立即执行函数
    (function recurse(currentNode) {
        // 第二步
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            // 第三步
            recurse(currentNode.children[i]);
        }
        // 第四步
        callback(currentNode);
        // 首先执行
    })(this._root);
};

traverseDF(callback)有一个callback参数，顾名思义，callback是一个稍后会在traverseDF(callback)内调用的函数。

traverseDF(callback)内包含了一个叫做recurse的函数。recurse的意思是递归，这是一个递归函数，用人话说就是这个函数会调用自己，然后（特定条件下）自动结束。注意上面代码注释中的第*步，我会用他们来描述一下recurse函数是怎么遍历到整棵树的：

首先执行： recurse，以树的根节点作为参数。此时，currentNode指向这个根节点。

第二步：进入到一个for循环，对currentNode（比如说根节点）的每一个子节点进行迭代，从第一个开始。

第三步：在for循环体内，调用recurse，传参currentNode的某一个子节点。具体哪一个子节点取决于for循环的迭代情况。

第四步：当currentNode没有更多的子节点，退出for循环，并调用在调用traverseDf(callback)时传递进来的callback函数。

第二步（自终止），第三步（自调用），第四步（回调函数） 会重复进行，直到我们遍历到树的所有节点。

完整的讲述递归需要一整面文章，这超出了本文的范围。读者可以用上面的traverseDF(callback)来实验（在浏览器里面打个断点看看是怎么执行的），来尝试理解它是怎么工作的。

下面这段例子用来说明一个树是如何被traverseDF(callback)遍历的。
首先我们创建一颗树用来遍历，下面这种方法并不好，但是可以起到说明的效果。理想的方式是使用后面在第四部分要实现的add(value)。

</>复制代码 
/*
建立一颗结构如下的树
one
├── two
│   ├── five
│   └── six
├── three
└── four
    └── seven
*/
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];

然后我们调用traverseDF(callback):

</>复制代码 
tree.traverseDF(function(node) {
    console.log(node.data)
});
/*
logs the following strings to the console(这个就不翻了)
"five"
"six"
"two"
"three"
"seven"
"four"
"one"
*/

第二个: traverseBF(callback)

这个方法用来进行宽度优先遍历。
深度优先和宽度优先的遍历顺序是不一样的，我们使用在traverseBF(callback)中用过的树来证明这一点：

</>复制代码 
/*
 tree
 one (depth: 0)
 ├── two (depth: 1)
 │   ├── five (depth: 2)
 │   └── six (depth: 2)
 ├── three (depth: 1)
 └── four (depth: 1)
     └── seven (depth: 2)
 */

然后传入相同的回调函数：

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

上面的log和树的结构已经说明了宽度优先遍历的模式。从根节点开始，然后向下一层，从左向右遍历所有这一层的节点。重复进行知道到达最底层。

现在我们有了概念，那么来实现代码：

</>复制代码 
Tree.prototype.traverseBF = function(callback) {
    var queue = new Queue();
    queue.enqueue(this._root);
    currentNode = queue.dequeue();
    while(currentNode){
        for (var i = 0, length = currentNode.children.length; i < length; i++) {
            queue.enqueue(currentNode.children[i]);
        }
        callback(currentNode);
        currentNode = queue.dequeue();
    }
};

traverseBF(callback)的定义包含了很多逻辑，作者在这里解释了一堆。我感觉对理解代码并没有帮助。
尝试解释一下，根节点算第一层：

从根节点开始，这个时候currentNode是根节点；

第一次while遍历currentNode的所有子节点，推进队列。（这个时候第二层已经遍历到了，并且会在while循环中依次执行，先进先出）

执行回调函数，传入currentNode；

currentNode赋值为第二层第一个子节点。

第二次while：对currentNode，第二层第一个子节点的所有子节点遍历，推入队列。注意这里是第三层的第一部分。

执行回调函数，传入currentNode；

currentNode赋值为第二层第二个子节点。

第三次while：对currentNode，第二层第二个子节点的所有子节点遍历，推入队列。注意这里是第三层的第二部分。

执行回调函数，传入currentNode；

currentNode赋值为第二层第三个子节点。

最后几次while

：这个时候已经没有下一层了，不会进入for循环，就是依次把队列里剩的节点传到回调函数里面执行就对了。

这样就很清楚了。

第三个: contains(callback,traversal)

这个方法用来在树里搜索一个特定的值。为了使用我们之前定义的两种遍历方式，contains(callback,traversal)可以接受两个参数，要找的值，和要进行的遍历方式。

</>复制代码 
Tree.prototype.contains = function(callback, traversal) {
    traversal.call(this, callback);
};

call方法的第一个参数把traversal绑定在调用contains(callback,traversal)的那棵树上面，第二个参数是一个在每个节点上面调用的函数。
下面这个函数大家自己理解，我感觉原作者解释反了。

</>复制代码 
// 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)

现在我们会找了，再来个添加的方法吧。

</>复制代码 
Tree.prototype.add = function(data, toData, traversal) {
    //实例一个node
    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.");
    }
};

注释就很清楚了。

</>复制代码 
var tree = new Tree("CEO");
tree.add("VP of Happiness", "CEO", tree.traverseBF);
/*
our tree
"CEO"
└── "VP of Happiness"
*/

</>复制代码 
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"
 */

第五个: remove(data, fromData, traversal)

类似的，删除方法：

</>复制代码 
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;
    //遍历某个data爹的娃，如果全等，那么返回这个娃的排行，否则返回的index等于undefined
    for (var i = 0; i < arr.length; i++) {
        if (arr[i].data === data) {
            index = i;
        }
    }
    return index;
}

在全文的最后，作者放出了全家福：

</>复制代码 
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;
}

GPU云服务器云服务器树结构树结构数据存储数据库树 JSON树结构

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/83910.html

Javascript中的树结构

摘要：前沿前端中设计数据结构的方面不多，最常用的就是对树结构的一些操作。毕竟，就是天然的树结构。递归输出非递归输出业务场景前端中的树操作，经常是生成特定的树结构。前沿前端中设计数据结构的方面不多，最常用的就是对树结构的一些操作。从某种意义上来说，前端工作本身就是和树结构打交道的一个工作方向。毕竟，DOM就是天然的树结构。所以如何能够良好地对树结构进行操作，是前端工程师不可或缺的一...

_Dreams 2019-08-23 18:10 评论0 收藏0
学习javascript数据结构(四)——树

摘要：原文博客地址学习数据结构四树知乎专栏简书专题前端进击者知乎前端进击者简书博主博客地址的个人博客人之所能，不能兼备，弃其所短，取其所长。通常子树被称作左子树和右子树。敬请期待数据结构篇最后一篇文章学习数据结构五图参考文章树数据结构二叉树前言总括：本文讲解了数据结构中的[树]的概念，尽可能通俗易懂的解释树这种数据结构的概念，使用javascript实现了树，如有纰漏，欢迎批评指正。 ...

Dean 2019-08-20 13:47 评论0 收藏0
学习JavaScript数据结构与算法（四）：二叉搜索树

摘要：像刚才的这幅图，就是二叉搜索树。而我们本文要学习的内容，就是如何写一个二叉搜索树。但在二叉搜索树中，我们把节点成为键，这是术语。前端路漫漫，且行且歌的前端乐园原文链接寒假前端学习学习数据结构与算法四二叉搜索树本系列的第一篇文章: 学习JavaScript数据结构与算法（一），栈与队列第二篇文章：学习JavaScript数据结构与算法（二）：链表第三篇文章：学习JavaScript数据...

ingood 2019-08-19 17:26 评论0 收藏0
JavaScript是如何工作的:渲染引擎和优化其性能的技巧

摘要：渲染树的布局创建渲染器并将其添加到树中时，它没有位置和大小，计算这些值称为布局。根渲染器的位置为，其尺寸与浏览器窗口的可见部分即的大小相同。渲染器使其在屏幕上的矩形无效，这会导致操作系统将其视为需要重新绘制并生成绘事件的区域。这是专门探索 JavaScript 及其所构建的组件的系列文章的第11篇。想阅读更多优质文章请猛戳GitHub博客,一年百来篇优质文章等着你！如果你错过了前...

big_cat 2019-08-23 14:40 评论0 收藏0
数据结构与算法JavaScript （不定时更新）

摘要：每个列表中的数据项称为元素。栈被称为一种后入先出，的数据结构。散列使用的数据结构叫做散列表。不包含任何成员的集合称为空集，全集则是包含一切可能成员的集合。因此二叉搜索树需要平衡，即左右子树高度要相近。楼楼非计算机专业，但是对计算机也还算喜欢。个人理解若有偏差，欢迎各位批评指正！对于数据结构和算法一直是我的薄弱环节，相信大多数前端工程师可能多少会有些这方面的弱点，加上数据结构和算法本...

levius 2019-08-26 11:40 评论0 收藏0