在二叉搜索樹中查找父項？

Question

我希望在BST中找到具有特定值的節點的父節點。我的節點類具有屬性項（即值/鍵），左側和右側。

想法找到一個親本是這樣的：
1）如果該值（鍵）不存在，則返回無，無
2）如果根是等於值（鍵），則返回None根
3）否則查找值（鍵）和回報（PAR，節點），其中面值爲家長和節點

我的功能看起來是這樣的：

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開始必須存在，如果它必須存在，它必須存在於搜索路徑。

應該指出，你有效地執行了兩次搜索，但這並不是那麼高效。相反，你可以嘗試這樣的事情：

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