创建带权重的n叉树

Question

在Python中，我想创建一个n叉树，也就是每个节点可以有多个分支，并且每个分支都有一个权重。这里有个例子：
节点A有三个孩子B、C、D，权重分别是100、-200和250；
B是叶子节点；
C有两个孩子E和F，权重分别是150和200；
E和F都是叶子节点；
D有两个孩子G和H，权重分别是-50和100；
G和H也是叶子节点；
你能给我展示一下怎么构建这个树吗？

> 感谢你的帮助。
谢谢你。在看了你的例子后，我觉得这让我重新思考了这个问题。与其给每个分支分配权重，我更想给每个孩子路径分配概率。

每个孩子节点如果走了那条路径，就会累积权重。这样从图示上看，每个节点都有概率和累积的权重。

A 0
B 100
C 250
D 150
E
F 200
G -50
H 100

A B C D E F G H

A 0 .25 .35 .4 0 0 0 0

B 0 0 0 0 0 0 0 0

C 0 0 0 0 .6 .4 0 0

D 0 0 0 0 0 0 .5 .5

E 0 0 0 0 0 0 0 0

F 0 0 0 0 0 0 0 0

我会从这样的代码开始：

class Adjacency:
def init(self, wt):
self.wt = wt
self.adj = []

然后我想这样做：

对于根节点来说，没有权重。
然后在我递归添加孩子的时候，我想为它走的路径添加概率，基本上是向后看它的父节点。然后把权重加到添加的孩子上。所以当这个孩子变成下一个父节点时，我就不再加权重，因为我在之前的步骤中已经加过了。但对于叶子节点，我必须加上权重。
另外，我不确定是否会有多个路径到达一个节点，但我想保留这个选项，就像你建议的那样。

我不太理解下面的代码，你能解释一下它是如何适应我所描述的场景的吗？我对Python还很陌生。

def add_node(self):
    for row in self.adj:
        row.append(inf)
    self.adj.append([inf] * (len(self.adj) + 1))

def set_weight(self, i, j, w):
    if i >= j:
        raise ValueError("Don't make a cycle")
    self.adj[i][j] = w

抱歉，格式有点乱，希望你能理解我的发帖。

Answer 1

我猜你可能想用这些树来做一些算法，所以我建议你使用networkx这个工具包。

Answer 2

我不知道你到底想要什么。而且你也没有提供任何代码让我评论。所以这需要你自己详细说明一下。与此同时，我可以给你一个一般的“节点”类的例子。不过网上肯定有更好的例子。

class Node(object):
   def __init__(self):
      self.children = []
      self.weight = 0

   def add_branch(self, node):
      self.children.append(node)

   def is_branch(self):
       return len(self.children) > 0

Answer 3

这应该能帮助你入门：

class TreeNode():
     def __init__(self,initWeight=<default>):
        self.children = List()
        self.weight = initWeight

    def addChild(self, weight):
        self.children.append(TreeNode(weight))

你只需要一个孩子列表和一个权重字段。之后你可以做得更复杂。在你的主程序中：

from treefile import TreeNode

if  __name__ == "__main__":
    root = TreeNode(5)
    root.addChild(100)

会形成

A(权重=5) | B(权重=100)

你可以给A添加任意数量的孩子，并通过查看孩子列表来获取这些孩子的引用。