树形数据结构上下反转

Question

自下向上的多条树形结构数据，反转合并成一条或多条自上向下树形结构

已知多个数据的id，得出所有的上级，之后再反转

原始数据 规则：每条数据的pid是唯一的

{id:1,pid:0},
{id:2,pid:1},
{id:3,pid:2},
{id:4,pid:3},
{id:5,pid:3},
{id:6,pid:2},
{id:7,pid:1},

---

已知id：3，7.需要得到的结果：

    0
    |
    1
   / \
  2   7
 /
3

思路以及原理

从id:3,7获得自下向上的树形结构:

3->2->1->0
7->1->0

之后再反转成上面自上向下的数据结构:

[
    {
        id:1,
        pid:0,
        children:[
            {
                id:2,
                pid:1,
                children:[
                    {
                        {id:3,pid:2}
                    }
                ]
            },
            {
                id:7,
                pid:1
            }
        ]
    }
]

---

那么这个过程用代码编程怎么实现？请求各位大佬帮忙看看...

Answer 1

function Node()
{
}
Node.prototype.id   = null;
Node.prototype.prev = null;
Node.prototype.next = null;
Node.prototype.filter = function($mapFilter){

    let i;
    let arr, arrNext = [];
    for(i=0; i<this.next.length; i++)
    {
        arr = this.next[i].filter($mapFilter);

        if(arr !== null)
            arrNext.push(arr);
    }

    if(arrNext.length <= 0 && (this.id in $mapFilter) === false)
        return null;

    return {
        id : this.id
        ,pid : (this.prev === null)?Tree.ROOT_ID:this.prev.id
        ,children : arrNext
    };
};

function Tree()
{
    this.mapRoot = [];
    this.mapNode = [];
}
Tree.ROOT_ID = 0;
Tree.prototype.mapRoot = null;
Tree.prototype.mapNode = null;
Tree.prototype.add = function($ndi){

    let nodeThis, nodePrev;

    if($ndi.id in this.mapNode === false)
    {
        nodeThis = new Node();
        nodeThis.id = $ndi.id;
        nodeThis.prev = null;
        nodeThis.next = [];

        this.mapNode[$ndi.id] = nodeThis;
    }
    else
        nodeThis = this.mapNode[$ndi.id];

    nodePrev = null;
    if($ndi.pid !== Tree.ROOT_ID)
    {
        if($ndi.pid in this.mapNode === false)
        {
            nodePrev = new Node();
            nodePrev.id = $ndi.pid;
            nodePrev.prev = null;
            nodePrev.next = [];

            this.mapNode[$ndi.pid] = nodePrev;
        }
        else
            nodePrev = this.mapNode[$ndi.pid];

        nodePrev.next.push(nodeThis);
    }

    nodeThis.prev = nodePrev;

    if(nodePrev !== null && nodePrev.id in this.mapRoot === false && nodePrev.prev === null)
        this.mapRoot[nodePrev.id] = nodePrev;

    if(nodeThis.id in this.mapRoot === true && nodeThis.prev !== null)
        delete this.mapRoot[nodeThis.id];
};
Tree.prototype.filter = function($arrFilter){
    let mapFilter = {};
    for(i=0; i<$arrFilter.length; i++)
        mapFilter[$arrFilter[i]] = $arrFilter[i];

    let data = [];
    let id;
    for(id in this.mapRoot)
    {
        if(this.mapRoot.hasOwnProperty(id) === false)
            continue;

        data.push(this.mapRoot[id].filter(mapFilter));
    }

    return data;
};

let arrNode = [
    { id: 4, pid: 3 },
    { id: 3, pid: 2 },
    { id: 1, pid: 0 },
    { id: 2, pid: 1 },
    { id: 5, pid: 3 },
    { id: 6, pid: 2 },
    { id: 7, pid: 1 },
    { id: 8, pid: 10 },
    { id: 9, pid: 8 },
    { id: 10, pid: 11 },
];

let i;
let tree = new Tree();
// 一次处理 生成树结构 并且 找到所有根节点
for(i=0; i<arrNode.length; i++)
    tree.add(arrNode[i]);
// 有了树结构，用代码可以方便的遍历和过滤数据
let data = tree.filter([3,7,9]);

console.log(JSON.stringify(data, null, '  '));

Answer 2

