python - 具有尽可能多的 child 的节点 python

Question

我想在 Python 中创建一个数据结构，但因为我非常喜欢 C 语言。我需要一点帮助。

一般来说，我想创建一个 Node 类，它将包含数据、一个指向兄弟节点的指针、一个指向子节点的指针和一个指向父节点的指针。

这是对 Node 类的一种思考方式:

                                 NODE
            /            /         ...  \                   \
       child_node1 - child_node2 - ... - child_node(N-1) - child_nodeN

到目前为止，我正在努力解决的问题是:我想重载 Node 类的“+”运算符，这样我就可以这样做:

node1 = Node("data1")
node2 = Node("data2", 3)
node1 = node1 + node2

所以基本上使 2 个节点成为 sibling 。

这是我的代码:

class Node:
def __init__(self, data = None, numberOfChildren = 0):
    '''
    Creates a new Node with *numberOfChildren* children. 
    By default it will be set to 0, meaning it will only create the root of the tree.
    No children whatsoever.
    '''
    self.__sibling_count = 0
    self.__parent = Node()
    self.__sibling = Node()
    self.__data = data

    self.__children = []
    if numberOfChildren != 0:
        '''
        The Node has children and we need to initialize them
        '''
        for i in range(numberOfChildren):
            self.__children[i] = Node()

def getParent(self):
    return self.__parent


def getData(self):
    return self.__data

def getChild(self, i):
    '''
    Returns the ith child of the current *Node*.
    '''
    return self.__children[i]


def __add__(self, other):
    '''
    Overloads the *+* function so that *Node* objects can be added.
    The 2 merged *Node* elements will now be siblings.
    ex. node1  = Node()
        node2 = Node()
        node1 = node1 + node2
    '''
    if self.__sibling_count == 0:
        self.__sibling = other
        self.__sibling_count += 1
    return self

但是当我尝试像这样添加 2 个节点时:

node1 = Node()
node2 = Node()
node1 = node1 + node2

我得到一个RuntimeError: maximum recursion depth exceeded。为什么会这样？

Answer 1

Python 中的运算符重写是允许的，但是对于不是连接或求和的内容使用 + 运算符是不受欢迎的。一个更 pythonic 的实现会像这个未经测试的片段:

class Node(object):
    def __init__(self, parent=None):
        self.set_parent(parent)
        self.children = set()

    def set_parent(self, parent):
        if self.parent and self.parent is not parent:
            self.parent.children.remove(self)
        self.parent = parent

    def siblings(self):
        if self.parent is None:
            return []
        return [_ for _ in self.parent.children if _ is not self]

    def add_child(self, node):
        self.children.add(node)
        node.set_parent(self)

    def add_sibling(self, node):
        assert self.parent, "root node can't have siblings"
        self.parent.add_child(node)

...等等。当然，您可以覆盖 + 运算符来执行 add_sibling，但其要点是严重依赖 native 集合。

如果你想创建一个有 3 个 child 的笔记，那就是:

root = Node()
nodes = [Node(parent=root) for _ in range(3)]