时间戳

首页 > 解决方案 > 删除最小二叉搜索树 Python

python - 删除最小二叉搜索树 Python

问题描述

我正在尝试从 BST 中删除最小节点，因此我在树中搜索直到获得最小值（当 root.leftnode 为 None 时），然后将 root.rightnode 设置为根本身以继续 BST。

问题是当我这样做后检查树时，它没有显示曾经发生过删除。

请有人指出我正确的方向，任何建议都值得赞赏。

class node():

    def __init__(self, key, data):

        self.data = data
        self.key = key
        self.leftnode = None
        self.rightnode = None
        self.count = 1


class binarysearch():

    def __init__(self):

        self.size = 0
        self.rootnode = None

    def insert(self, key, data):

        if self.rootnode is None:
            self.rootnode = node(key, data)
        else:
            self.insertnode(self.rootnode, key, data)

    def getroot(self):

        return self.rootnode

    def insertnode(self, root, key, data):

            if root.key == key:
                root.data = data

            elif key < root.key:
                if root.leftnode is None:                    
                    root.leftnode = node(key, data)
                else:
                    self.insertnode(root.leftnode, key, data)
            else:
                if root.rightnode is None:
                    root.rightnode = node(key, data)
                else:
                    self.insertnode(root.rightnode, key, data)

            root.count = 1 + self.sizenode(root.leftnode) + self.sizenode(root.rightnode)

    def inorder(self, root):

        if root is not None:

            self.inorder(root.leftnode)
            print(root.key)
            self.inorder(root.rightnode)

    def deletemin(self):

        if self.rootnode is None:
            print("No nodes exist")
        else:
            self.deleteminnode(self.rootnode.leftnode)

    def deleteminnode(self, root):

        if root.leftnode is not None:
            self.deleteminnode(root.leftnode)
        else:
            print (root.key, "deleted")
            root = root.rightnode


if __name__ == '__main__':

    a = binarysearch()
    a.insert(7,7)
    a.insert(1,1)
    a.insert(8,8)
    a.insert(3,3)
    a.insert(9,9)
    a.insert(2,2)
    a.insert(4,4)
    a.insert(11,11)
    a.insert(10,10)
    a.deletemin()
    a.getnodes()

标签： pythonbinary-search-treeminimum

解决方案

您遇到的问题是root = root.rightnode仅重新绑定局部变量root。它不会更改您对该节点的引用的其他位置（例如树中的父节点）。

要解决此问题，您需要更改递归函数的工作方式。而不是期望它在最后一次调用中完成所有工作，而是return应该作为其父节点的左节点的值。然后那将是节点本身，但对于最小节点，它将是它的右孩子。

def deletemin(self):
    if self.rootnode is None:
        print("No nodes exist")
    else:
        self.rootnode = self.deleteminnode(self.rootnode)

def deleteminnode(self, root):
    if root.leftnode is not None:
        root.leftnode = self.deleteminnode(root.leftnode)
        return root
    else:
        return root.rightnode

关于名称的最后一点说明：root用作树中随机节点的名称有点奇怪。通常一棵树只有一个根节点，其他节点root因为有父节点而不会被调用。node不幸的是，您的节点类已经使用了最传统的名称。通常应该给出类CapitalizedNames，以便lowercase_names可以专门引用实例和其他变量。不过，这只是惯例（以及诸如list打破规则之类的内置类型）。如果您使用标准名称样式，其他人可能更容易理解您的代码，但 Python 不会强制执行它们。它将允许您使用任何您想要的名称。连名字self不是必需的，尽管如果您在没有充分理由的情况下对方法的第一个参数使用不同的东西会非常混乱（一个充分理由的示例：类方法和元类的方法通常cls用作其第一个参数的名称，因为对象将是一个类）。

推荐阅读