let all = [
    { id: 4, pid: 3 },
    { id: 3, pid: 2 },
    { id: 1, pid: 0 },
    { id: 2, pid: 1 },
    { id: 5, pid: 3 },
    { id: 6, pid: 2 },
    { id: 7, pid: 1 },
    { id: 8, pid: 10 },
    { id: 9, pid: 8 },
    { id: 10, pid: 11 },
]
// 根据id获取所对应的对象
let getPid = id => {
    let parent = {}
    all.forEach(obj => {
        if (obj.id == id) {
            parent = obj
        }
    })
    return parent
}
// 递归获取不重复的pid
let getParents = (id, parents = []) => {
    if (!id) {
        return parents
    }
    if (parents.indexOf(id) < 0) {
        parents.push(id)
    }
    let pid = getPid(id).pid
    if (parents.indexOf(pid) > -1) {
        return parents
    } else if (pid == 0) {
        // parents.push(id)
        return parents
    } else {
        return getParents(pid, parents)
    }
}

let ids = [3, 7, 9]
// 获取包含自己的所有上级id
let parents = []
ids.forEach(id => {
    parents = getParents(id, parents)
})
console.log(parents)
// [ 3, 2, 1, 7, 9, 8, 10, 11 ]

// 递归处理hash key
rec = (id, hash) => {
    let obj = hash[id]
    if (obj.pid in hash) {
        if (!('children' in hash[obj.pid])) {
            hash[obj.pid]['children'] = {}
        }
        hash[obj.pid]['children'][obj.id] = JSON.parse(JSON.stringify(obj))
        return rec(obj.pid, hash)
    } else {
        return hash
    }
}
// 把parents id处理成自上向下的树结构
let hash = {}
all.forEach(obj => {
    let id = obj.id
    if (parents.indexOf(id) > -1) {
        hash[id] = JSON.parse(JSON.stringify(obj))
    }
})
let keys = Object.keys(hash)
keys.forEach(key => {
    hash = rec(key, hash)
})
let tree = {}
keys.forEach(key => {
    if (!(hash[key].pid in hash)) {
        tree[key] = hash[key]
    }
})
console.log(tree)

得到的结果

{
    "1": {
        "id": 1,
        "pid": 0,
        "children": {
            "2": {
                "id": 2,
                "pid": 1,
                "children": {
                    "3": {
                        "id": 3,
                        "pid": 2
                    }
                }
            },
            "7": {
                "id": 7,
                "pid": 1
            }
        }
    },
    "10": {
        "id": 10,
        "pid": 11,
        "children": {
            "8": {
                "id": 8,
                "pid": 10,
                "children": {
                    "9": {
                        "id": 9,
                        "pid": 8
                    }
                }
            }
        }
    }
}

Answer 3

其实给定的数据很适合建立节点树，每个不同的id都是一个节点，代码如下

// 1.得到数据源副本
nda = arr.map(v => {
    return { ...v }
})
// 2.建立父子节点关系链
nda.forEach(v => {
    // 找出当前节点的子节点
    v.children = nda.filter(child => child.pid == v.id)
    // 当前节点为叶子，裁剪之
    v.children == 0 && delete v.children
});

寻找根节点，得到整棵树形打印

let root = nda.find(item => item.id == 1)
console.log(JSON.stringify(root, null, 2))

效果图

{
  "id": 1,
  "pid": 0,
  "children": [
    {
      "id": 2,
      "pid": 1,
      "children": [
        {
          "id": 3,
          "pid": 2,
          "children": [
            {
              "id": 4,
              "pid": 3
            },
            {
              "id": 5,
              "pid": 3
            }
          ]
        },
        {
          "id": 6,
          "pid": 2
        }
      ]
    },
    {
      "id": 7,
      "pid": 1
    }
  ]
}

相较过滤id，先去枝为叶子节点，然后再去同父的非指定id的兄弟节点，需要递归，如下

function filterTree(nd, ids) {
    // 1.裁剪过滤id指向的节点 使其为叶子节点
    if (ids.includes(nd.id)) {
        nd.children && delete nd.children
    }
    if (nd.children) {
        for (let i = nd.children.length - 1; i >= 0; i--) {
            const element = nd.children[i];
            // 2.回调之前需要先判断是否有下级
            if (element.children) {
                // 3. 移动指针进入下一层
                filterTree(element, ids)
            } else {
                // 4.裁剪同父兄弟节点数据
                if (!(ids.includes(element.id))) {
                    nd.children.splice(i, 1)
                }
            }
        }
    }
    return
}

最终过滤会如你所愿，测试如下

filterTree(root, [3, 7])
console.log(JSON.stringify(root, null, 2))

{
  "id": 1,
  "pid": 0,
  "children": [
    {
      "id": 2,
      "pid": 1,
      "children": [
        {
          "id": 3,
          "pid": 2
        }
      ]
    },
    {
      "id": 7,
      "pid": 1
    }
  ]
}