欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

多叉树结构的数据,parent表示法转成children表示法

程序员文章站 2022-03-06 10:26:14
最近碰到的问题,有个数组,数组元素是对象,该对象的结构就如树的parent表示法的节点一样。形象点讲就是该数组存放了树的所有“叶子节点”,并且叶子节点内存有父节点,一直到根节点为止,就如存了一条从叶子节点到根节点路径。 现在有要求是将这个数组转成一个children表示法的对象,即从根节点开始,每个 ......

最近碰到的问题,有个数组,数组元素是对象,该对象的结构就如树的parent表示法的节点一样。形象点讲就是该数组存放了树的所有“叶子节点”,并且叶子节点内存有父节点,一直到根节点为止,就如存了一条从叶子节点到根节点路径。

现在有要求是将这个数组转成一个children表示法的对象,即从根节点开始,每个节点存有其子节点数组。转化效果如下(节点必须有个唯一标识符,以下id就是,并且转化前后其他属性保持不变,这里为了显示简洁没有加入其他属性。):

多叉树结构的数据,parent表示法转成children表示法

多叉树结构的数据,parent表示法转成children表示法

核心思想是使用递归,新建唯一的根节点开始,不断生长出子节点。并再插入子节点时判断子节点是否存在,存在的话不插入,反之插入。注意所有将子节点插入到父节点children数组的操作,都必须保证被插入父节点已经是“新建的唯一根节点”下的,这样才能实现不断生长的效果。以下通过递归返回父节点的方式确保,返回前是一次插入操作,这时已经判断出“插入新节点”和“未插入新节点”,根据这两种情况,递归返回值就可以判断,如果插入新节点则返回该新节点作为父节点,反之返回已存在于“唯一根节点上的”的“该节点”作为父节点。

 1 var treeconverter = {
 2         result: null, //转化后的结果,是根节点,所有节点都是从根节点长出来的
 3         attributename: 'id', //节点唯一标识符
 4         needfind: true, //是否查询节点在result中已经存在,为了优化效率
 5         transform: function (node) { //转化递归函数,参数:一个待插入节点
 6             if (node.parent != null) { //该节点有父节点
 7                 var newnode = this.transform(node.parent); //递归进入,返回值为一个节点,用作父节点,该父节点必然存在于result中,这点由下面的算法可以控制
 8                 if (this.needfind) {
 9                     for (var i = 0; i < newnode.children.length; i++) { //查找要插入的node子节点是否在newnode这个父节点中存在
10                         if (newnode.children[i][this.attributename] === node[this.attributename]) {
11                             return newnode.children[i]; //存在的话直接返回newnode父节点内的该子节点,该子节点必然存在于result中,作为返回值它将被用作上级递归的newnode,因此newnode必然存在于result中
12                         }
13                     }
14                 }
15                 this.needfind = false; //不存在的话,关闭之后递归的循环判断,因为待插入node节点不存在于result中,故而它的子节点一定不存在于result中,不用再循环判断
16                 delete node.parent; //删除该节点的parent属性,如果有的话
17                 node.children = []; //因为确定是要新插入的节点,没有children:[]属性,故给该节点增加children:[]属性
18                 newnode.children.push(node); //将该node节点push进newnode的子节点数组中
19                 return node; //return该新插入节点,作为递归返回值给上层,用作newnode父节点,node存在于result中故newnode存在于result中
20             } else if (node.parent == null) { //该叶节点没有父节点,即为根节点
21                 delete node.parent; //删除该节点的parent属性,如果有的话
22                 if (this.result == null) { //根节点不存在
23                     node.children = []; //给该节点增加children:[]属性
24                     return this.result = node; //该节点赋给result,并return根节点,作为返回值它将被用作上级递归的newnode,因此newnode必然存在于result中
25                 } else {
26                     return this.result // 直接return根节点,作为返回值它将被用作上级递归的newnode,因此newnode必然存在于result中
27                 }
28             }
29         },
30         getsingle: function (node, attributename) { //传入单个叶子节点,attributename作为节点唯一标识符属性,返回单个转化结果
31             this.result = null; //重置根节点
32             this.needfind = true; //重置开启节点是否已存在判断
33             this.attributename = attributename == null ? 'id' : attributename; //唯一标识符默认为“id”
34             this.transform(json.parse(json.stringify(node))); //复制出一个新的节点对象作为参数,保证不改变原有数据
35             return this.result; //返回根节点
36         },
37         getwhole: function (nodes, attributename) { //传入整个叶子节点数组,attributename作为节点唯一标识符属性,返回整个转化结果
38             this.result = null; //重置根节点
39             this.attributename = attributename == null ? 'id' : attributename; //唯一标识符默认为“id”
40             nodes = json.parse(json.stringify(nodes)); //复制出一个新的节点对象作为参数,保证不改变原有数据
41             nodes.foreach(item => { //循环调用转化方法
42                 this.needfind = true; //重置开启节点是否已存在判断,保证不插入重复节点
43                 this.transform(item);
44             })
45             return this.result; //返回根节点
46         }
47     }
48     var result = treeconverter.getwhole(nodes); //调用

 

模拟数据:

var nodes= [
    {
        id: 2,
        parent: {
            id: 5,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 1,
        parent: {
            id: 5,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 4,
        parent: {
            id: 7,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 14,
        parent: {
            id: 13,
            parent: {
                id: 9,
                parent: {
                    id: 8,
                    parent: {
                        id: 7,
                        parent: {
                            id: 3,
                            parent: null
                        }
                    }
                }
            }
        }
    },
    {
        id: 6,
        parent: {
            id: 7,
            parent: {
                id: 3,
                parent: null
            }
        }
    },
    {
        id: 10,
        parent: {
            id: 8,
            parent: {
                id: 7,
                parent: {
                    id: 3,
                    parent: null
                }
            }
        }
    }
]