4 二叉查找树（BST）5题

sy352: 二叉查找树的建立

https://sunnywhy.com/sfbj/9/4/352

将n个互不相同的正整数先后插入到一棵空的二叉查找树中，求最后生成的二叉查找树的先序序列。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示二叉查找树的结点个数；

第二行 n 个整数 $a_{i} (1 \leq a_{i} \leq 100)$ ，表示插入序列。

输出

输出个整数，表示先序遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
5 2 3 6 1 8

输出

5 2 1 3 6 8

解释

插入的过程如下图所示。

python

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

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

    def insert(self, value):
        if self.root is None:
            self.root = Node(value)
        else:
            self._insert(value, self.root)

    def _insert(self, value, node):
        if value < node.value:
            if node.left is None:
                node.left = Node(value)
            else:
                self._insert(value, node.left)
        else:
            if node.right is None:
                node.right = Node(value)
            else:
                self._insert(value, node.right)

    def preorder(self):
        return self._preorder(self.root)

    def _preorder(self, node):
        if node is None:
            return []
        return [node.value] + self._preorder(node.left) + self._preorder(node.right)

n = int(input().strip())
values = list(map(int, input().strip().split()))
bst = BST()
for value in values:
    bst.insert(value)
print(' '.join(map(str, bst.preorder())))

sy353: 二叉查找树的判定

https://sunnywhy.com/sfbj/9/4/353

现有一棵二叉树的中序遍历序列，问这棵二叉树是否是二叉查找树。

二叉查找树的定义：在二叉树定义的基础上，满足左子结点的数据域小于或等于根结点的数据域，右子结点的数据域大于根结点的数据域。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示二叉查找树的结点个数；

第二行 n 个整数 $a_{i} (1 \leq a_{i} \leq 100)$ ，表示中序遍历序列。数据保证序列元素互不相同。

输出

如果是二叉查找树，那么输出Yes，否则输出No。

样例1

输入

3
1 2 3

输出

Yes

解释

对应的二叉树如下所示，是二叉查找树。

二叉查找树的判定.png

样例2

输入

3
2 1 3

输出

No

解释

对应的二叉树如下所示，不是二叉查找树。

二叉查找树的判定_2.png

python

n = int(input().strip())
sequence = list(map(int, input().strip().split()))

if sequence == sorted(sequence):
    print("Yes")
else:
    print("No")

sy354: 还原二叉查找树

https://sunnywhy.com/sfbj/9/4/354

现有一棵二叉查找树的先序遍历序列，还原这棵二叉查找树，并输出它的后序序列。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示二叉查找树的结点个数；

第二行 n 个整数 $a_{i} (1 \leq a_{i} \leq 100)$ ，表示先序遍历序列。数据保证序列元素互不相同。

输出

输出个整数，表示后序遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
5 2 1 3 6 8

输出

1 3 2 8 6 5

解释

对应的二叉查找树如下所示，后序序列为1 3 2 8 6 5。

还原二叉查找树.png

python

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

class BST:
    def __init__(self, preorder):
        if not preorder:
            self.root = None
        else:
            self.root = self.build(preorder)

    def build(self, preorder):
        if not preorder:
            return None
        root = Node(preorder[0])
        i = 1
        while i < len(preorder) and preorder[i] < root.value:
            i += 1
        root.left = self.build(preorder[1:i])
        root.right = self.build(preorder[i:])
        return root

    def postorder(self):
        return self._postorder(self.root)

    def _postorder(self, node):
        if node is None:
            return []
        return self._postorder(node.left) + self._postorder(node.right) + [node.value]

n = int(input().strip())
preorder = list(map(int, input().strip().split()))
bst = BST(preorder)
print(' '.join(map(str, bst.postorder())))

sy355: 相同的二叉查找树

https://sunnywhy.com/sfbj/9/4/355

将第一组个互不相同的正整数先后插入到一棵空的二叉查找树中，得到二叉查找树；再将第二组个互不相同的正整数先后插入到一棵空的二叉查找树中，得到二叉查找树。判断和是否是同一棵二叉查找树。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示二叉查找树的结点个数；

第二行个 n 个整数 $a_{i} (1 \leq a_{i} \leq 100)$ ，表示第一组插入序列；

第三行个 n 个整数 $b_{i} (1 \leq b_{i} \leq 100)$ ，表示第二组插入序列。

输出

如果是同一棵二叉查找树，那么输出Yes，否则输出No。

样例1

输入

6
5 2 3 6 1 8
5 6 8 2 1 3

输出

Yes

解释

两种插入方式均可以得到下面这棵二叉查找树。

还原二叉查找树.png

样例2

输入

6
5 2 3 6 1 8
5 6 8 3 1 2

