判断是否二叉排序树

一个二叉排序树具有以下几个性质：如果左子树不为空，则左子树上所有节点的值都小于根节点的值；如果右子树不为空，则右子树上所有节点的值都大于根节点的值；左右子树也都是二叉排序树。

通过对给定的二叉树进行中序遍历，并将遍历结果保存在一个数组中，我们可以判断这个数组是否是一个递增序列。如果是，则该二叉树是一个二叉排序树；否则，不是一个二叉排序树。

以下是用Java语言实现中序遍历的代码：

public void inOrder(TreeNode treeNode, List<Integer> list) {
    if (treeNode == null) {
        return;
    }
    inOrder(treeNode.leftChild, list);
    list.add(treeNode.data);
    inOrder(treeNode.rightChild, list);
}

通过调用上述代码，将二叉树的中序遍历结果存储在一个List<Integer>类型的列表中。然后，我们检查列表中的元素是否按照递增的顺序排列。如果是，则该二叉树是一个二叉排序树；否则，不是一个二叉排序树。

相关问题

数据结构二叉排序树

二叉排序树，也称为二叉搜索树（Binary Search Tree，简称BST），是一种特殊的二叉树结构，它具有以下性质：

1. 对于二叉排序树的任意一个非叶子节点，其左子树的所有节点的值都小于该节点的值，右子树的所有节点的值都大于该节点的值。
2. 对于二叉排序树的任意一个节点，其左子树和右子树都是二叉排序树。

下面是一个示例代码，演示了如何构建一个二叉排序树，并进行插入和查找操作：

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

def insert(root, val):
    if root is None:
        return TreeNode(val)
    if val < root.val:
        root.left = insert(root.left, val)
    else:
        root.right = insert(root.right, val)
    return root

def search(root, val):
    if root is None or root.val == val:
        return root
    if val < root.val:
        return search(root.left, val)
    else:
        return search(root.right, val)

# 构建二叉排序树
root = None
values = [5, 3, 8, 2, 4, 7, 9]
for val in values:
    root = insert(root, val)
# 查找节点
target = 4
result = search(root, target)
if result:
    print("找到了节点", target)
else:
    print("未找到节点", target)

这段代码首先定义了一个`TreeNode`类，表示二叉排序树的节点。然后定义了`insert`函数，用于向二叉排序树中插入节点。最后定义了`search`函数，用于在二叉排序树中查找指定的节点。通过构建二叉排序树并进行查找操作，可以实现对数据的快速插入和查找。

数据结构二叉排序树课程设计

二叉排序树是一种特殊的二叉树，它的左子树中的所有节点的值都小于根节点的值，右子树中的所有节点的值都大于根节点的值。因此，二叉排序树的中序遍历结果是一个有序的序列。下面是一个简单的二叉排序树的课程设计：

1.定义二叉排序树的节点类

class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None

2.定义二叉排序树类

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

    # 插入节点
    def insert(self, val):
        if not self.root:
            self.root = TreeNode(val)
        else:
            self._insert(val, self.root)

    def _insert(self, val, node):
        if val < node.val:
            if not node.left:
                node.left = TreeNode(val)
            else:
                self._insert(val, node.left)
        else:
            if not node.right:
                node.right = TreeNode(val)
            else:
                self._insert(val, node.right)

    # 查找节点
    def search(self, val):
        return self._search(val, self.root)

    def _search(self, val, node):
        if not node:
            return False
        elif node.val == val:
            return True
        elif val < node.val:
            return self._search(val, node.left)
        else:
            return self._search(val, node.right)

    # 删除节点
    def delete(self, val):
        self._delete(val, self.root)

    def _delete(self, val, node):
        if not node:
            return node
        if val < node.val:
            node.left = self._delete(val, node.left)
        elif val > node.val:
            node.right = self._delete(val, node.right)
        else:
            if not node.left:
                return node.right
            elif not node.right:
                return node.left
            else:
                temp = self._find_min(node.right)
                node.val = temp.val
                node.right = self._delete(temp.val, node.right)
        return node

    def _find_min(self, node):
        while node.left:
            node = node.left
        return node

    # 中序遍历
    def inorder(self):
        res = []
        self._inorder(self.root, res)
        return res

    def _inorder(self, node, res):
        if not node:
            return
        self._inorder(node.left, res)
        res.append(node.val)
        self._inorder(node.right, res)

3.测试代码

bst = BST()
bst.insert(5)
bst.insert(3)
bst.insert(7)
bst.insert(1)
bst.insert(9)
print(bst.inorder()) # 输出：[1, 3, 5, 7, 9]
bst.delete(3)
print(bst.inorder()) # 输出：[1, 5, 7, 9]
print(bst.search(7)) # 输出：True
print(bst.search(4)) # 输出：False