在Python中找到树上的所有唯一单一分支。

huangapple go评论67阅读模式
英文:

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']]

huangapple
  • 本文由 发表于 2023年6月1日 09:14:41
  • 转载请务必保留本文链接:https://go.coder-hub.com/76378108.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定