Js遍历多叉树

今天在工作上有个需求是把后台数据库的菜单按照层级结构整理成想要的数据。父子关系在数据库中是用parentid来维系的,但是在实际页面展示中需要由高到底进行展示,也就是说需要把数据变成由children属性来保存子数据的模式,这样就涉及到了数据存储,以及根据父子关系进行数据更新插入,涉及到本文要记录的一个东西:遍历多叉树。

最重要的是了解思想,编程语言都是无所谓的,这里因为是前端工作所以用了JavaScript

思路:新建一个数组,将没有父级数据的菜单(如果有需要,则排序)直接推进数组,将有父级数据的菜单先查找父级数据,然后插入到父级数据的children属性中。

实现:因为不能保证数据是按照先父级数据进入数组,然后是子数据进入数组的顺序进行,所以这个过程需用了递归来实现。(可能还会有非递归方法,再想)

实现过程中的难点:查找已经加入数组的菜单里有没有当前菜单的父级菜单,但是因为菜单的父级菜单不一定是哪一级的菜单,所以涉及到了一个多叉树的遍历问题。

多叉树的遍历,有几个方法:

1.递归方法

思路:从根数据开始不断的遍历,所有数据的子数据,直到没有子数据或者找到符合条件的数据。

function getMenu(menus, code) {
    if (!menus || menus.length == 0) reutrn;
    for (let i = 0, len = menus.length; i < len; i++) {
        if (menus[i].code == code) {
            return menus[i];
        }
        if (menus[i].children && menus[i].children.length > 0) {
            getMenu(menus[i].children, code)
        }
    }
}

2. 非递归方法

非递归方法分为深度优先遍历与广度优先遍历,深度优先遍历就是先抓住一个树杈就遍历到叶子节点,然后再遍历下一个树杈;广度优先遍历就是先把相同层级的东西全部找到了,然后再找下一层的数据。

2.1 广度优先遍历

直接贴代码吧:

function getMenu(menus, code) {
    let array = [];
    for (let i = 0, len = menus.length; i < len; i++) {
        array.push(menus[i]);
    }
    let item = null;
    while (array.length > 0) {
        item = array.shift();
        if (item.code == code) {
            return item;
        }
        if (item.children && item.children.length > 0) {
            //这里把下一层的数据放到了被遍历的数组的后面,所以先遍历相同层再遍历下一层
            array = array.concat(item.children);
        }
    }
}
2.2 深度优先遍历
function getMenu(menus, code) {
    let array = [];
    for (let i = 0, len = menus.length; i < len; i++) {
        array.push(menus[i]);
    }
    let item = null;
    while (array.length > 0) {
        item = array.shift();
        if (item.code == code) {
            return item;
        }
        if (item.children && item.children.length > 0) {
            //这里把下一层的数据放到了被遍历的数组的前面,所以先遍历固定树杈的数据知道叶子节点没有下层数据为止
            array = item.children.concat(array);
        }
    }
}

感觉代码上应该比较容易理解,不多做解释,如果不是很好理解可以做个menus的简单数据,运行代码进行测试。

暂时没有二叉树的问题,也找了篇文章,有想看的可以过去看一下二叉树遍历

相关文章

发表新评论