python - Python递归中的二叉搜索树删除

Question

我知道这个问题已被问过数百次，但我一直无法找到与我的二叉搜索树实现完全相同的问题。我在 Python 中实现了一个基本的二叉搜索树类；目前唯一未完成的功能是删除功能。我了解它是如何完成的算法，以及三种不同的删除情况。我有一个限制是我不想使用父指针，我不确定如何跟踪前一个节点，以便我可以根据删除适当地设置它。

例如，对于要删除的节点有一个孩子的情况，我不知道如何跟踪前一个节点（父节点），以便我可以将其左或右孩子更新为该节点的孩子那被删除了。

我不想在这个删除函数中为每个节点使用父指针

    def delete(self, value):
        if self.root:
            self.__delete(value, self.root)

    def __delete(self, value, curr_node):
        #How do I keep track of previous (parent) node here?
        if curr_node:
            if value < curr_node.value:
                self.__delete(value, curr_node.left)
            elif value > curr_node.value:
                self.__delete(value, curr_node.right)
            elif value == curr_node.value:
                #Case 1: Node is leaf (no children)
                #Case 2: Node has one child: the parent node has its child updated to the deleted node's children
                #Case 3: Node has two children 
                pass

完整代码

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.value)

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):        
        if not self.root:
            self.root = Node(value)
        else:
            self.__insert(value, self.root)

    def __insert(self, value, curr_node):
        if value < curr_node.value:
            if not curr_node.left:
                curr_node.left = Node(value)
            else:
                self.__insert(value, curr_node.left)
        elif value > curr_node.value:
            if not curr_node.right:
                curr_node.right = Node(value)
            else:
                self.__insert(value, curr_node.right)
        else:
            print("Node already exists!")

    def lookup(self, value):
        if value == self.root.value:
            return self.root
        else:
            self.__lookup(value, self.root)

    def __lookup(self, value, curr_node):
        if value < curr_node.value:
            if value == curr_node.left.value:
                return curr_node.left
            else:
                self.__lookup(value, curr_node.left)
        elif value > curr_node.value:
            if value == curr_node.right.value:
                return curr_node.right
            else:
                self.__lookup(value, curr_node.right)
        else:
            print("Value doesn't exist!")

    def height(self):
        if not self.root:
            return 0
        else:
            return self.__height(self.root)

    def __height(self, curr_node):
        if not curr_node:
            return 0 
        return 1 + max(self.__height(curr_node.left), self.__height(curr_node.right))

    def min_value(self):
        if self.root:
            return self.__min_value(self.root)

    def __min_value(self, curr_node):
        if not curr_node.left:
            return curr_node

        return self.__min_value(curr_node.left)

    def max_value(self):
        if self.root:
            return self.__max_value(self.root)

    def __max_value(self, curr_node):
        if not curr_node.right:
            return curr_node
        return self.__max_value(curr_node.right)

    def count_nodes(self):
        if not self.root: 
            return 0 
        else:
            return self.__count_nodes(self.root)

    def __count_nodes(self, curr_node):
        if not curr_node:
            return 0 

        return 1 + self.__count_nodes(curr_node.left) + self.__count_nodes(curr_node.right)

    def inorder_traversal(self):
        if self.root:
            return self.__inorder_traversal(self.root)

    def __inorder_traversal(self, curr_node):
        path = []

        if curr_node:
            path.extend(self.__inorder_traversal(curr_node.left))
            path.append(curr_node.value)
            path.extend(self.__inorder_traversal(curr_node.right))

        return path

    def __num_children(self, curr_node):
        if not curr_node.left and not curr_node.right:
            return 0
        elif curr_node.right or curr_node.left:
            return 1
        elif curr_node.right and curr_node.left:
            return 2

    def delete(self, value):
        if self.root:
            self.__delete(value, self.root)

    def __delete(self, value, curr_node):
        #How do I keep track of previous (parent) node here?
        if curr_node:
            if value < curr_node.value:
                self.__delete(value, curr_node.left)
            elif value > curr_node.value:
                self.__delete(value, curr_node.right)
            elif value == curr_node.value:
                #Case 1: Node is leaf (no children)
                #Case 2: Node has one child: the parent node has its child updated to the deleted node's children
                #Case 3: Node has two children 
                pass

标签： pythonsearchtreebinary