完全二叉搜索树pta

### 完全二叉搜索树的概念 完全二叉搜索树是一种特殊的二叉树结构，它既满足二叉搜索树的性质，又具有完全二叉树的特点。具体来说： - **二叉搜索树特性**：对于任意一个节点，其左子树的所有节点值均小于当前节点值，右子树的所有节点值均大于或等于当前节点值[^3]。 - **完全二叉树特性**：除最后一层外，其余每一层都达到最大宽度；最后一层的节点从最左侧依次排列，无任何空缺[^2]。 要验证一颗二叉搜索树是否为完全二叉树，可以通过以下方式实现： 1. 使用队列进行层次遍历（广度优先搜索）。 2. 在层次遍历时记录第一个非满节点的位置。 3. 若后续存在更靠后的节点，则说明不是完全二叉树。 --- ### 实现方法 以下是基于 Python 的一种实现方案，用于构建并验证完全二叉搜索树： #### 构建二叉搜索树 通过给定的一系列数字顺序插入来构建二叉搜索树。每次插入新节点时，按照二叉搜索树的规则调整位置。 ```python class TreeNode: def __init__(self, val=0): self.val = val self.left = None self.right = None def insert_bst(root, key): if not root: return TreeNode(key) if key < root.val: root.left = insert_bst(root.left, key) elif key >= root.val: root.right = insert_bst(root.right, key) return root ``` #### 层次遍历与完全性检测 利用队列完成层次遍历，并在此过程中检查是否存在不符合完全二叉树特性的节点。 ```python from collections import deque def is_complete_binary_tree(root): if not root: return True queue = deque([root]) met_non_full_node = False # 标记是否遇到过非满节点 while queue: node = queue.popleft() if node: # 当前节点有效 if met_non_full_node: # 已经遇到了非满节点，但仍有新的节点加入队列 return False queue.append(node.left) queue.append(node.right) else: # 遇到了空节点 met_non_full_node = True # 设置标记为已遇非满状态 return True ``` #### 主函数逻辑 将上述功能组合起来形成完整的解决方案。 ```python def main(): n = int(input()) # 节点数量 preorder = list(map(int, input().split()))[:n] # 先序遍历序列 k = int(input()) # 待删除节点的数量 delete_keys = list(map(int, input().split()))[:k] # 删除列表 # 构造BST bst_root = None for value in preorder: bst_root = insert_bst(bst_root, value) # 检查是否为完全二叉树 complete_flag = is_complete_binary_tree(bst_root) # 输出结果 result = [] from collections import deque q = deque([bst_root]) while q: current = q.popleft() if current: result.append(current.val) q.append(current.left) q.append(current.right) else: result.append(None) # 补充占位符以便观察结构 print("Yes" if complete_flag and all(x is not None for x in result[:-result.count(None)]) else "No") # 判断条件 print(' '.join(str(i) for i in result if i is not None)) # 打印层序遍历结果 main() ``` --- ### 解决思路总结 以上代码实现了如下目标： 1. 动态构建二叉搜索树； 2. 基于层次遍历判断是否为完全二叉树； 3. 提供最终的层序遍历结果以及判定结论。 需要注意的是，在实际应用中还需考虑边界情况，比如输入数据异常或者极端情况下性能优化等问题。 --- ###