二叉搜索樹懶洗掉Python

我創建了一個二叉搜索樹類，并試圖了解“延遲洗掉”的作業原理。我設定了一個標志以顯示節點是否已被洗掉。當我搜索要洗掉的值時，self.removed 將被標記為 True。但是，當我使用 findValue 方法時，它仍然說洗掉的值仍然存在。

我一直在研究延遲洗掉的作業原理，他們都說你需要設定一個標志并將其設定為 True 如果找到該值。為了讓它發揮作用，我還需要實施什么其他措施嗎？還是我錯過了什么？

任何幫助，將不勝感激！

class Node:

    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None
        self.removed = False

    def setLeft(self, left):
        self.left = left

    def setRight(self, right):
        self.right = right

    def getLeft(self):
        return self.left

    def getRight(self):
        return self.right

    def getValue(self):
        return self.value


class Tree:

    def __init__(self):
        self.root = None

    def insertValue(self, value):
        """add a new node containing value to the tree """
        if self.root is None:
            temp = Node(value)
            self.root = temp
            return
        self.recInsertValue(value, self.root)

    def recInsertValue(self, value, ptr):
        if value < ptr.value:
            if ptr.getLeft() is None:
                temp = Node(value)
                ptr.left = temp
            else:
                self.recInsertValue(value, ptr.getLeft())
        else:
            if ptr.right is None:
                temp = Node(value)
                ptr.right = temp
            else:
                self.recInsertValue(value, ptr.right)

    def findValue(self, value):
        """return true if there is a node containing value, false otherwise"""
        ptr = self.root

        while ptr is not None:
            if ptr.value == value:
                return True
            if value < ptr.value:
                ptr = ptr.getLeft()
            else:
                ptr = ptr.getRight()
        return False

    def removeValue(self, value):
        ptr = self.root
        while ptr is not None:
            if ptr.value == value:
                ptr.removed = True
                return True
            if value < ptr.value:
                ptr = ptr.getLeft()
            else:
                ptr = ptr.getRight()
        return False


    def inOrder(self):
        return self.recInOrder(self.root)


    def recInOrder(self, ptr):
        buffer = ""
        if ptr is not None:
            buffer  = self.recInOrder(ptr.getLeft())
            buffer  = str(ptr.getValue())   " "
            buffer  = self.recInOrder(ptr.getRight())
            return buffer
        return ""

uj5u.com熱心網友回復：

您還應該修改搜索方法，否則無法使用該removed標志。

    def findValue(self, value):
        """return true if there is a node containing value, false otherwise"""
        ptr = self.root

        while ptr is not None:
            if ptr.value == value and not ptr.removed:
                return True
            if value < ptr.value:
                ptr = ptr.getLeft()
            else:
                ptr = ptr.getRight()
        return False

也不要忘記recInOrder：

    def recInOrder(self, ptr):
        buffer = ""
        if ptr is not None:
            buffer  = self.recInOrder(ptr.getLeft())
            buffer  = str(ptr.getValue())   " " if not ptr.removed else ""
            buffer  = self.recInOrder(ptr.getRight())
            return buffer
        return ""

標籤：Pythonpython-3.x算法数据结构二叉搜索树

上一篇：為序列寫一個演算法

下一篇：素數分解的除數數