在Python中查找给定二叉树中是否存在BST的程序

二叉树是一种经常使用的数据结构，它可以使用Python很容易地实现。在二叉树中，每个节点最多有两个子节点：左节点和右节点。其中，BST（二叉搜索树）是一种特殊的二叉树，具有以下特点：

左子树的所有节点值都小于当前节点值。
右子树的所有节点值都大于当前节点值。
左右子树都是BST。

现在，我们需要写一个程序，在给定的二叉树中查找是否存在BST。

二叉树的实现和遍历

在Python中，我们可以使用类来实现二叉树。每个节点包含三个属性：value、left和right。其中，value存储当前节点的值，left和right分别存储左子树和右子树。

下面是一个简单的例子：

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

class BinaryTree:
    def __init__(self, root=None):
        self.root = root

接下来，我们可以实现二叉树的遍历，包括前序遍历、中序遍历和后序遍历。

class BinaryTree:
    # 创建二叉树

    # 前序遍历
    def preorder(self, node):
        if node is not None:
            print(node.value)
            self.preorder(node.left)
            self.preorder(node.right)

    # 中序遍历
    def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(node.value)
            self.inorder(node.right)

    # 后序遍历
    def postorder(self, node):
        if node is not None:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.value)

查找BST的实现

现在，让我们来看看如何查找给定二叉树中是否存在BST。回顾一下，BST需要满足左子树小于当前节点，右子树大于当前节点。因此，我们可以通过比较当前节点和它的左右子节点来判断它是否是一个BST。

下面是一个简单的程序，用于查找给定二叉树中是否存在BST：

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def checkBST(node, left, right):
            if not node:
                return True
            if not left < node.value < right:
                return False
            return checkBST(node.left, left, node.value) and checkBST(node.right, node.value, right)

        return checkBST(root, float('-inf'), float('inf'))

在这个程序中，我们定义了一个名为checkBST的嵌套函数，该函数接受一个节点、一个左边界和一个右边界。如果当前节点为空，我们返回True。否则，如果当前节点不在左右边界之间，我们返回False。最后，我们递归检查当前节点的左子树和右子树，将左子树的右边界设置为当前节点的值，将右子树的左边界设置为当前节点的值。如果两个递归调用都返回True，则返回True。

完整代码

下面是完整的代码，用于查找给定二叉树中是否存在BST：

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

class BinaryTree:
    def __init__(self, root=None):
        self.root = root

    # 前序遍历
    def preorder(self, node):
        if node is not None:
            print(node.value)
            self.preorder(node.left)
            self.preorder(node.right)

    # 中序遍历
   def inorder(self, node):
        if node is not None:
            self.inorder(node.left)
            print(node.value)
            self.inorder(node.right)

    # 后序遍历
    def postorder(self, node):
        if node is not None:
            self.postorder(node.left)
            self.postorder(node.right)
            print(node.value)

class Solution:
    def isValidBST(self, root):
        """
        :type root: TreeNode
        :rtype: bool
        """
        def checkBST(node, left, right):
            if not node:
                return True
            if not left < node.value < right:
                return False
            return checkBST(node.left, left, node.value) and checkBST(node.right, node.value, right)

        return checkBST(root, float('-inf'), float('inf'))

if __name__ == '__main__':
    # 构建二叉树
    root = Node(5)
    root.left = Node(2)
    root.right = Node(6)
    root.left.left = Node(1)
    root.left.right = Node(4)
    root.right.right = Node(7)

    # 判断二叉树是否是BST
    solution = Solution()
    is_BST = solution.isValidBST(root)
    print(is_BST)

在这个程序中，我们首先创建了一棵二叉树，并将它保存为root。然后，我们创建了一个名为solution的Solution对象，并使用它的isValidBST()方法来查找给定二叉树中是否存在BST。最后，我们打印了结果，表示这个二叉树是否是BST。