Python

Question

我正在为一棵树创建一个 python class，其中每个节点都有 "order" 给出的 children 数（但每个 child 只有一个节点）。我有一个方法，children(self,i)，它 returns 索引 i 处节点的 children。我需要实现 parent(self, i) ，它将在索引 i 处获得 child 的 parent。

这是我目前的情况：

class Tree:
  def __init__(self, order=2, l=[]):
    self._tree = l
    self._order = order

  def children(self, i):
    left = self._tree[(i+1)*self._order-1]
    right = self._tree[(i+1)*self._order]
    return [left, right]

  def parent(self, i):
    if i>len(self._tree):
        return ValueError
    elif i==0:
        return None
    else:
        #get parent of node i

由 order=2 和列表 [45, 2, 123, 1, 8, 40, 456] 表示的示例树如下所示：

      45
    /    \
  2       123
 / \     /   \
1   8   40   456

我知道可能有一种方法可以逆转我用于 children(self, i) 的方法，但我不确定如何。

Answer 1

你会做逆运算：

else:
    #get parent of node i
    return self._tree[(i-1)//self._order]

请注意，您的实现仅适用于二叉树（您 return 两个 children，而不是 n）。像这样更正它：

def children(self, i):
    return self._tree[(i*self._order+1):((i+1)*self._order+1)]

Python - 平面列表树实现：给定 child，得到 parent？

Python - Flat list tree implementation: Given child, get parent?

tree

n-ary-tree