如何在python中创建一个非二叉树?

Question

我有这样的输入:输入= [["hair"，理发"，男士理发"]， ["头发"，发型"]， ["皮肤"，脱毛"，手臂脱毛"]]。每个子列表中的节点数量可能不相同(例如:给定元素中的第二个元素只有2个节点)。基于此输入，应该形成如下的树:

菜单=

{
"root": [{
"name": "Service Menu Mapping",
"is_root": True,
"is_leaf": False,
"child": [{
"name": "hair",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "hair cut",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "men's haircut",
"is_root": False,
"is_leaf": True,
"child": []
}]
},
{
"name": "hair style",
"is_root": False,
"is_leaf": True,
"child": []
}
]
},
{
"name": "skin",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "waxing",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "arm waxing",
"is_root": False,
"is_leaf": True,
"child": []
}]
}]
}
]
}]
}

我开始学习树形结构的算法，我一直在尝试这种方法，类NonBinTree:

class NonBinTree:
def __init__(self, val):
self.parent = val
self.parent[0]['child'] = []
def add_node(self, val):
self.parent[0]['child'].append(NonBinTree(val))
def __repr__(self):
return f"NonBinTree({self.parent}): {self.parent[0]['child']}"

用这种方法，我可以手工创建树，但如果在任何子集中有n个节点，这将是混乱的。有人能帮助正确的算法或方法吗?提前谢谢。

Answer 1

class对生成输出没有多大帮助，它本质上是一个嵌套的字典。

您可以为每个输入字符串创建项，并键入该标签的路径。然后填充这些child列表。

这是如何作为一个函数来编码的:

def createmenu(paths):
# Create the nodes without linking them, keyed by their path
dct = {
"|".join(path[:i+1]) : {
"name": label,
"is_root": False,
"is_leaf": i == len(path) - 1,
"child": []
}
for path in paths  
for i, label in enumerate(path)
}
# Add root node, identified with an empty-string path
dct[""] = {
"name": "Service Menu Mapping",
"is_root": True,
"is_leaf": len(paths) == 0,
"child": []
}
# Populate child lists
visited = set()
for path in paths:
for i, label in enumerate(path):
pathid = "|".join(path[:i+1])
if pathid not in visited:
visited.add(pathid)
dct["|".join(path[:i])]["child"].append(dct[pathid])
# Wrapper
return {
"root": [dct[""]]
}

使用例子:

paths = [["hair", "hair cut", "men's haircut"],
["hair", "hair style"],
["skin", "waxing", "arm waxing"]]
menu = createmenu(paths)

menu将为:

{
"root": [{
"name": "Service Menu Mapping",
"is_root": True,
"is_leaf": False,
"child": [{
"name": "hair",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "hair cut",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "men's haircut",
"is_root": False,
"is_leaf": True,
"child": []
}]
}, {
"name": "hair style",
"is_root": False,
"is_leaf": True,
"child": []
}]
}, {
"name": "skin",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "waxing",
"is_root": False,
"is_leaf": False,
"child": [{
"name": "arm waxing",
"is_root": False,
"is_leaf": True,
"child": []
}]
}]
}]
}]
}