为什么我在从二进制搜索树中删除最小或最大项目后看到 None 数据?

Why I am seeing None data after deleting the smallest or largest item from Binary Search Tree?

我有一个二叉搜索树。我已经编写了完整树的基本插入、删除、遍历并找到树的最大和最小节点,但是在删除最小或最大节点后我无法找到最大和最小节点。

此函数删除特定节点:

def deleteNode(self,val):
    if self.data:
        if self.data > val:
            self.left.deleteNode(val)
        elif self.data < val:
            self.right.deleteNode(val)
        else:
            if self.left is None:
                self.data = self.right
                return True
            elif self.right is None:
                self.data = self.left
                return True
            else:
                dltNode = self
                dltNode.data = self.data
                largest = self.left.findMax()
                dltNode.data = largest
                dltNode.left.deleteNode(largest)
                return True

此函数查找最小节点:

def findMin(self):
    if self.data:
        if self.left is None:
            return self.data
        else:
            return self.left.findMin()

这是最大节点:

def findMax(self):
    if self.data:
        if self.right is None:
            return self.data
        else:
            return self.right.findMax()

findMin 和 findMax 函数在不删除任何节点的情况下工作正常。 如果我在删除最小和最大节点后调用它们,它们将 return None,无论它们是否应该 return 仅整数节点数据。这是我输出的屏幕截图:

它应该打印 34 而不是 None。

这是我的全部code

deleteNode

中存在一些问题
  • if self.data 不应该存在:这意味着您不能从树中删除值为 0 的节点。其他方法也存在类似问题(findMinfindMaxinsert、...)。

  • self.left.deleteNode(val) 的执行没有首先检查 self.left 不是 Noneself.right.deleteNode(val)

    也是如此
  • self.data = self.right 将节点引用分配给 data 属性(应该是一个数字)。

  • 函数有时return什么都没有(None)或True。由于递归的性质,方法的原始调用者将得到 None。这不一致。

  • 该函数无法处理删除根节点,因为调用者将继续使用根节点引用(示例代码中的 tt2)。

要解决这些问题,您应该创建一个单独的 Tree class,或者同意 deleteNode returns 树的根节点,它可以是与进行调用的根不同的根(当根节点被删除时),甚至 None 当它是树的最后一个节点时。

这是它的样子:

    def deleteNode(self,val):
        if self.data > val:
            if self.left:
                self.left = self.left.deleteNode(val)
        elif self.data < val:
            if self.right:
                self.right = self.right.deleteNode(val)
        else:
            if self.left is None:
                return self.right
            elif self.right is None:
                return self.left
            else:
                largest = self.left.findMax()
                self.data = largest
                self.left = self.left.deleteNode(largest)
        return self

要正确执行此操作,您需要使用此方法中的 return 值,例如:

t1 = t1.deleteNode(34)

注意:在某些方法中,您检查是否 self.data is None。我知道这是一些特殊条件,用于指示根节点不是真正的节点,应该被视为空树,但这不是一个好的模式。相反,一个空树应该只是 None,或者您应该定义另一个 Tree class,它有一个 root 属性,可以是 None.