【模板】二叉搜索树(BST)

题目背景

众所周知,~~二叉搜索树没有任何实际用途~~,so我来出一道模板题给大家练习代码能力……

题目描述

## 前言——BST是啥 BST 二叉搜索树是基于二叉树的一种树,一种特殊的二叉树。 二叉搜索树要么是一颗空树,要么满足一下特点(性质)的二叉树: 1. 它的左子树要么为空,要么它(左子树)的所有节点均小于它的根节点。 1. 它的右子树要么为空,要么它(右子树)的所有节点均大于它的根节点。 1. 它的左、右子树也分别是二叉搜索树。 直观的说,如果中序遍历一棵二叉搜索树,则会产生一个有序数列。 如:![1.PNG](https://i.loli.net/2019/04/20/5cbad7361312f.png),中序遍历会产生序列:1 2 5 6 8 9 ------------ 现在,要你构建一棵BST,资磁:插入、删除、查找、三种遍历。

输入输出格式

输入格式


给出$n$,再给你$n$个数,要你用这$n$个数构建一棵BST,输出它的先序遍历、中序遍历、后序遍历,每个一行。 然后给出$m$,又给你$m$个询问,每个询问对应输出"Yes"/"No"。 最后给出$Q$,并给你$Q$个数,删除这些数**(不保证所有数均已在BST中!输出方法见样例!)**

输出格式


给出$n$,再给你$n$个数,要你用这$n$个数构建一棵BST,输出它的先序遍历、中序遍历、后序遍历,每个一行。 然后给出$m$,又给你$m$个询问,每个询问对应输出"Yes"/"No"。 最后给出$Q$,并给你$Q$个数,删除这些数**(不保证所有数均已在BST中!输出方法见样例!)**

输入输出样例

输入样例 #1

5 
11 10 9 12 3
3
1 11 111
2
1 3

输出样例 #1

11 10 9 3 12 
3 9 10 11 12 
3 9 10 12 11 
No
Yes
No
No number!
3 has now been deleted.
11 10 9 12 
9 10 11 12 
9 10 12 11 

说明

所有数据$>=0,<=32767$ 数据由标程+随机数生成……