输出

No

解释

两种插入方式分别得到下图的两种二叉查找树。

相同的二叉查找树_2.png

先定义了TreeNode类用于表示二叉树的节点，然后定义了insert_into_bst函数用于将一个新值插入到二叉查找树中。build_bst_from_sequence函数接收一个序列，依次调用insert_into_bst来构建出一棵二叉查找树。is_same_tree函数用于比较两棵二叉树是否结构相同（即形状相同且对应位置的节点值相等）。

python

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

def insert_into_bst(root, val):
    if not root:
        return TreeNode(val)
    if val < root.val:
        root.left = insert_into_bst(root.left, val)
    else:
        root.right = insert_into_bst(root.right, val)
    return root

def build_bst_from_sequence(sequence):
    root = None
    for val in sequence:
        root = insert_into_bst(root, val)
    return root

def is_same_tree(p, q):
    if not p and not q:
        return True
    if not p or not q:
        return False
    if p.val != q.val:
        return False
    return is_same_tree(p.left, q.left) and is_same_tree(p.right, q.right)

# 输入处理
n = int(input().strip())
seq1 = list(map(int, input().strip().split()))
seq2 = list(map(int, input().strip().split()))

# 构建二叉查找树
tree1 = build_bst_from_sequence(seq1)
tree2 = build_bst_from_sequence(seq2)

# 判断是否为同一棵树
if is_same_tree(tree1, tree2):
    print("Yes")
else:
    print("No")

sy356: 填充二叉查找树

https://sunnywhy.com/sfbj/9/4/356

现有一棵个结点的二叉树（结点编号为从0到n-1，根结点为0号结点），将个互不相同的正整数填入这棵二叉树结点的数据域中，使其成为二叉查找树。求填充后二叉查找树的先序序列。

输入

第一行一个整数 $n (1 \leq n \leq 50)$ ，表示二叉树的结点个数；

第二行 n 个整数，表示需要填入二叉树中的数 $v a l_{i}$ , 其中填入数字的范围为 $1 \leq v a l_{i} \leq 100$ 。

接下来 n 行，每行一个结点，按顺序给出编号为从0到n-1的个结点的左子结点编号和右子结点编号，中间用空格隔开。如果不存在对应的子结点，那么用-1表示。

输出

输出 n 个整数，表示先序遍历序列，中间用空格隔开，行末不允许有多余的空格。

样例1

输入

6
1 2 3 5 6 8
2 5
-1 -1
1 4
-1 -1
-1 -1
-1 3

输出

5 2 1 3 6 8

解释

下左图为输入的二叉树，填入6个整数后变为下右图的二叉查找树。

填充二叉查找树.png

To solve this problem, you can follow these steps:

Read the input values and the structure of the binary tree.
Sort the input values in ascending order.
Perform an inorder traversal of the binary tree and fill the nodes with the sorted values. This will make the binary tree a binary search tree (BST) because the inorder traversal of a BST is a sorted sequence.
Perform a preorder traversal of the BST and print the result.

Here is the Python code that implements this plan:

python

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

class BST:
    def __init__(self, n):
        self.nodes = [Node() for _ in range(n)]
        self.index = 0

    def insert_values(self, values):
        self.values = iter(sorted(values))
        self._insert_values(self.nodes[0])

    def _insert_values(self, node):
        if node is not None:
            self._insert_values(node.left)
            node.value = next(self.values)
            self._insert_values(node.right)

    def preorder(self):
        return self._preorder(self.nodes[0])

    def _preorder(self, node):
        if node is None:
            return []
        return [node.value] + self._preorder(node.left) + self._preorder(node.right)

n = int(input().strip())
values = list(map(int, input().strip().split()))
bst = BST(n)
for i in range(n):
    left, right = map(int, input().strip().split())
    if left != -1:
        bst.nodes[i].left = bst.nodes[left]
    if right != -1:
        bst.nodes[i].right = bst.nodes[right]
bst.insert_values(values)
print(' '.join(map(str, bst.preorder())))

This code reads the input values and the structure of the binary tree from the input, sorts the input values, fills the nodes of the binary tree with the sorted values, performs a preorder traversal of the BST, and then prints the result.

4 二叉查找树（BST）5题 ​

sy352: 二叉查找树的建立 ​

sy353: 二叉查找树的判定 ​

sy354: 还原二叉查找树 ​

sy355: 相同的二叉查找树 ​

sy356: 填充二叉查找树 ​

4 二叉查找树（BST）5题

sy352: 二叉查找树的建立

sy353: 二叉查找树的判定

sy354: 还原二叉查找树

sy355: 相同的二叉查找树

sy356: 填充二叉查找树