可能な限り多くの子を持つノード

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つのノード、兄弟を作成します。

は、ここに私のコードです：

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再帰はスタックオーバーフローと無限再帰を防ぐために制限されています。ブレーク条件を持たない再帰やカウンタは、何回か繰り返した後に停止されます。

いくつかのレベルの後にノードを作成しないでください。そうしないと、pythonがあなたを止めます。 最初にNodeに__init_をアクティブにしていて、その子どものすべての子どもなどにアクティブにしています。これは決して停止せず、この実行時エラーを引き起こします。

>>> def f(): f() 
>>> f() 
Traceback (most recent call last): 
    File "<stdin>", line 1, in <module> 
    File "<stdin>", line 1, in f 
    File "<stdin>", line 1, in f 
    File "<stdin>", line 1, in f 
    ... another 995 times the same 
    File "<stdin>", line 1, in f 
RecursionError: maximum recursion depth exceeded 

あなたはこれに__init__を変更することができます：Pythonでオーバーライド

def __init__(self, levels = 5, numberOfChildren = 0, data = None): 
    ''' 
    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 
    # these will only produce **new** nodes. I commented them. 
    # self.__parent = Node() 
    # self.__sibling = Node() 
    self.__data = data 

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

Answer 2

オペレータは可能ですが、ために+演算子を使用している

は、あなたが行くことができるどこまでの推定とすることを参照してください。連結または合計ではないものが眉をひそめます。よりpythonの実装は、この未テストのフラグメントのようなものになります：

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を実行することもできますが、その要点はネイティブコレクションに大きく依存することです。

あなたは3人の子供とのメモを作成したい場合、それは次のようになります。ところで

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