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

Question

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

此函数删除特定节点：

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

Answer 1

deleteNode

中存在一些问题

if self.data 不应该存在：这意味着您不能从树中删除值为 0 的节点。其他方法也存在类似问题（findMin、findMax、insert、...）。
self.left.deleteNode(val) 的执行没有首先检查 self.left 不是 None。 self.right.deleteNode(val)
也是如此
self.data = self.right 将节点引用分配给 data 属性（应该是一个数字）。
函数有时return什么都没有（None）或True。由于递归的性质，方法的原始调用者将得到 None。这不一致。
该函数无法处理删除根节点，因为调用者将继续使用根节点引用（示例代码中的 t 或 t2）。

要解决这些问题，您应该创建一个单独的 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.

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

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

python

binary-search-tree

nonetype

treenode