主观题：二叉搜索树的概念及应用

二叉搜索树是一棵二叉树，可能为空；对于一棵非空的二叉搜索树，请回答以下问题：
（1）一棵非空的二叉搜索树应该满足哪些特征？（7分）
（2）按照输入顺序：30,5,40,2,80,35构造二叉搜索树，这棵树的根节点是什么?（2分）
（3）写出上面构造出二叉搜索树的前序遍历结果。（2分）
（4）二叉搜索树的哪一种遍历结果可以输出所有关键字从小到大的排列？（2分）
（5）二叉搜索树插入和删除的平均时间复杂度是多少？（2分）





answer：评分标准：
（1）特征：每个元素都有一个关键字，并且任意两个元素的关键字都不相同，所有关键字都是唯一的；在根节点的左子树中，元素的关键字（如果有的话）都小于根节点的关键字；在根节点的右子树中，元素的关键字（如果有的话）都大于根节点的关键字；根节点的左右子树也都是二叉搜索树；（7分）
（2）所构造的二叉搜索树的根为30；（2分）
（3）先序（前序）遍历结果：[30，5，2，40，35，80]；（2分）
（4）中序遍历结果可以输出所有关键字从小到大的排列；（2分）
（5）二叉搜索树插入和删除的平均时间复杂度是O(logn);(2分）