バイナリ検索ツリーで親を検索しますか？

Question

私は、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は何ですか？

Answer 1

コードが現在動作しているので、あなたは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