英文:
Find all unique single branch on a tree in python
问题
我正在尝试编写一个Python算法，以获取树中路径直到最后一个节点的所有节点列表。
每个子节点有未知数量的子节点。这是对评论线程的表示。例如，对于帖子A，有回复B和C等。我想获取所有唯一的对话流，所以只需从每个节点中获取文本主体：例如：(A B D G)。因此，数据框将具有以下行：0(A B D G)，1(A B D H)，2(A C E I)，3(A C F)，4(A C J)。
这是我目前拥有的树结构。
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
self.parent = None
def add_child(self, child):
child.parent = self
self.children.append(child)
def get_children_body(self):
body = ""
for child in self.children:
body = body + child.data["body"]
return body
def has_children(self):
return len(self.children) > 0
def get_author(self):
return self.data["author"]
编辑：这个方法不起作用，但这是我尝试过的内容。
# 返回列表的列表
def find_all_branches(node):
retList = []
for child in node.children:
retList.append(find_all_branches_recursive(child, [node.data], retList))
return retList
def find_all_branches_recursive(node, curr_list, final_list):
if node.has_children():
for child in node.children:
curr_list.append(child.data)
find_all_branches_recursive(child, curr_list, final_list)
else:
curr_list.append(node.data)
final_list.append(curr_list)
英文:
I'm trying to write an algorithm in Python to get a list of all nodes in a tree where the path reaches until the last node.
Each child has an unknown number of children. It is a representation of a comment thread. For instance the for post A there are replies B and C and so on. I want to get all unique streams of conversation so just get the body of the text from each node: eg: (A B D G). So the data frame would have the following rows: 0(A B D G), 1(A B D H), 2(A C E I), 3(A C F), 4(A C J).
A
|
-----
| |
B C
| |
| -------
| | |. |
D E F. J
/ | |
G H I
This the tree I currently have
class TreeNode:
def __init__(self, data):
self.data = data
self.children = []
self.parent = None
def add_child (self, child):
child.parent = self
self.children.append(child)
def get_children_body(self):
body=""
for child in self.children:
body=body+child.data["body"]
return body
def has_children(self):
return len(self.children)>0
def get_author(self):
return self.data["author"]
Edit: this does not work but this is something I have tried
#returns list of list
def find_all_branches(node):
retList=[]
for child in node.children:
retList.append(find_all_branches_recursive(child,[node.data],retList))
return retList
def find_all_branches_recursive(node,curr_list,final_list):
if node.has_children():
for child in node.children:
curr_list.append(child.data)
find_all_branches_recursive(child,curr_list,final_list)
else:
curr_list.append(node.data)
final_list.append(curr_list)
答案1
得分: 2
这是一个足够简单的生成器函数：
def paths(node):
if node.children:
for child in node.children:
for path in paths(child):
yield [node.data] + path
else:
yield [node.data]
>>> list(paths(a)) # 假设a是你树的根节点
[['A', 'B', 'D', 'G'],
['A', 'B', 'D', 'H'],
['A', 'C', 'E', 'I'],
['A', 'C', 'F'],
['A', 'C', 'J']]
英文:
Here's a simple enough generator function:
def paths(node):
if node.children:
for child in node.children:
for path in paths(child):
yield [node.data] + path
else:
yield [node.data]
>>> list(paths(a)) # a being the root node of your tree
[['A', 'B', 'D', 'G'],
['A', 'B', 'D', 'H'],
['A', 'C', 'E', 'I'],
['A', 'C', 'F'],
['A', 'C', 'J']]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论