二叉查找树

一、实验题目

（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));

    }
}