插入功能使bst无法正常工作

Question

如果有人可以帮我递归部分？我省略了一些认为没有必要的部分但是在那个功能不起作用之后。

class node(object):
    def __init__(self,value):
        self.data=value
        self.left=None
        self.right=None

def insert(Node,value):
    if Node is None:
        Node=node(value)
    else:
        if value<Node.data:
##            if Node.left is None: Node.left=node(value)
##            else: insert(Node.left,value)
            insert(Node.left,value)
        else:
##            if Node.left is None: Node.left=node(value)
##            else: insert(Node.left,value)
            insert(Node.right,value)

Answer 1

因为您需要为空分支创建新的node实例。

让我们看看两个定义会发生什么，打印出Node参数的值：

def insert(Node, value):
  print(Node)
  if Node is None:
    Node=node(value)
  else:
    if value<Node.data:
      insert(Node.left,value)
    else:
      insert(Node.right,value)

在REPL上：

In [17]: badTree = node(10)

In [18]: badTree.data
Out[18]: 10

In [20]: badTree.left.data
----------------------------------------------------------------------
AttributeError                       Traceback (most recent call last)
<ipython-input-20-3cb52def2967> in <module>()
----> 1 badTree.left.data

AttributeError: 'NoneType' object has no attribute 'data'

In [21]: badTree.right.data
----------------------------------------------------------------------
AttributeError                       Traceback (most recent call last)
<ipython-input-21-b6f1267c9d29> in <module>()
----> 1 badTree.right.data

AttributeError: 'NoneType' object has no attribute 'data'

让我们看看如果我们向badTree插入一个元素会发生什么：

In [22]: insert(badTree, 2)
<__main__.node object at 0x7f706bf34d30>
None

In [23]: badTree.left.data
----------------------------------------------------------------------
AttributeError                       Traceback (most recent call last)
<ipython-input-23-3cb52def2967> in <module>()
----> 1 badTree.left.data

AttributeError: 'NoneType' object has no attribute 'data'

它无法插入元素，但为什么？在badTree，left和right分支都是None（空），这意味着我们需要在那里创建新树，因为我们将无法递归地添加新值，因为我们失去了对主要Node的引用。这是，如果我们在向insert(Node.left, value)指定一个新对象之前调用Node.left，它将等同于调用insert(None, value)（这个值为None，当我们在insert上调用badTree时可以看到它），它将递归调用insert并执行None = node(value)。什么都不做

如果我们使用这个定义会发生什么：

def insert(Node, value):
  print(Node)
  if Node is None:
    Node = node(value)
  else:
    if value < Node.data:
      if Node.left is None:
        Node.left = node(value)
      else:
        insert(Node.left, value)
    else:
      if Node.right is None:
        Node.right = node(value)
      else:
        insert(Node.right, value)

在REPL上：

In [25]: newTree = node(4)

In [26]: insert(newTree, 10)
<__main__.node object at 0x7f706bf30668>

In [27]: insert(newTree, 12)
<__main__.node object at 0x7f706bf30668>
<__main__.node object at 0x7f706bf30a58>

现在看到它不会再失败，因为我们正在跟踪树节点中的内存地址，因此我们可以引用那些允许我们就地插入的对象（树）。