js如何将树形结构数组对象变为二维数组？

Question

有个以下格式的省市区数组对象：

[
    {
        "name": "上海市",
        "child": [
            {
                "name": "市辖区",
                "child": [
                    {
                        "name": "黄浦区",
                        "child": null
                    },
                    {
                        "name": "卢湾区",
                        "child": null
                    },
                    {
                        "name": "徐汇区",
                        "child": null
                    },
                    {
                        "name": "长宁区",
                        "child": null
                    },
                    {
                        "name": "静安区",
                        "child": null
                    },
                    {
                        "name": "普陀区",
                        "child": null
                    },
                    {
                        "name": "闸北区",
                        "child": null
                    },
                    {
                        "name": "虹口区",
                        "child": null
                    },
                    {
                        "name": "杨浦区",
                        "child": null
                    },
                    {
                        "name": "闵行区",
                        "child": null
                    },
                    {
                        "name": "宝山区",
                        "child": null
                    },
                    {
                        "name": "嘉定区",
                        "child": null
                    },
                    {
                        "name": "浦东新区",
                        "child": null
                    },
                    {
                        "name": "金山区",
                        "child": null
                    },
                    {
                        "name": "松江区",
                        "child": null
                    },
                    {
                        "name": "青浦区",
                        "child": null
                    },
                    {
                        "name": "南汇区",
                        "child": null
                    },
                    {
                        "name": "奉贤区",
                        "child": null
                    }
                ]
            },
            {
                "name": "县",
                "child": [
                    {
                        "name": "崇明县",
                        "child": null
                    }
                ]
            }
        ]
    }
]

请问如何用Ts变为以下格式的二维数组？

[
['上海市', '市辖区', '黄浦区']
 ['上海市', '市辖区', '卢湾区']
['上海市', '市辖区', '徐汇区']
 ['上海市', '市辖区', '长宁区']
['上海市', '市辖区', '静安区']
 ['上海市', '市辖区', '普陀区']
 ['上海市', '市辖区', '闸北区']
 ['上海市', '市辖区', '虹口区']
 ['上海市', '市辖区', '杨浦区']
 ['上海市', '市辖区', '闵行区']
 ['上海市', '市辖区', '宝山区']
 ['上海市', '市辖区', '嘉定区']
 ['上海市', '市辖区', '浦东新区']
 ['上海市', '市辖区', '金山区']
 ['上海市', '市辖区', '松江区']
 ['上海市', '市辖区', '青浦区']
 ['上海市', '市辖区', '南汇区']
 ['上海市', '市辖区', '奉贤区']
 ['上海市', '县', '崇明县']
]

Answer 1

interface AddrItem {
  name: string;
  child: AddrItem[] | null;
}

function formatAddrData (data: AddrItem[]): string[][] {
  const result: string[][] = [];

  function traverse (addrList: AddrItem[], path: string[]): void {
    if (!addrList || addrList.length === 0) {
      return;
    }

    for (const item of addrList) {
      const newPath = [...path, item.name];
      if (!item.child || item.child.length === 0) {
        result.push(newPath);
      } else {
        traverse(item.child, newPath);
      }
    }
  }

  traverse(data, []);

  return result;
}

const addrData = [
  {
    "name": "上海市",
    "child": [
      {
        "name": "市辖区",
        "child": [
          {
            "name": "黄浦区",
            "child": null
          },
          {
            "name": "卢湾区",
            "child": null
          },
          {
            "name": "徐汇区",
            "child": null
          },
          {
            "name": "长宁区",
            "child": null
          },
          {
            "name": "静安区",
            "child": null
          },
          {
            "name": "普陀区",
            "child": null
          },
          {
            "name": "闸北区",
            "child": null
          },
          {
            "name": "虹口区",
            "child": null
          },
          {
            "name": "杨浦区",
            "child": null
          },
          {
            "name": "闵行区",
            "child": null
          },
          {
            "name": "宝山区",
            "child": null
          },
          {
            "name": "嘉定区",
            "child": null
          },
          {
            "name": "浦东新区",
            "child": null
          },
          {
            "name": "金山区",
            "child": null
          },
          {
            "name": "松江区",
            "child": null
          },
          {
            "name": "青浦区",
            "child": null
          },
          {
            "name": "南汇区",
            "child": null
          },
          {
            "name": "奉贤区",
            "child": null
          }
        ]
      },
      {
        "name": "县",
        "child": [
          {
            "name": "崇明县",
            "child": null
          }
        ]
      }
    ]
  }
]
console.log(formatAddrData(addrData));

Answer 2

有两种递归方式，一种是最外层等待内部递归的结果，然后进行拼接；另一种是把当前的name传递给内层，直到最内层child为null，然后拼接路径。

如果是 ts 的话，我们先声明一个树形结构的类型：

interface TreeItem {
  name: string;
  child?: TreeItem[];
}

外层等待内层的递归结果

