正在尝试创建二进制搜索树

Question

因此，当我在主函数中调用它们时，我的findMin和findMax函数无法正常工作，可能需要一些帮助。我的功能不能正常工作吗？我试图通过遍历它们并获取最左边的叶子来递归地调用函数，因为那是最小值，然后遍历右边的子树以找到最大值

heres the error i get

这是我的代码。

from BinaryTree import BinaryTree


class BinarySearchTree(BinaryTree):

    # Constructor
    def BinarySearchTree(self, payload = None, leftChild = None, rightChild = None):

        # payload is the data
        # leftchild is the left subtree
        # rightChild is the right subtree

        BinaryTree.__init__(self, payload, leftChild, rightChild)
        if (self.getPayload() is None):
            # The height of an empty tree is -1
            self.__height = -1
        else:
            # The height of a leaf is 0
            # We can't use computeHeight here because we end up
            # calling it multiple times where there will be
            # new tree being created with "None" as the height.
            self.__height = 0

    def getHeight(self):
        return self.__height

    # Compute and set height based on the subtrees
    def computeHeight(self):
        # the height of an empty tree is -1
        # the height of a leaf is 0
        height = -1

        if (self.getLeftChild() is not None):
            height = max(height, self.getLeftChild().getHeight())
        if (self.getRightChild() is not None):
            height = max(height, self.getRightChild().getHeight())

        self.__height = height + 1

    def setPayload(self, payload):
        BinaryTree.setPayload(self, payload)
        self.computeHeight()

    # inserts a new value into the bst
    def insert(self, x):
        if self.isEmpty():
            self.setPayload(x)

        elif x < self.getPayload():
            if self.getLeftChild() is None:
                # no left subtree
                self.setLeftChild(BinarySearchTree(x))
                self.computeHeight()
            else:
                # go into left subtree
                self.getLeftChild().insert(x)
                self.computeHeight()
        else:
            if self.getRightChild() is None:
                # no right subtree
                self.setRightChild(BinarySearchTree(x))
                self.computeHeight()
            else:
                # go into right subtree
                self.getRightChild().insert(x)
                self.computeHeight

    # Find a value in the BST
    def find(self, x):
        if self.isEmpty():
            return None

        elif x == self.getPayload():
            return self.getPayload()

        elif x < self.getPayload():
            if self.getLeftChild() is None:
                return None
            else:
                return self.getLeftChild().find(x)
        else:
            if self.getRightChild() is None:
                return None
            else:
                return self.getRightChild().find(x)
    def findMin(self):
        leaf = self

        while (leaf.leftChild is not None):
            leaf = leaf.getLeftChild

            return leaf

    def findMax(self):
        leaf = self

        while (leaf.getRightChild() is not None):
            leaf = leaf.getRightChild()

            return leaf

    def inorderTraversal(self):
        BinaryTree.inorderTraversal(self)


        result = ""
        if self.isEmpty():
            return result

        else:
            # visit the left subtree
            if self.getLeftChild() is not None:
                result += self.getLeftChild().preorderTraversal()

            # visiting the root
            result += " " +str(self.getPayload()) + "(" + str(self.getHeight()) + ")"

            # visit the right subtree
            if self.getRightChild() is not None:
                result += self.getRightChild().preorderTraversal()
        return result

def main():
    BT = BinarySearchTree()
    print("isEmpty() = " + str(BT.isEmpty()))
    print(BT)

    BT.setPayload(101)
    print("isEmpty() = " + str(BT.isEmpty()))
    print(BT)

    BT.setLeftChild(BinaryTree(50))
    print(BT)

    BT.setRightChild(BinaryTree(250))
    print(BT)

    BT.getLeftChild().setLeftChild(BinaryTree(42))
    print(BT)

    BT.getLeftChild().getLeftChild().setLeftChild(BinaryTree(31))
    print(BT)

    BT.getRightChild().setRightChild(BinaryTree(315))
    print(BT)

    BT.getRightChild().setLeftChild(BinaryTree(200))
    print(BT)

    print("Find the minimum value of the tree: " + BT.findMin())
    print("Find the maximum value of the tree: " + BT.findMax())
    print("Inserting a value into the tree: " + BT.insert(200))
    print("Inorder traversal: " + BT.inorderTraversal())
    print("Preorder traversal: " + BT.preorderTraversal())
    print("Postorder traversal: " + BT.postorderTraversal())



if __name__ == "__main__":
    main()

Answer 1

在findMin()方法中，您缺少括号leaf.getLeftChild。并且还将return和findMin()方法中的findMax()语句移到while循环之外。

将此更改为

def findMin(self):
    leaf = self
    while (leaf.leftChild is not None):
        leaf = leaf.getLeftChild

        return leaf

此

def findMin(self):
    leaf = self
    while (leaf.leftChild is not None):
        leaf = leaf.getLeftChild()
    return leaf