[数据结构与算法]二分查找及二叉排序树应用

一、实验目的

1、掌握二分查找算法。
2、掌握二叉排序树的含义及其在计算机中的存储实现。
3、掌握在二叉排序树上查找操作的算法实现。
4、掌握二叉排序树的插入、删除操作的算法实现。
5、在采用二叉排序树为数据结构的学生信息管理系统中实现查找操作（应用性设计内容）。

二、实验内容

1、有序表的二分查找（折半查找）

在顺序表中实现通过对比关键字来查找特定关键字对应信息

说明：顺序表可以使用Java自带的，实验要求的话自己写就行了

1. KeyType类

实现了Comparab 接口，实现了可比较

package Ex1;

import java.security.Key;

public class KeyType implements Comparable<KeyType>{
    //数据类型必须是可比较的
    public int key;
    public KeyType(){
    }

    public KeyType(int key){
        this.key = key;
    }

    //当前对象 key 小于 比较对象 key 返回 -1 ，等于返回 0 ，大于返回 1
    @Override
    public int compareTo(KeyType key2) {
        return (this.key < key2.key ? -1 : (this.key == key2.key ? 0 : 1));
    }
}

2. RecordNode类

存储关键字及关键字对应数据

package Ex1;

//数据节点，成员变量中有KeyType，因此可以通过每个RecordNode中的key实现比较
public class RecordNode /*implements Comparable<RecordNode>*/ {
    public KeyType key;
    public Object element;

    public RecordNode(KeyType key){
        this.key = key;
    }

    public RecordNode(KeyType key,Object element){
        this.key = key;
        this.element = element;
    }

    public String toString(){
        return "["+key.key+","+element+"]";
    }
}

3. 测试

package Ex1;

import java.util.Scanner;

public class BinarySearchTest {

    public static SeqList createSeqList() throws Exception{
        int maxSize = 100;
        SeqList ST = new SeqList(maxSize);
        int curlen;
        Scanner scanner = new Scanner(System.in);
        System.out.println("请输入有效数据长度：");
        curlen = scanner.nextInt();

        KeyType[] k = new KeyType[curlen];
        String[] element = new String[curlen];
        System.out.println("请输入关键字序列及对应元素（可无序）：");
        for (int i = 0;i < curlen;i++) {
            k[i] = new KeyType(scanner.nextInt());
            element[i] = new String(scanner.next());
        }
        for (int i = 0;i < curlen;i++){
            RecordNode recordNode = new RecordNode(k[i],element[i]);
            ST.insert(ST.length(),recordNode);
        }
        return ST;
    }

    public static void main(String[] args) throws Exception {
        SeqList ST = createSeqList();
        System.out.println("请输入查找的关键字：");
        Scanner scanner = new Scanner(System.in);
        KeyType k1 = new KeyType(scanner.nextInt());
        KeyType k2 = new KeyType(scanner.nextInt());
        System.out.println("binarySearch("+k1.key+")="+ ST.binarySearch( k1));
        System.out.println("binarySearch("+k2.key+")="+ST.binarySearch( k2));
    }
}

2、应用性设计实验

编程设计一个简单的学生信息管理系统。每个学生的信息包括学号、姓名、性别、班级和电话等。
实验要求：
⑴ 采用二叉排序树的结构创建学生的信息表。
⑵ 能按照学号或姓名查找学生的信息。如果查找成功，则输出学生的所有信息，否则输入查找失败的提示信息。

说明：重点在于二叉排序树的操作的实现，节点类根据自己所需要解决的问题修改就可以了。

1. 二叉排序树的二叉链表的结点类：

package Stu_Inf_Cul_System;

import Ex1.KeyType;

public class StudentNode {
    public KeyType key;
    public String name;
    public String sex;
    public String banji;
    public String telephone;
    public StudentNode(KeyType key){
        this(key,null,null,null,null);
    }
    public StudentNode(KeyType key,String name,String sex,String banji,String telephone){
        this.key = key;
        this.name = name;
        this.sex = sex;
        this.banji = banji;
        this.telephone = telephone;
    }

    public String toString(){
        return "["+key.key+","+name+","+sex+","+banji+","+telephone+"]";
    }

}

2. 二叉排序树类（查找、插入 、删除、中序遍历等成员函数）：

package Stu_Inf_Cul_System;

import BiTree.BiTreeNode;
import Ex1.*;

public class BSTree {
    public BiTreeNode root;
    public BSTree(){
        root = null;
    }

    //中根遍历以 biTreeNode 节点为根的二叉树
    public void inOrderTraverse(BiTreeNode biTreeNode){
        if (biTreeNode != null){
            inOrderTraverse(biTreeNode.lChild);
            System.out.print(((RecordNode)biTreeNode.data).toString() + " ");
            inOrderTraverse(biTreeNode.rChild);
        }
    }

    //查找关键字值为key的节点，若查找成功，则返回节点值，否则返回null
    public Object searchBST( Comparable key){
        if (key == null || ! (key instanceof Comparable)){
            return null;
        }
        return searchBST(root,key);
    }

