为什么我的根设置为 None？

Question

我无法理解为什么我的根节点被设置为 None。这是树实现的一部分。

class Node(object):
    def __init__(self, d=None):
        self.left = None
        self.right = None
        self.data = d


class Tree(object):
    root = Node()

    #methods to add data to to the binary search tree
    def add(self, d):
        node_to_add = Node(d)
        if self.root is None: 
            self.root.data = node_to_add
        self._traverse_and_add(self.root, node_to_add)

    def _traverse_and_add(self, node, new_node):
        if new_node.data < node.data:
            if node.left is None:
                node.left = new_node
            else:
                self._traverse_and_add(node.left, new_node)

        elif new_node.data > node.data:
            if node.right is None:
                node.right = new_node
            else:
                self._traverse_and_add(node.right, new_node)

当我运行调试器中的代码时，它显示我的根是 None。在我的添加方法中，我检查根是否为 None，如果是，我希望 root.data 取值 d。 root填满后没有none，就可以相应的添加数据了。我在 Java 中使用了类似的方法，我没有遇到这个问题。这个错误成为后来方法的问题，例如寻找深度。如果我使用填充树

，这是我得到的视觉效果

t = Tree()
t.add(10)
t.add(2)
t.add(11)


result = 
  None
   /\
  2 10
     \
      11

expected =
   10
   /\
  2 11

Answer 1

问题在行 -

if self.root is None: 
    self.root.data = node_to_add

在 add() 函数中，您正在检查 root 是否为 none ，但您甚至可能没有在 [=16] 中创建 root 属性 =].

我猜你没有 __init__ 功能。您需要具有以下代码的 __init__ 函数 -

def __init__(self):
    self.root = None

您还需要更改添加功能，如下所示-

def add(self, d):
    node_to_add = Node(d)
    if self.root is None: 
        self.root = node_to_add
    self._traverse_and_add(self.root, node_to_add)

Answer 2

您已将 root 设置为 Node():

class Tree(object):
    root = Node()

但在这里你检查它是 None:

def add(self, d):
    node_to_add = Node(d)
    if self.root is None:  # it is not None, it is Node()

此外，您没有任何 __init__ 方法。你应该在那里定义你的实例变量。

def __init__(self):
    self.root = Node()

所以，现在你可以修改你的检查：if self.root.data is None

为什么我的根设置为 None？

Why is my root being set to None?

python

tree

binary-search-tree