程序员最近都爱上了这个网站  程序员们快来瞅瞅吧！  it98k网:it98k.com

所以我有一个完美工作的二叉表达式树，但是当我试图修改它以添加一个指向每个节点的父指针时（我稍后需要创建从节点到根的路径），它不起作用。

class Node:
    def __init__(self, value, left=None, right=None, parent=None):
        self.value = value
        self.left = left
        self.right = right
        self.parent = parent


class Tree:
    def __init__(self, lst):
        self.it = iter(lst)  # Create an iterator over the list
        self.lst = lst
        self.root = None

    def create_tree(self):  # Helper function
        value = next(self.it, None)
        print(value)
        N = Node(value)
        if self.root is None:
            self.root = N
        if value is None:  # No more value
            return None
        if not value.isdigit():  # N = Parent
            NL = self.create_tree()  # Use recursion to build the left subtree
            NR = self.create_tree()  # Use recursion to build the right subtree
            return Node(value, NL, NR, parent=N)  # create a Node instance with them as children

        else:  # We need a leaf node
            return Node(value, parent=N)

lst = ["+", "*", "2", "6", "/", "10", "2"]
t = Tree(lst)
t.create_tree()

现在我认为这些行中的错误是： N = Node(value) return Node(value, NL, NR, parent=N) return Node(value, parent=N) Parent=N 与我调用实例的变量“值”的值相同。我可以用什么代替 N 来调用此值的父级？

解决方案

问题在这里：

return Node(value, NL, NR, parent=N) 

和这里：

return Node(value, parent=N)

这个新节点的父节点不是N. N创建为，这里我们为相同的值Node(value)创建另一个节点，但它的父节点引用另一个重复节点。

当您不parent向Node构造函数传递参数，而是让节点构造函数将该属性设置为 时，会更容易None。

要建立父链接，您可以让构造函数分配给其子元素parent的属性。因此，如果给出一个参数，让它获得对当前初始化实例 ( ) 的引用。leftleftparentself

class Node:
    def __init__(self, value, left=None, right=None):
        self.value = value
        self.left = left
        if self.left:
            self.left.parent = self
        self.right = right
        if right:
            right.parent = self
        self.parent = None


class Tree:
    def __init__(self, lst):
        it = iter(lst) # Create an iterator over the list
        
        def create_tree():  # Helper function
            value = next(it, None)
            if value is None:  # No more value
                return None
            if value.isdigit():  # We need a leaf node
                return Node(value)
            # Use recursion to build the left and right subtree and
            #     create a Node instance with them as children
            return Node(value, create_tree(), create_tree())

        self.root = create_tree()


lst = ["+", "*", "2", "6", "/", "10", "2"]
t = Tree(lst)

其他备注

这样做不是好的做法：

    self.lst = lst

树不应保留对调用者提供的列表的引用。这意味着即使这些值已经被处理并存储为树中的节点，列表也不能被垃圾回收。

其次，create_tree是一个辅助函数，不应作为方法提供给您的类的用户。调用者已将值列表传递给构造函数，并且应该期望构造函数已使用这些值构造了树。违反直觉的是，即使调用了构造函数，树仍然需要...通过调用来构建create_tree()。