字符串数组转为树形结构

基于路径串，分类目录串，以及数据库查询记录源，分别用js面向对象，函数，及过程的方式构建树形数据结构

题面

写一个算法实现字符串数组按照一定格式转为树形结构

const arr = [
  'root/lufei.jpg',
  'root/font/VarelaRound.ttf',
  'root/font/SourceSansPro.ttf',
  'root/img/avator.jpg',
  'root/img/favicon.jpg',
  'root/img/bg5.jpg',
  'root/img/bg4.jpg',
  'root/img/upload/a.png',
  'root/img/nt/mvvm.png',
  'root/img/nt/android.png',
  'root/img/nt/upload.png',
  'root/img/nt/js.png',
  'root/img/mvvm/a.png',
];

转为类似如下树形

      "name": "root",
      "children": [
        {
          "name": "lufei.jpg"
        },
        {
          "name": "font",
          "children": [
            {
              "name": "VarelaRound.ttf"
            },
            {
              "name": "SourceSansPro.ttf"
            }
          ]
        },
        ...

思路

以/分割，每段示为一个节点，节点有两个属性，其中children 是节点类型的数组，其节点数据结构描述如下

type Node {
    name string
    children []*Node
}

显然还需要一个节点查找方法，子节点递归插入

类方案

用js原型+构造函数实现代码

function O() {
  this.name = 'Trie'
  this.children = []
}
// 绑定构造器
O.prototype.constructor = O

// 共享方法
// 第一个匹配成功节点，用于插入
O.prototype.matchChild = function (part) {
  for (let i = 0; i < this.children.length; i++) {
    if (this.children[i].name == part) {
      return this.children[i]
    }
  }
  return null
}

/**
 * 插入节点
 * @param {[]string} parts 
 * @param {Number} height 
 */
O.prototype.insert = function (parts, height) {
  if (parts.length == height) {
    // 清除子节点
    delete this.children
    // 必须有退出机制
    return
  }
  part = parts[height]
  // 查找第一个同级同名节点
  child = this.matchChild(part)
  if (child == null) {
    // 新建子节点
    child = new O()
    child.name = part
    this.children.push(child)
  }
  // 进入下一层继续搜索插入
  child.insert(parts, height + 1)
}

测试

o = new O()
arr.map(v => {
  t = v.split('/')
  o.insert(t, 0)
})
console.log(JSON.stringify(o,null,2))

效果

{
  "name": "Trie",
  "children": [
    {
      "name": "root",
      "children": [
        {
          "name": "lufei.jpg"
        },
        {
          "name": "font",
          "children": [
            {
              "name": "VarelaRound.ttf"
            },
            {
              "name": "SourceSansPro.ttf"
            }
          ]
        },
        {
          "name": "img",
          "children": [
            {
              "name": "avator.jpg"
            },
            {
              "name": "favicon.jpg"
            },
            {
              "name": "bg5.jpg"
            },
            {
              "name": "bg4.jpg"
            },
            {
              "name": "upload",
              "children": [
                {
                  "name": "a.png"
                }
              ]
            },
            {
              "name": "nt",
              "children": [
                {
                  "name": "mvvm.png"
                },
                {
                  "name": "android.png"
                },
                {
                  "name": "upload.png"
                },
                {
                  "name": "js.png"
                }
              ]
            }
          ]
        }
      ]
    },
    {
      "name": "abc",
      "children": [
        {
          "name": "img",
          "children": [
            {
              "name": "mvvm",
              "children": [
                {
                  "name": "a.png"
                }
              ]
            }
          ]
        }
      ]
    }
  ]
}

函数方案

已知如下数组

let srcList = ['动物-昆虫-蚂蚁', '动物-昆虫', '植物-草-绿色', '植物-花-红色','植物-花-黄色']

达成结构

[
  {
    "name": "动物",
    "children": [
      {
        "name": "昆虫",
        "children": [
          {
            "name": "蚂蚁"
          }
        ]
      }
    ]
  },
  {
    "name": "植物",
    "children": [
      {
        "name": "草",
        "children": [
          {
            "name": "绿色"
          }
        ]
      },
      {
        "name": "花",
        "children": [
          {
            "name": "红色"
          },
          {
            "name": "黄色"
          }
        ]
      }
    ]
  }
]

解法详情

function listToTree(srcList) {
  // 1.记录根位置
  let destList = []
  srcList.forEach(path => {
    // 2.待匹配项
    let pathList = path.split('-')
    // 3.将移动指针重置顶层，确保每次从根检索匹配（必须！！！）
    let levelList = destList
    // 4.遍历待询节点
    for (let name of pathList) {
      // 5.同层同名节点查找匹配
      let obj = levelList.find(item => item.name == name)
      // 6.若不存在则建立该节点
      if (!obj) {
        obj = { name, children: [] }
        levelList.push(obj)
        // 7.若当前被增节点是叶子节点，则裁剪该节点子节点属性
        if (name == pathList[pathList.length - 1]) {
          delete obj.children
        }
      }
      // 8.已有则进入下一层，继续寻找
      levelList = obj.children
    }
  })
  return destList
}

测试

let srcList = ['动物-昆虫-蚂蚁', '动物-昆虫', '植物-草-绿色', '植物-花-红色','植物-花-黄色']
let result = listToTree(srcList)
console.log(JSON.stringify(result, null, 2))

数据库变树形

通常从数据库查询的树形条源如下

arr = [
  { 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 }
]

要转的树形结构

办法简单，粗暴将源数据转为节点数组，然后子节点填充建树，裁剪叶子

// 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
});

打印id为1的数据树形结构

let obj = nda.find(item => item.id == 1)
console.log(JSON.stringify(obj, 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
    }
  ]
}

小结

最后一种看起来简单，实际上取巧了，数据库取的条目通常是确定，所以可先将所有节点构建出来，后两两建立当前节点与上下级之关系。事实上，惯用法是递归创建。递归创建通常要求有出路，终止递归条件。而数据记录，又恰巧只记录一个节点的情况。

本作品采用《CC 协议》，转载必须注明作者和本文链接