JS数据结构描述之广度遍历和深度遍历

printempw 发布于2019-08-20 15:35 / 1609人阅读

摘要：一数据模型二递归实现递归实现三非递归广度优先实现先将第一层节点放入栈如果该节点有子节点，继续添加进入栈底非递归广度优先实现四非递归深度优先实现先将第一层节点放入栈如果该节点有子节点，继续添加进入栈顶非递归深度优先实现

文章来源：http://www.html-js.com/articl...

简单的遍历一个树形结构数据的几种方法、非递归方法效率最好。

一：数据模型:

(function (window, undefined) {
    var treeNodes = [
       {
            id: 1,
            name: "1",
            children: [
                 {
                      id: 11,
                      name: "11",
                      children: [
                           {
                                id: 111,
                                name: "111",
                                children:[]
                           },
                           {
                                id: 112,
                                name: "112"
                           }
                      ]
                 },
                 {
                      id: 12,
                      name: "12",
                      children: []
                 }
            ],
            users: []
       },
       {
            id: 2,
            name: "2",
            children: [
                {
                    id: 22,
                    name: "22",
                    children: []
                }
            ]
       }
    ];

二：递归实现

    var parseTreeJson = function(treeNodes){
      if (!treeNodes || !treeNodes.length) return;

       for (var i = 0, len = treeNodes.length; i < len; i++) {

            var childs = treeNodes[i].children;

            console.log(treeNodes[i].id);

            if(childs && childs.length > 0){
                 parseTreeJson(childs);
            }
       }
    };

    console.log("------------- 递归实现 ------------------");
    parseTreeJson(treeNodes);

三：非递归广度优先实现

var iterator1 = function (treeNodes) {
    if (!treeNodes || !treeNodes.length) return;

    var stack = [];

    //先将第一层节点放入栈
    for (var i = 0, len = treeNodes.length; i < len; i++) {
        stack.push(treeNodes[i]);
    }

    var item;

    while (stack.length) {
        item = stack.shift();

        console.log(item.id);

        //如果该节点有子节点，继续添加进入栈底
        if (item.children && item.children.length) {
            //len = item.children.length;

            // for (i = 0; i < len; i++) {
            //  stack.push(item.children[i]);
            // }

            stack = stack.concat(item.children);
        }
    }
};

console.log("------------- 非递归广度优先实现 ------------------");
iterator1(treeNodes);

四：非递归深度优先实现

 var iterator2 = function (treeNodes) {
        if (!treeNodes || !treeNodes.length) return;

        var stack = [];

        //先将第一层节点放入栈
        for (var i = 0, len = treeNodes.length; i < len; i++) {
            stack.push(treeNodes[i]);
        }

        var item;

        while (stack.length) {
            item = stack.shift();

            console.log(item.id);

            //如果该节点有子节点，继续添加进入栈顶
            if (item.children && item.children.length) {
                // len = item.children.length;

                // for (; len; len--) {
                //  stack.unshift(item.children[len - 1]);
                // }
                stack = item.children.concat(stack);
            }
        }
    };

    console.log("------------- 非递归深度优先实现 ------------------");
    iterator2(treeNodes);
})(window);

GPU云服务器云服务器广度遍历广度优先遍历 js 遍历数据图的深度遍历

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

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

JS算法之深度优先遍历(DFS)和广度优先遍历(BFS)

摘要：算法之深度优先遍历和广度优先遍历背景在开发页面的时候，我们有时候会遇到这种需求在页面某个节点中遍历，找到目标节点，我们正常做法是利用选择器，或者，但在本文，我们从算法的角度去查找节点，同时理解一下深度优先遍历和广度优先遍历的原理。 JS算法之深度优先遍历(DFS)和广度优先遍历(BFS) 背景在开发页面的时候，我们有时候会遇到这种需求：在页面某个dom节点中遍历，找到目标dom节点，...

roadtogeek 2019-08-23 16:33 评论0 收藏0
js 中二叉树的深度遍历与广度遍历(递归实现与非递归实现)

摘要：树中结点的最大层次称为树的深度或高度。二叉树有深度遍历和广度遍历，深度遍历有前序中序和后序三种遍历方法。二叉树的前序遍历可以用来显示目录结构等中序遍历可以实现表达式树，在编译器底层很有用后序遍历可以用来实现计算目录内的文件及其信息等。树的简介栈、队列、链表等数据结构，都是顺序数据结构。而树是非顺序数据结构。树型结构是一类非常重要的非线性结构。直观地，树型结构是以分支关系定义的层次结...

Yuanf 2019-08-23 11:38 评论0 收藏0
JS中的二叉树遍历

摘要：一个二叉树的例子广度优先遍历广度优先遍历是从二叉树的第一层根结点开始，自上至下逐层遍历在同一层中，按照从左到右的顺序对结点逐一访问。有的书里将二叉树的遍历只讲了上面三种递归遍历。二叉树是由根节点，左子树，右子树组成，左子树和友子树分别是一个二叉树。这篇文章主要在JS中实现二叉树的遍历。一个二叉树的例子 var tree = { value: 1, left: { ...

ghnor 2019-08-19 17:52 评论0 收藏0
实现深度遍历和广度遍历(递归与非递归版本)

摘要：先画个树，然后解释何为深度，何为广度第一层子集第二层子集第二层子集第三层，子集第三层第四层图就不画太复杂了，最高四层的结构，如果换成的形式的话可以理解成第一层第二层先画个树，然后解释何为深度，何为广度第一层子集 | ...

Betta 2019-08-26 10:09 评论0 收藏0
图的JS实现

摘要：图的实现如下采用邻接表结构实现。由于本次示例的是无向图，因此每个顶点都互相增加为邻接点。然而由于本次示例的图为无向图，会出现重复遍历的情况，例如顶点的邻接点有，的邻接点有。图的定义图就是由若干个顶点和边连接起来的一种结构。很多东西都可以用图来说明，例如人际关系，或者地图。其中图还分为有向图和无向图。如下就是有向图图的数据结构对于图这种关系，可以通过两种方式来存储。领接表将...

LeanCloud 2019-08-21 17:00 评论0 收藏0