python - 如何打印给定节点的父节点

Question

我创建了一个二叉树，我试图找到我手动传递的任何节点的父节点。它在左子树上运行良好，但仅对于右子树上的某些特定节点没有给出任何结果。

# 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))

如果我给出root.parent_search(root,80)，我会得到 90 作为 80 的父级。但是，如果我搜索，假设右侧是 40，它会给出 NoneType 错误。

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'

观察

我没有看到子树的右子树有任何问题，因为当我们调用它的父树或子树时，我可以看到 root.left.right 成功传递。

Answer 1

我明白为什么你使用了两个return，你需要从函数中返回一些东西，并且你需要为左数组和右数组调用它。只需使用 or 即可。因为，something 或 None 总是返回 something

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)