const transform = (tree: TreeItem[]) => {
  let result: string[][] = [];

  tree.forEach((item) => {
    if (item.child) {
      // 得到子元素的数组
      const childList = transform(item.child);

      result = result.concat(
        childList.map((child) => {
          // 对每个子元素，都拼接上当前元素的name
          return [item.name].concat(child);
        })
      );
    } else {
      result.push([item.name]);
    }
  });

  return result;
};

这种方式比较绕。

外层元素递归传给内层

const transform = (tree: TreeItem[]) => {
  const result: string[][] = []; // 声明一个全局变量，用来存储递归结束时的数据

  const find = (list: TreeItem[], parents: string[] = []) => {
    list.forEach((item) => {
      const path: string[] = parents.concat(item.name);
      if (item.child) {
        find(item.child, path);
      } else {
        result.push(path);
      }
    });
  };
  find(tree);

  return result;
};

Answer 3

const paths = (items, pathKey, childrenKey) => {    
    const _path = (items, result, parents) => {
        if(items && items.length) {
            items.forEach(item => 
                    _path(item[childrenKey], result, [...parents, item[pathKey]]));
            return;
        }
        if(parents.length) {
            result.push(parents);
        }      
    };
    const result = [];
    _path(items, result, []);
    return result;
}


// const items = [...];

// const result = paths(items, 'name', 'child');
// console.log(result);

Answer 4

function tree2arr(tree) {
    var ret = [];
    var depth = [];
    var values = [];
    var stack = tree.slice();
    while (stack.length) {
        var top = stack.pop();
        values.push(top.name);
        if (top.child) {
            depth.push(top.child.length);
            stack.push.apply(stack, top.child);
        } else {
            ret.unshift(values.slice());
            do {
                values.pop();
            } while (!--depth[depth.length - 1]);
        }
    }
    return ret;
}
var tree = [{
    "name": "上海市",
    "child": [{
            "name": "市辖区",
            "child": [{
                    "name": "黄浦区",
                    "child": null
                },
                {
                    "name": "卢湾区",
                    "child": null
                },
                {
                    "name": "徐汇区",
                    "child": null
                },
                {
                    "name": "长宁区",
                    "child": null
                },
                {
                    "name": "静安区",
                    "child": null
                },
                {
                    "name": "普陀区",
                    "child": null
                },
                {
                    "name": "闸北区",
                    "child": null
                },
                {
                    "name": "虹口区",
                    "child": null
                },
                {
                    "name": "杨浦区",
                    "child": null
                },
                {
                    "name": "闵行区",
                    "child": null
                },
                {
                    "name": "宝山区",
                    "child": null
                },
                {
                    "name": "嘉定区",
                    "child": null
                },
                {
                    "name": "浦东新区",
                    "child": null
                },
                {
                    "name": "金山区",
                    "child": null
                },
                {
                    "name": "松江区",
                    "child": null
                },
                {
                    "name": "青浦区",
                    "child": null
                },
                {
                    "name": "南汇区",
                    "child": null
                },
                {
                    "name": "奉贤区",
                    "child": null
                }
            ]
        },
        {
            "name": "县",
            "child": [{
                "name": "崇明县",
                "child": null
            }]
        }
    ]
}];
console.log(tree2arr(tree));

Answer 5

interface TreeNode {
  name: string;
  child?: TreeNode[]|null;
}

function getTreeNames(list: TreeNode[]): string[][] {
  const dfs = (list: TreeNode[], result: string[][] = [], names: string[] = []): string[][] => {
    return list.reduce((res,node) => {
      // 先把遍历到的节点name存起来，即先(前)序遍历
      names.push(node.name);
      // 深度遍历节点
      // 遍历到叶子节点时拷贝name数组push进结果【数组是引用类型，故需要拷贝一次】
      if(node.child && node.child.length) dfs(node.child, res, names)
      else res.push(names.slice())
      // 回溯name
      // 当执行至这里时代表已经到达叶子节点，要返回到上一级节点了，故要把刚push的name推出
      names.pop();
      return res;
    }, result);
  }
  // 外层的getTreeNames实际上只是为了隐藏内部的dfs函数的另外两个参数
  // 也可以考虑去除外层包装直接将dfs作为getTreeNames
  return dfs(list)
}

getTreeNames(data)

Answer 6

// 将树形结构数组对象转换为二维数组
function flattenTreeArray(treeArray) {
  const result = [];

  function flatten(node, level) {
    result.push({
      id: node.id,
      name: node.name,
      level: level
    });

    if (node.child && node.child.length > 0) {
      node.child.forEach(child => {
        flatten(child, level + 1);
      });
    }
  }

  treeArray.forEach(node => {
    flatten(node, 0);
  });

  return result;
}

Answer 7

使用递归的方式来解决，并且使用尾递归进行优化

interface Item {
    name: string
    child: Item[] | null
}


function transformItem(item: Itme, result: string[]) {
    if (item.child === null) {
        return [...result, item.name]
    }
    return item.child.map(c => transformItem(c, [...result, item.name]))
}

function main(items: Item) {
    return items.flatMap(item => transformItem(item, []))
}