    private Object searchBST(BiTreeNode biTreeNode, Comparable key) {
        if (biTreeNode != null){
            if (key.compareTo(((RecordNode) biTreeNode.data).key ) == 0){
                return biTreeNode.data;
            }
            if (key.compareTo(((RecordNode) biTreeNode.data).key) < 0){
                return searchBST(biTreeNode.lChild,key);        //若小于则在左子树查找
            }else {
                return searchBST(biTreeNode.rChild,key);        //若大于则在右子树查找
            }
        }
        return null;
    }

    //若插入成功返回true，否则返回false
    public boolean insertBST(Comparable new_key , Object new_element){
        if (new_key == null || !(new_key instanceof Comparable))    //不能插入空对象或者不能比较大小的对象
            return false;
        if (root == null){
            root = new BiTreeNode(new RecordNode((KeyType) new_key,new_element));
            return true;
        }
        return insertBST(root,new_key,new_element);
    }
    private boolean insertBST(BiTreeNode biTreeNode,Comparable key,Object element){
        if (key.compareTo(((RecordNode)biTreeNode.data).key) == 0)
            return false;
        if (key.compareTo(((RecordNode)biTreeNode.data).key) < 0){
            if (biTreeNode.lChild == null){
                biTreeNode.lChild = new BiTreeNode(new RecordNode((KeyType) key,element));
                return true;
            }else {
                return insertBST(biTreeNode.lChild,key,element);
            }
        }else if (biTreeNode.rChild == null){
            biTreeNode.rChild = new BiTreeNode(new RecordNode((KeyType) key,element));
            return true;
        }else {
            return insertBST(biTreeNode.rChild,key,element);
        }
    }

    public Object removeBFS(Comparable key){
        if (root == null || key == null || !(key instanceof Comparable)){
            return null;
        }
        return removeBFS(root,key,null);
    }
    private Object removeBFS(BiTreeNode biTreeNode,Comparable elemKey,BiTreeNode parent){
        if (biTreeNode != null){
            if (elemKey.compareTo(((RecordNode) biTreeNode.data).key) < 0) {
                return removeBFS(biTreeNode.lChild, elemKey, biTreeNode);
            }else if (elemKey.compareTo(((RecordNode) biTreeNode.data).key) > 0){
                return removeBFS(biTreeNode.rChild,elemKey,biTreeNode);
            }else if (biTreeNode.lChild != null && biTreeNode.rChild != null) {  //当找到被删除关键字切其左右孩子不为空
                BiTreeNode innext = biTreeNode.rChild;
                while(innext.lChild != null){   //找右子树上最小的节点，当然也可以找左子树上最大的节点
                    innext = innext.rChild;
                }
                biTreeNode.data = innext.data;  //用右子树上最小节点替换被删节点
                return removeBFS(biTreeNode.rChild,((RecordNode) biTreeNode.data).key,biTreeNode);  //递归删除节点biTreeNode
            }else{
                //biTreeNode度为1或叶子结点
                if (parent == null){
                    if (biTreeNode.lChild != null){
                        root = biTreeNode.lChild;
                    }else {
                        root = biTreeNode.rChild;
                    }
                    return biTreeNode.data;
                }
                if (biTreeNode == parent.lChild){
                    if (biTreeNode.lChild != null){
                        parent.lChild = biTreeNode.lChild;
                    }else{
                        parent.lChild = biTreeNode.rChild;
                    }
                }else if (biTreeNode.lChild != null){
                    parent.rChild = biTreeNode.lChild;
                }else{
                    parent.rChild = biTreeNode.rChild;
                }
                return biTreeNode.data;     //返回被删除节点
            }
        }
        return null;
    }
}

3. 测试类代码：

package Stu_Inf_Cul_System;

import Ex1.KeyType;

import java.util.Scanner;

public class StudentTest {
    public static void main(String[] args) {
        BSTree bsTree = new BSTree();
        while(true){
            System.out.println("请选择操作：\n" +
                    "1:添加学生信息\n" +
                    "2:查找学生信息\n" +
                    "3:删除学生信息\n" +
                    "4:查看所有学生信息\n" +
                    "5:结束程序");
            Scanner sc = new Scanner(System.in);
            int a = sc.nextInt();
            if (a == 1){
                System.out.println("请分别输入学生ID、姓名、性别、班级、电话：");
                KeyType ID = new KeyType(sc.nextInt());
                String name = sc.next();
                String sex = sc.next();
                String banji = sc.next();
                String telephone = sc.next();
                StudentNode studentNode = new StudentNode(ID,name,sex,banji,telephone);
                bsTree.insertBST(studentNode.key,studentNode);
            }else if (a == 2){
                System.out.println("请输入待查找学生ID：");
                KeyType ID = new KeyType(sc.nextInt());
                if (bsTree.searchBST(ID) == null){
                    System.out.println("没有该学生！");
                }else {
                    System.out.println(bsTree.searchBST(ID));
                }
            }else if (a == 3){
                System.out.println("请输入待删除学生ID：");
                KeyType ID = new KeyType(sc.nextInt());
                bsTree.removeBFS(ID);
            }else if (a == 4){
                bsTree.inOrderTraverse(bsTree.root);
                System.out.println();
            }else if (a == 5){
                System.out.println("程序结束！");
                break;
            }else {
                System.out.println("请输入正确选项！");
            }
        }

    }
}