扁平数据转树形求助，无 parentId，只有“/a/b/c”的路径

[yaphets666]

数据类似
{
"path": "/顶级目录 /基本资料 /测试文件夹",
"file_id": "20220223113038833005618826100001"
},
{
"path": "/顶级目录 /学习资料 /学习资料-1/学习资料-1-1",
"file_id": "20222211646376995968624808413776"
},
{
"path": "/顶级目录 /其他",
"file_id": "551D3363-900F-4C90-941C-BA2DC8D6D0AD_233D55BD45C64964B848DDCD3A42B1F4"
},
{
"path": "/顶级目录 /其他",
"file_id": "6AEF3E58-DC5D-4081-9DF0-1DB2D625BC06_CA383FB15A774BF8BFC04BEEB1E1A6B9"
},
{
"path": "/顶级目录 /学习资料 /学习资料-2",
"file_id": "20220226175423469003578532800001"
},
{
"path": "/顶级目录 /默认文件存放处",
"file_id": "20220228110816879009037188700001"
},
{
"path": "/顶级目录 /默认文件存放处",
"file_id": "20220228110821760004283673600001"
},


我现在的方法是把,path 转化成数组['顶级目录','学习资料','学习资料-1','学习资料-1-1']后循环,判断创建树形.内部有循环套循环再套 find 的的操作,导致目前性能有问题,网上找不到类似的方法,请大家帮帮忙

[doommm]

循环的时候用 HashMap 记录下每一段 path 对应目录的对象？可以把现在的代码发上来看看

[yaphets666]

@doommm function markFolder(tree) {
tree.forEach(item => {
if (item.children) {
item.children.forEach(child => {
if ("children" in child) {
item.hasFolderChild = true;
}
});
markFolder(item.children);
}
});
}
function addPath(folders) {
folders.forEach(item => {
item.isOpen = true;
item.checked = false;
item.folder_name = item.folderName;
if ("children" in item) {
item.children.forEach(child => {
child.path = item.path + "/" + child.folderName;
});
addPath(item.children);
}
});
}
function makeTree(data,length = 0) {
let { files, folders } = data;
const rootName = files[0].file_folder.slice(1).split("/")[0];
folders.forEach(item => {
item.path = "/" + rootName + "/" + item.folderName;
});
addPath(folders);
let tree = [{ children: folders }];
tree[0].folderName = rootName;
tree[0].folder_name = rootName;
tree[0].path = "/" + rootName;
tree[0].isOpen = true;
files.forEach(item => {
console.count(item.file_folder)
let pathArr = item.file_folder.slice(length + 1).split("/");
let curr = {}; //指针对象

pathArr.forEach((path, index) => {
if (index === 0) {
let root = tree.find(
branch => branch.folderName === path || branch.folder_name === path
);
if (!root) {
tree.push({
folder_name: path,
children: [],
isOpen: true,
root: "root",
path: "/" + path,
checked: false
});
}
curr = tree.find(
branch => branch.folderName === path || branch.folder_name === path
);
} else {
let obj = curr.children.find(
branch => branch.folderName === path || branch.folder_name === path
);
if (!obj) {
curr.children.push({
folder_name: path,
children: [],
isOpen: true,
path: curr.path + "/" + path,
checked: false
});
}
curr = curr.children.find(
branch => branch.folderName === path || branch.folder_name === path
);
}
});
curr.children.push(
Object.assign(
{
path: item.file_folder,
checked: false
},
item
)
);
});
markFolder(tree);
return tree;
}




不光是处理树的代码 还有业务代码 工具代码

[sunjiayao]

1. 创建一个 hash 对象； k = path ; v = {currentPath,parent,fileIds,child}
2. 循环数组
3. path.split("/") 后循环（因为是 / 开头的所以 index 要从 1 开始）
4. 检测 pathArray[index] 是否存在 hash 内；如果没有创建 v 对象；如果当前 index >1 则说明有 parent; parent = pathArray[index-1]
5. 当 index = pathArray.length -1 时; 要往 hash.pathArray[index].fileIds 添加当前 fileId
以上结束后
循环 hash.values 如果 v.parent 不为空。则把 v 添加进 hash[v.parent].child 内;
最后 hash[顶级目录] 就是你想要的 tree

[sunjiayao]

@sunjiayao

[sunjiayao]

@sunjiayao
1. 创建一个 hash 对象； k = path ; v = {currentPath,parent,fileIds,child}
更正为
1. 创建一个 hash 对象； k = currentPath ; v = {currentPath,parent,fileIds,child}

[imn1]

我只有 python 的

xpath2dict 函数

gist.github.com/ImN1/cbcbfabb9ed2f277c926427f4598bbb7

--------------------
最后几行(一个递归)是某国外博客抄过来的，根据数据格式有小改动，当时忘记记下出处，其他是自己写的

这是我常用的自定义函数，因为 pyqt5 树控件用得很多，经常需要构建
由于我部分项目传入数据格式是 topnode/node/[leaf] 这种格式(由拼接后得到)
所以加了段 tryJson 代码，如果觉得没需要，可以去掉，v = tryJson(x[1]) 这句改为 v=x[1]则可

[imn1]

补充上面：
传入 xpath 每行无论是否以 / 开头，第一个节点均视为首层（非 root ）节点
因为 x.strip(sep) 把开头的分隔符去掉了，注意一下这点

@Livid
为何回复贴 gist url 也视为 spamming ？我要去掉 https 才能发，沙盒测试时没这个限制

[ch2]

前缀树了解一下

[Livid]

@imn1 收到。你看到的出错提示信息是？

[imn1]

@Livid #9
提示就是不要贴链接，会被视为 spamming ，无法提交-->提交还是继续提示

[ZZITE]

根据 Path 来创建 parent 关系
如 “/顶级目录 /基本资料 /测试文件夹"先转为你说的数组，最后一项'测试文件夹'为自身 id ， 前面的所有项再 join('-')，即'顶级目录-基本资料'作为 parentId 。有了这个 parentId 再转树就容易了吧。

[3dwelcome]

算法没问题啊，我也这样写。

性能主要瓶颈在于查找已经创建好的树对象。

可以建立一个全局 hash pair ，专门用于查找; 在 tree.find 参数里，不要传对象，改传字符串，这样查找就能快很多。

你现在 tree 是结构体，查找数量一多肯定慢。用{}的键值去查。

[Kilerd]

trie 树就好了啊

[yaphets666]

@sunjiayao
@imn1
@ch2
@ZZITE
@3dwelcome
@Kilerd 感谢 我慢慢看下