リスト内のノードの子を分離する方法

Question

私は各ノードがその値に対応する子ノードへの値と参照を含むエントリを持つリストであるトライデータ構造に取り組んでいますが、例えば、 "the"と "sin"が両方ともトライであれば、CONTAINS（）関数は "s"が第1レベルにあるため "true"を返しますが、 「h」は2番目のレベルにあり、「e」は3番目のレベルにありますが、これらの文字は別のブランチになければなりません。私はPythonのリファレンスについて読んだことがあり、なぜこれが起こっているのか理解できません。

class triepair: 
    value = None 
    next = None 

    def __init__(self, value=None, next=None): 
     self.value = value 
     self.next = next 

    def NEXT(self,next): 
     self.next = next 

    def GETNEXT(self): 
     return self.next 

class trienode: 
    nodespace = [] 

    def __int__(self,nodespace=[]): 
     self.nodespace = nodespace 

    def APPEND(self,value): 
     newnext = trienode() 
     newpair = triepair(value,newnext) 
     self.nodespace.append(newpair) 

    def NEXT(self, value): 
     for triepair in self.nodespace: 
      if triepair.value == value: 
       return triepair.GETNEXT() 

     print("ERROR: value not found") 
     return None 

    def CONTAINS(self, value): 
     for triepair in self.nodespace: 
      if triepair.value == value: 
       return True 

     return False 

    def INSERT(self, word): 
     c = word[:1] 
     rest = word[1:] 

     if self.CONTAINS(c): 
      if len(rest) > 0: 
       nextnode = self.NEXT(c) 
       nextnode.INSERT(rest) 

     else: 
      self.APPEND(c) 
      if len(rest) > 0: 
       nextnode = self.NEXT(c) 
       nextnode.INSERT(rest) 


    def TRACE(self, word): 
     c = word[:1] 
     rest = word[1:] 
     if self.CONTAINS(c): 
      print "found character ",c 
      if self.NEXT(c) is not None and len(rest) > 0: 
       self.NEXT(c).TRACE(rest) 
      else: 
       print "trace complete" 

    def HASWORD(self, word): 
     c = word[:1] 
     rest = word[1:] 

     if self.CONTAINS(c): 
      #print str(self)," contains ",c 
      if len(rest) > 0: 
       return self.NEXT(c).HASWORD(rest) 
      else: 
       return True 

     else: 
      return False 

class trie: 
    root = trienode() 

    def __init__(self): 
     self.root = trienode() 

    def INSERT(self,word): 
     self.root.INSERT(word) 

    def TRACE(self,word): 
     if self.root is not None: 
      self.root.TRACE(word) 
     else: 
      print("null trie") 

    def CONTAINS(self, word): 
     return self.root.HASWORD(word) 

Answer 1

Lol、これはデバッグにしばらく時間がかかりましたが、わかりました。これに

class trienode: 
    nodespace = [] 

    def __int__(self,nodespace=[]): 
     self.nodespace = nodespace 

：この

変更

class trienode: 
    nodespace = [] 

    def __init__(self): 
     self.nodespace = [] 

はまず、__int__はものではありませんが、それは問題の一部のみです。

正確にという完全なPythonの詳細が分からずに、の理由で、ルートnodespaceが再利用されていました。

APPEND()に新規作成すると、実際には発生せず、新しい「子」に同じnodespaceが表示されます。

結果的にすべてがフラットです。 value -> trienodeのペアはすべて同じレベルにあり、3つのノードの参照は常に同じものです。

とにかく上記の変更を行うと、新しい空番号nodespaceから始まり、したがってAPPEND()と.NEXT().CONTAINS()などが確実に動作するようになります。