一、实验题目
（1）实验题目
二叉查找树
（2）问题描述
对于查找集合进行动态查找，为了使得元素的插入、删除和查找操作都能够很快地完成，可以采用二叉查找树作为查找结构。对于给定的查找集合，给出在二叉查找树上进行查找的比较次数。
二、实验内容
（1）设计二叉查找树的存储结构；
（2）用伪代码描述算法，并分析时空性能；
（3）编程实现。
三、数据结构设计
底层使用二叉排序树,根据节点的插入建树,基于查找的方法,进行改进,以满足题目要求.
//使用内部类定义一个节点
static class TreeNode{
public int val ;
public TreeNode left;
public TreeNode right;
public TreeNode(int val) {
this.val = val;
}
//使用接口,定义使用到的方法
public interface IList {
void insert(int val);//节点的插入
int search(int val);//查找
}
四、算法设计
(1)insert(int val) :
需要找到插入的位置:通过循环遍历实现,初始条件为cur = root,结束条件为 cur = null;
如果cur.val < val ,说明根节点的值较小,需要向右子树遍历,即cur = cur.right,
如果cur.val > val ,说明根节点的值较大,需要向左子树遍历,即cur = cur.left;
如果cur.val = val ,说明要插入的节点已经存在,直接返回即可.
经过上面的分析,循环结束,cur =null,显然是不行的,所以要定义一个parent 引用,当cur要移动前,parent指向cur,然后cur再移动 ;
时间复杂度:O(log2 N)
空间复杂度:O(1)
(2)search(int val)
依然采用循环遍历的方式,初始条件为cur = root,结束条件为cur = null,每遍历一次,让计数器++;
时间复杂度:O(log2 N)
空间复杂度:O(1)
五、运行结果
六、程序源码
```cpp```cpp```cpp```cpp//使用接口,定义使用到的方法
public interface IList {void insert(int val);//节点的插入int search(int val);//查找
}
public class BinarySearchTree implements IList {//使用内部类定义一个节点static class TreeNode{public int val ;public TreeNode left;public TreeNode right;public TreeNode(int val) {this.val = val;}}public TreeNode root;public void insert(int val) {TreeNode node = new TreeNode(val);if(root == null){root =node;return;}TreeNode cur = root;TreeNode parent = null;while(cur != null){if(cur.val < val) {parent = cur;cur = cur.right;}else if(cur.val > val){parent = cur;cur =cur.left;}else {//插入元素已经存在,无法插入,直接返回return;}}if(parent.val < val){parent.right = node;}else{parent.left = node;}}public int search(int val){if(root == null){return -1;}int count = 0;//计数器TreeNode cur = root;while(cur != null){if(cur.val < val){cur = cur.right;count++;}else if(cur.val > val){cur = cur.left;count++;}else {count++;return count;}}return -1 ;//没找到返回-1}}
//测试类
public class Test {public static void main(String[] args) {BinarySearchTree binarySearchTree = new BinarySearchTree();System.out.println("请输入二叉排序树的节点个数:");Scanner scanner =new Scanner(System.in);int number = scanner.nextInt();System.out.println("请输入要插入的节点:");for (int i = 0; i < number; i++) {int val = scanner.nextInt();binarySearchTree.insert(val);}System.out.println("请输入要查找的值:");int elem = scanner.nextInt();System.out.print("查找次数: ");System.out.println(binarySearchTree.search(elem));}
}
