Python-Wie Eltern eines bestimmten Knotens zu drucken

Question

Ich habe einen Binärbaum erstellt und ich versuche, den Elternknoten von jedem Knoten zu finden, die ich manuell übergeben. Es funktioniert gut auf linken Teilbaum aber gibt mir keine nur für bestimmte Knoten im rechten Teilbaum.

# To create a tree from scratch 
class tree: 
    """To create nodes each time an instance has been 
    created""" 
    def __init__(self, key): 
     self.data = key 
     self.left = None 
     self.right = None 

    def parent_search(self, root, child_node): 
     if root : 
     if root.left.data== child_node: 
      return root.data 
     if root.right.data== child_node: 
      return root.data 
     elif root: 
      return self.parent_search(root.left, child_node) 
      return self.parent_search(root.right, child_node) 

root = tree(10) 
root.left = tree(20) 
root.left.left = tree(90) 
root.left.right = tree(100) 
root.left.left.left = tree(80) 
root.right = tree(30) 
root.right.left = tree(40) 
root.right.right = tree(50) 
print(root.parent_search(root,80)) 

Wenn ich root.parent_search(root,80) gebe ich bekommen 90 als Mutter von 80 .aber wenn ich 40 auf der rechten Seite nehme suchen es gibt mir Nonetype Fehler.

return self.parent_search(root.left, child_node) 
    File "/home/vaibhav/Desktop/Data_Structures/python_play_area.py", line 14, in parent_search 
    if root.right.data== child_node: 
AttributeError: 'NoneType' object has no attribute 'data' 

Beobachtung ich nicht jedes Problem finden Sie in der mit dem rechten Kind des Unterbaums, weil ich root.left.right erfolgreich bestanden immer sehen können, wenn wir es Eltern oder Kind nennen.

Answer 1

Ich verstehe, warum Sie zwei return s verwendet haben, müssen Sie etwas von der Funktion zurückgeben, und Sie müssen dies für beide linken und rechten Array aufrufen. Verwenden Sie einfach einen or dafür. Denn something or None immer something kehrt

def parent_search(self, root, child_node): 
    if not root: return None 
    if root.left and root.left.data==child_node: return root 
    if root.right and root.right.data==child_node: return root 
    return self.parent_search(root.left, child_node) or self.parent_search(root.right, child_node) 

Answer 2

Ich habe gerade eine kleine Änderung an meinen Code durch Hinzufügen, wenn mit der Bedingung root.left wenn root.left == Kind und es funktionierte. Dies ist die minimale Änderung, die ich gemacht habe und es hat funktioniert.

# To create a tree from scratch 
class tree: 
    """To create nodes each time an instance has been 
    created""" 
    def __init__(self, key): 
     self.data = key 
     self.left = None 
     self.right = None 

    def parent_search(self, root, child_node): 
     if root : 
      if root.left and root.left.data== child_node: 
       return root.data 
      if root.right and root.right.data== child_node: 
       return root.data 
      elif root: 
       return self.parent_search(root.left, child_node) or self.parent_search(root.right, child_node) 


root = tree(10) 
root.left = tree(20) 
root.left.left = tree(90) 
root.left.right = tree(100) 
root.left.left.left = tree(80) 
root.right = tree(30) 
root.right.left = tree(40) 
root.right.right = tree(50) 
print(root.parent_search(root,50))