2016-09-11 12 views
1

私は、BSTの特定の値を持つノードの親を見つけたいと思っています。私のノードクラスは属性項目(値/キー)を左から右に持っています。ルートは、値(キー)に等しい場合、値が(キー))なし、なし
2を返さない、存在しませんその後、Noneを返す場合
1):親を見つけるためバイナリ検索ツリーで親を検索しますか?

アイデアは、このようなものです、ルート
3)それ以外の値(キー)とリターンパーは私の関数は、このようになります

親ノードである(パー、ノード)を見つける:

def findpar(self,key): 
    if not self._exists(key): 
     return None,None 
    elif self.root.item==key: 
     return None, self.root 
    p=self.root 
    found=False 
    while not found: 
     if p.left.item==key: 
      return p, p.left 
      found=True 
     elif p.right.item==key: 
      return p, p.right 
      found=True 
     elif p.item<key: 
      p=p.left 
     elif p.item>key: 
      p=p.right 

はどのように問題を扱うかをp.leftまたはp.rightは何ですか?

答えて

3

コードが現在動作しているので、あなたはNoneの左または右の子供の方に向っていることは不可能です。あなたのコードが存在している必要があり

if not self._exists(key): 
    return None,None 

のでkeyで始まるためです、それが存在しなければならない場合、それは検索パス上に存在している必要があります。

効率的ではないが、効果的に検索を2回実行していることに注意してください。代わりに、次のようなものを試すことができます:

def findpar(self,key): 
    parent, node = None, self.root 
    while True: 
     if node is None: 
      return (None, None) 

     if node.item == key: 
      return (parent, node) 

     parent, node = node, node.left if key < node.item else node, node.right 
+0

これは本当にすっきりした解決策です!私はそれを好きではないに親を初期化するとは思わなかった、これは私を大きく助けてくれるはずです。 – Lozansky

+1

@Lozansky HTH。 LMKに入力ミスがあったり、コードに何かがある場合は、私はちょうど答えに直接書きました。 –

関連する問題