字符串数组转为树形结构

基于路径串,分类目录串,以及数据库查询记录源,分别用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.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 协议》,转载必须注明作者和本文链接
pardon110
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

请勿发布不友善或者负能量的内容。与人为善,比聪明更重要!
开发者 @ 社科大
文章
102
粉丝
12
喜欢
82
收藏
38
排名:102
访问:4.6 万
私信
所有博文