精华内容
下载资源
问答
  • 折半查找二叉排序树

    千次阅读 多人点赞 2019-10-10 14:19:28
    从查找过程看,二叉排序树与二分查找相似。就平均时间性能而言,二叉排序树上的查找和二分查找差不多,但不完全一致; 折半查找的性能分析可以用二叉判定树来衡量,平均查找长度和最大查找长度都是O(logn); ...

    1.折半查找和二叉排序树的时间性能分析:

    •  从查找过程看,二叉排序树与二分查找相似。就平均时间性能而言,二叉排序树上的查找和二分查找差不多,但不完全一致;
    • 折半查找的性能分析可以用二叉判定树来衡量,平均查找长度和最大查找长度都是O(logn);
    • 二叉排序树的查找性能与数据的输入顺序有关,最好情况下的平均查找长度与折半查找相同,但最坏情况时,即形成单支树时,其查找长度为O(n)。
    • 折半查找的判定树唯一,而二叉排序树不唯一,相同的关键字其插入顺序不同可能生成不同的二叉排序树。

    2.就维护表的有序性而言,二叉排序树无需移动节点,只需修改指针即可完成插入和删除操作,平均执行时间是O(logn)。二分查找的对象是有序顺序表,若有插入和删除结点的操作,所花的代价是O(n)。

    3.当有序表是静态查找表时,宜用顺序表作为其存储结构,而采用二分查找实现其查找操作;若有序表是动态查找表,则应选择二叉排序树作为其逻辑结构。

    4.折半查找过程所对应的判定树是一棵平衡二叉树:每次把一个数组从中间分割时,总是把数组分为结点数相差最多不超过1的两个子数组,从而使得对应的判定树的两颗子树高度差绝对值不超过1。

    展开全文
  • 折半查找二叉排序树的建立、查找删除、链式哈希表的建立查找: 1————建立有序表———— 2————折半查找————— 3————建立二叉排序树—— 4————二叉排序树查找—— 5————二叉排序树...
  • 实验:实现顺序查找,折半查找二叉排序树,哈希表实验原理:
  • 顺序查找表 二分查找表 折半查找二叉排序树 C#源代码 注意二叉排序树只实现了查找和插入算法,使用Visual Studio 2008开发
  • 数据结构中的单链表;二叉树遍历;折半查找;二叉排序树;内部排序。有具体实现代码。
  • 3、熟悉二叉排序树的特点,掌握二叉排序树的插入、删除操作。 二、实验内容 1、设有关键字序列k={ 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 },查找key=21和key=25的数据元素。 2、根据关键字序列{45、24、53、12、37、93}...

    文中内容来源于《数据结构 --Java语言描述》(第二版) 刘小晶 杜选 主编
    此系列文章作为学校实验记录,若文中内容有误,请大家指出,谢谢

    一、实验目的

    1、掌握查找的特点。
    2、掌握折半查找的基本思想及其算法。
    3、熟悉二叉排序树的特点,掌握二叉排序树的插入、删除操作。

    二、实验内容

    1、设有关键字序列k={ 5 ,14 ,18 ,21 ,23 ,29 ,31 ,35 },查找key=21和key=25的数据元素。
    2、根据关键字序列{45、24、53、12、37、93}构造二叉排序树,并完成插入13删除关键字53和24的操作。

    三、实验步骤

    1、折半查找
    (1)从键盘输入上述8个整数5 ,14 ,18 ,21 ,23 ,29 ,31 ,35,存放在数组bub[8]中,并输出其值。
    (2)从键盘输入21,查找是否存在该数据元素,若存在,则输出该数据元素在表中的位置,否则给出查找失败的信息。
    (3)从键盘输入25,查找是否存在该数据元素,若存在,则输出该数据元素在表中位置,否则给出查找失败的信息。
    2、二叉排序树
    (1)二叉排序树存储定义
    (2)从键盘上输入六个整数45、24、53、12、37、9构造二叉排序树
    (3)输出其中序遍历结果。
    (4)插入数据元素13,输出其中序遍历结果。
    (5)删除数据元素24和53,输出其中序遍历结果。

    源代码

    //顺序表记录结点类
    package ch7;
    public class ElementType {
        public Object data;
    
        public ElementType(Object data) {
            this.data = data;
        }
        public ElementType() {
        }
        public String toString() {
            return (String)data;
        }
    }
    
    
    //顺序表记录关键字类
    package ch7;
    public class KeyType implements Comparable<KeyType> {
        public int key;
        public KeyType() {
    
        }
        public KeyType(int key) {
            this.key = key;
        }
        public String toString() {
            return key + "";
        }
        //覆盖Comparable接口中比较关键字大小的方法
        public int compareTo(KeyType another) {
            int thisVal = this.key;
            int anotherVal = another.key;
            if(thisVal<anotherVal) {
                return -1;
            } else {
                if(thisVal == anotherVal) {
                    return 0;
                } else {
                    return 1;
                }
            }
        }
    }
    
    
    //待排序的顺序表记录类
    package ch7;
    public class RecordNode {
        public Comparable key;
        public Object element;
        public RecordNode(Comparable key) {
            this.key = key;
        }
        public RecordNode(Comparable key,Object element) {
            this.key = key;
            this.element = element;
        }
        public String toString() {
            return "[" + key + "]";
        }
    }
    
    
    //待排序的顺序表类
    package ch7;
    import java.util.Scanner;
    public class SeqList {
        public RecordNode[] r;//顺序表记录结点数组
        public int curlen;//顺序表长度,即记录个数
        //顺序表的构造方法,构造一个存储空间容量为maxSize的顺序表
        public SeqList(int maxSize) {
            this.r = new RecordNode[maxSize];
            this.curlen = 0;
        }
        //在当前顺序表的第i个结点之前插入一个RecordNode类型的结点x
        public void insert(int i,RecordNode x) throws Exception{
            if(curlen == r.length) {
                throw new Exception("顺序表已满!");
            }
            if(i<0 || i>curlen) {
                throw new Exception("插入位置不合法!");
            }
            for (int j = curlen; j > i; j--) {
                r[j] = r[j - 1];//插入位置及之后的数据元素后移
            }
            r[i] = x;//插入x
            this.curlen++;//表长度增1
        }
    /*
    二分查找的递归写法
    public int binarySearchDG(int low,int high,Comparable key) {
        int mid;
        if(low<=high) {
            mid = low + high;
            if(r[mid].key.compareTo(key)>0) {
                return binarySearchDG(low,mid - 1,key);
            } else if(r[mid].key.compareTo(key)<0) {
                return binarySearchDG(mid + 1,high,key);
            } else {
                return mid;
            }
        }
        return -1;
    }
    */
    
        public int binarySearch(Comparable key) {
            if(curlen>0) {
                int low = 0,high = curlen - 1;//查找范围上下界
                while(low<=high) {
                    int mid = (low + high)/2;//中间位置,当前比较的数据元素位置
                    if(r[mid].key.compareTo(key) == 0) {
                        System.out.print("查找成功!");
                        return mid;//查找成功
                    } else if(r[mid].key.compareTo(key)>0) {//给定值更小
                        high = mid -1;//查找范围缩小到前半段
                    } else {
                        low = mid + 1;//查找范围缩小到后半段
                    }
                }
            }
            System.out.print("查找失败!");
            return -1;//查找不成功
        }
        //创建查找表,
        public static SeqList ST = null;//使查找表公开,这样才能在测试类中调用
        public static void createSearchList() throws Exception {
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入查找表预分配空间的大小:");
            int maxSize = sc.nextInt();
            ST = new SeqList(maxSize);
            System.out.println("请输入关键字表长:");
            int kLength = sc.nextInt();
            KeyType[] k = new KeyType[kLength];
            System.out.println("请输入关键字:");
            for (int i = 0; i < kLength; i++) {
                k[i] = new KeyType(sc.nextInt());
            }
            for (int i = 0; i < kLength; i++) {
                RecordNode r = new RecordNode(k[i]);
                ST.insert(ST.curlen,r);
            }
        }
    }
    
    
    package ch9;
    import ch7.*;
    import ch7.RecordNode;
    import ch5.BiTreeNode;//二叉树的二叉链表结点类
    public class BSTree {//二叉排序树类
        public BiTreeNode root;//根结点
        public BSTree() {//构造空二叉排序树
            root = null;
        }
        //中根次序遍历以p结点为根的二叉树
        public void inOrderTraverse(BiTreeNode p) {
            if(p != null) {
                inOrderTraverse(p.lchild);
                System.out.print(((RecordNode)p.data).toString() + "");
                inOrderTraverse(p.rchild);
            }
        }
        //查找关键字为key的结点,成功返回结点值,失败返回null
        public Object searchBST(Comparable key) {
            if(key == null || !(key instanceof Comparable)) {
                System.out.println("查找"+key+"失败!");
                return null;
            }
            return searchBST(root , key);
        }
        //二叉排序树查找的递归算法
        //在二叉排序树中查找关键字值为key的结点,成功返回结点值,否则返回null
        private Object searchBST(BiTreeNode p,Comparable key) {
            if(p != null) {
                if(key.compareTo(((RecordNode)p.data).key) == 0) {
                    System.out.print("查找"+key+"成功!");
                    return p.data;
                }
                if(key.compareTo(((RecordNode)p.data).key) < 0) {
                    return searchBST(p.lchild,key);//左子树查找
                } else {
                    return searchBST(p.rchild,key);//右子树查找
                }
            }
            return null;
        }
        //在二叉排序树中插入关键字值为key,数据元素为theElement的新结点
        //插入成功返回true,失败返回false
        public boolean insertBST(Comparable key,Object theElement) {
            //不能插入空对象或不可比较大小的对象
            if(key == null || !(key instanceof Comparable)) {
                System.out.println("插入"+key+"失败!");
                return false;
            }
            if(root == null) {
                root = new BiTreeNode(new RecordNode(key,theElement));
                System.out.println("插入"+key+"成功!");
                return true;
            }
            return insertBST(root,key,theElement);
        }
        //将关键字值为key,数据元素为theElement的结点插入到以p为根的二叉排序树中的递归算法
        private boolean insertBST(BiTreeNode p, Comparable key, Object theElement) {
            if(key.compareTo(((RecordNode)p.data).key) == 0) {
                System.out.println("插入"+key+"失败!");
                return false;//不插入关键字值重复的结点
            }
            if(key.compareTo(((RecordNode)p.data).key) < 0) {
                if(p.lchild == null) {
                    p.lchild = new BiTreeNode(new RecordNode(key,theElement));
                    System.out.println("插入"+key+"成功!");
                    return true;
                } else {
                    return insertBST(p.lchild,key,theElement);
                }
            } else if(p.rchild ==null){
                p.rchild = new BiTreeNode(new RecordNode(key,theElement));
                System.out.println("插入"+key+"成功!");
                return true;
            } else {
                return insertBST(p.rchild,key,theElement);
            }
        }
        //二叉排序树中删除一个结点,若成功则返回被删除结点,否则返回null
        public Object removeBST(Comparable key) {
            if(root == null || key == null || !(key instanceof Comparable)) {
                System.out.println("删除"+key+"失败!");
                return null;
            }
            //在以root为根的二叉树中删除关键字值为elemKey的结点
            return removeBST(root,key,null);
        }
        //在以p为根的二叉排序树中删除关键字为elemKey的结点,parent是p的父结点,采用递归算法
        private Object removeBST(BiTreeNode p, Comparable elemKey, BiTreeNode parent) {
            if(p != null) {
                if(elemKey.compareTo(((RecordNode)p.data).key) < 0) {
                    return removeBST(p.lchild,elemKey,p);
                } else if(elemKey.compareTo(((RecordNode)p.data).key) > 0) {
                    return removeBST(p.rchild,elemKey,p);
                } else if(p.lchild != null && p.rchild != null) {
                    BiTreeNode innext = p.rchild;//寻找p在中根次序下的后继结点innext
                    while(innext.lchild != null) {// 寻找左子树中的最左孩子
                        innext = innext.lchild;
                    }
                    p.data = innext.data;//用后继结点代替p
                    return removeBST(p.rchild,((RecordNode)p.data).key,p);//递归删除结点p
                } else {//p是1度和叶子结点
                    if(parent == null) {//删除根结点,p = root
                        if(p.lchild != null) {
                            root = p.lchild;
                        } else {
                            root = p.rchild;
                        }
                        System.out.println("删除"+elemKey+"成功!");
                        return p.data;//返回被删除的结点p
                    }
                    if(p == parent.lchild) {//p是parent的左孩子
                        if(p.lchild != null) {
                            parent.lchild = p.lchild;//以p的左子树填充
                        } else {
                            parent.lchild = p.rchild;
                        }
                    } else if(p.lchild != null) {//p是parent的右孩子且p的左子树非空
                        parent.rchild = p.lchild;
                    } else {
                        parent.rchild = p.rchild;
                    }
                    System.out.println("删除"+elemKey+"成功!");
                    return p.data;
                }
            }
            System.out.println("删除"+elemKey+"失败!");
            return null;
        }
    
    }
    
    
    package ch9;
    import ch7.KeyType;
    import java.util.Scanner;
    import static ch7.SeqList.*;
    public class BinarySearchTest {
        public static void main(String[] args) throws Exception{
            int sum;
            createSearchList();
            System.out.println("请输入要查找的关键字个数:");
            Scanner sc = new Scanner(System.in);
            sum = sc.nextInt();
            System.out.println("请输入要查找的关键字:");
            while(sum>0) {
                KeyType key = new KeyType(sc.nextInt());
                System.out.println(key.key + "下标为:" + ST.binarySearch(key));
                sum--;
            }
        }
    }
    
    
    package ch9;
    import ch7.KeyType;
    import java.util.Scanner;
    public class BSTreeTest {
        public static void main(String[] args) {
            BSTree bstree = new BSTree();
            Scanner sc = new Scanner(System.in);
            System.out.println("请输入关键字的个数:");
            int kLength = sc.nextInt();
            int[] k = new int[kLength];
            KeyType[] key = new KeyType[k.length];
            System.out.println("请输入关键字:");
            for (int i = 0; i < kLength; i++) {
                k[i] = sc.nextInt();
            }
            for (int i = 0; i < k.length; i++) {
                key[i] = new KeyType(k[i]);
                bstree.insertBST(key[i],null);
    
            }
    
            System.out.println("\n中序遍历二叉排序树:");
            bstree.inOrderTraverse(bstree.root);
            System.out.println();
            System.out.println();
    
            KeyType keyvalue;
            System.out.println("请输入要添加的关键码的个数:");
            int sum = sc.nextInt();
            System.out.println("请输入要添加的关键码:");
            while(sum>0) {
                keyvalue = new KeyType(sc.nextInt());
                bstree.insertBST(keyvalue,null);
                System.out.println("添加关键码:" + keyvalue + "后的中序遍历序列:");
                bstree.inOrderTraverse(bstree.root);
                System.out.println();
                sum--;
            }
    
            System.out.println("请输入要删除的关键码个数:");
            sum = sc.nextInt();
            System.out.println("请输入要删除的关键码:");
            while(sum>0) {
                keyvalue = new KeyType(sc.nextInt());
                bstree.removeBST(keyvalue);
                System.out.println("删除关键码:" + keyvalue + "后的中序遍历序列:");
                bstree.inOrderTraverse(bstree.root);
                System.out.println();
                sum--;
            }
        }
    }
    
    

    运行结果

    BinarySearchTest.java
    请输入查找表预分配空间的大小:
    20
    请输入关键字表长:
    8
    请输入关键字:
    5 14 18 21 23 29 31 35
    请输入要查找的关键字个数:
    2
    请输入要查找的关键字:
    21 25
    查找成功!21下标为:3
    查找失败!25下标为:-1
    
    Process finished with exit code 0
    
    BSTreeTest.java
    请输入关键字的个数:
    6
    请输入关键字:
    45 24 53 12 37 9
    插入45成功!
    插入24成功!
    插入53成功!
    插入12成功!
    插入37成功!
    插入9成功!
    
    中序遍历二叉排序树:
    [9][12][24][37][45][53]
    
    请输入要添加的关键码的个数:
    1
    请输入要添加的关键码:
    13
    插入13成功!
    添加关键码:13后的中序遍历序列:
    [9][12][13][24][37][45][53]
    请输入要删除的关键码个数:
    2
    请输入要删除的关键码:
    24 53
    删除37成功!
    删除关键码:24后的中序遍历序列:
    [9][12][13][37][45][53]
    删除53成功!
    删除关键码:53后的中序遍历序列:
    [9][12][13][37][45]
    
    Process finished with exit code 0
    
    
    展开全文
  • 数据结构课程设计-综合查找算法(顺序查找、折半查找二叉排序树、哈希表) 可以在Microsoft Visual C++ 上运行没有错误 包括论文word文档,答辩的ppt等
  • 折半查找与二叉查找

    万次阅读 2016-02-17 18:03:09
    折半查找二叉查找的效率均高于顺序查找,在本文构建的折半查找与二叉查找在生活中的应用也是十分广泛。

    在生活当中,我们可能每天都要进行查找工作,字典中查找,搜索引擎中查找,数据库中进行查找。在这个信息的时代下,我们每天都要从互联网上接触到很多信息。这些信息从哪里来,当然是保存在数据库中。提到数据库,大家首先想到的肯定是索引,是的数据库的优劣很大是与索引相关。而索引是为了什么,就是为了方便查找,快速从数据库中提取我们想要的数据,对于索引的优化也是一个难点。下面笔者就来介绍一下折半查找和建立二叉查找树进行查找。

    折半查找:

    大家知道,顺序查找(线性查找)是从线性表中的一端到另一端逐个进行比较,当数据非常大时,查找效率非常低,时间复杂度为O(n),但是它对记录的存储没有任何要求(记录不必有序)。

    折半查找:必须要求记录有序,采用顺序存储,利用这个特点,所以折半查找的效率也比顺序查找高,对于数量非常大时,非常快,时间复杂度为O(logN)。

    基本思想:(1)在有序数据中,去中间的记录作为比较对象,若给定的值与中间记录相等,则查找成功。  

        (2) 若给定的值小于中间记录,则在中间记录的左半区进行查找。

        (3) 若给定的值大于中间记录,则在中间记录的右半区进行查找。

        (4) 重复以上步骤,直到查找成功,若查找的区域无记录,则查找失败。

    下面笔者定义了一个折半查找的类: 使用数字进行存储数据。

    	private Object[] array;
    	private int size;  // 数组的大小
    
    	private BinarySearch(int max) {  //通过构造函数初始化数组的大小
    		array = new Object[max];
    		size = 0;
    	}
    插入数据: 由于折半查找要求数据必须有序,并且插入操作往往比查找操作频率更加小。所以在插入时就对数据进行排序。
    	/**  插入元素
    	 */
    	@SuppressWarnings("unchecked")
    	public void insert(T value) {
    		int pos = 0;
    		while(pos < size){
    			if (((Comparable<? super T>) array[pos]).compareTo(value) > 0)
    				break;
    			pos++;
    		}
    		
    		for (int k = size; k > pos; k--) {  //将比插入值大的元素后移
    			array[k] = array[k - 1];
    		}
    		array[pos] = value;
    		size++;
    	}

    折半查找: 这里使用的是 递归进行查找,时间复杂度为O(logN)。
    	public int find(T searchKey) {
    		return reFind(searchKey, 0, size - 1);
    	}
    
    	/**
    	 * 通过将关键字与查找部分的中间元素比较,并调用自身实现递归调用,直到找到关键字
    	 * 
    	 * @param searchKey 需要寻找的关键字
    	 * @param lower 查找部分的开始
    	 * @param upper 查找部分的结尾
    	 * @return  成功找到返回关键字位置,失败则返回 -1
    	 */
    	@SuppressWarnings("unchecked")
    	public int reFind(T searchKey, int lower, int upper) {
    		int current;
    		current = (lower + upper) / 2;
    		if (array[current] == searchKey) { // 找到关键字直接返回关键字位置
    			return current;
    		} else if (lower > upper) { // lower、upper交错,不能找到,直接返回数组大小
    			return -1;
    		} else {
    			if (((Comparable<? super T>) array[current]).compareTo(searchKey) < 0) { // 关键字在小于 array[current] 的一半查找
    				return reFind(searchKey, current + 1, upper);
    			} else {
    				return reFind(searchKey, lower, current - 1); // 关键字在大于array[current]的一半查找
    			}
    		}
    	}

    测试:
    package org.TT.Recursion;
    
    import java.util.Scanner;
    
    /** 使用递归进行二分查找。
     *    递归的二分查找代码简洁,时间复杂度为O(logN)
     */
    public class BinarySearch<T extends Comparable<? super T>> {
    
    	// 这里的数组需要已经排好序,在插入时就直接排序
    	private Object[] array;
    	private int size;  // 数组的大小
    
    	private BinarySearch(int max) {  //通过构造函数初始化数组的大小
    		array = new Object[max];
    		size = 0;
    	}
    
    	/** 取得查找数组的大小
    	 */
    	public int size() {
    		return size;
    	}
    
    	public int find(T searchKey) {
    		return reFind(searchKey, 0, size - 1);
    	}
    
    	/**
    	 * 通过将关键字与查找部分的中间元素比较,并调用自身实现递归调用,直到找到关键字
    	 * 
    	 * @param searchKey 需要寻找的关键字
    	 * @param lower 查找部分的开始
    	 * @param upper 查找部分的结尾
    	 * @return  成功找到返回关键字位置,失败则返回 -1
    	 */
    	@SuppressWarnings("unchecked")
    	public int reFind(T searchKey, int lower, int upper) {
    		int current;
    		current = (lower + upper) / 2;
    		if (array[current] == searchKey) { // 找到关键字直接返回关键字位置
    			return current;
    		} else if (lower > upper) { // lower、upper交错,不能找到,直接返回数组大小
    			return -1;
    		} else {
    			if (((Comparable<? super T>) array[current]).compareTo(searchKey) < 0) { // 关键字在小于 array[current] 的一半查找
    				return reFind(searchKey, current + 1, upper);
    			} else {
    				return reFind(searchKey, lower, current - 1); // 关键字在大于array[current]的一半查找
    			}
    		}
    	}
    
    	/**  插入元素
    	 */
    	@SuppressWarnings("unchecked")
    	public void insert(T value) {
    		int pos = 0;
    		while(pos < size){
    			if (((Comparable<? super T>) array[pos]).compareTo(value) > 0)
    				break;
    			pos++;
    		}
    		
    		for (int k = size; k > pos; k--) {  //将比插入值大的元素后移
    			array[k] = array[k - 1];
    		}
    		array[pos] = value;
    		size++;
    	}
    
    	/**
    	 *  展示需要查找的所有数组值
    	 */
    	public void dispaly() {
    		for (int i = 0; i < size; i++) {
    			System.out.print(array[i] + " ");
    		}
    	}
    
    	@SuppressWarnings("resource")
    	public static void main(String[] args) {
    		Scanner in = new Scanner(System.in);
    
    		BinarySearch<Integer> search = new BinarySearch<>(10);
    		search.insert(10);
    		search.insert(90);
    		search.insert(80);
    		search.insert(50);
    		search.insert(30);
    		search.insert(20);
    		search.insert(40);
    		search.insert(700);
    		
    		System.out.print("数组元素为: ");
    		search.dispaly();
    
    		System.out.println();
    		System.out.print("请输入需要查找的元素:");
    		int searchNum = in.nextInt();
    		if (search.find(searchNum) != -1) {
    
    			System.out.println("Found: " + searchNum);
    		} else {
    			System.out.println("Can't find " + searchNum);
    		}
    	}
    
    }
    
    测试


    建立二叉查找树进行查找


    二叉查找树:
    性质: 若它的左子树不为空,则左子树上所有节点的值均小于根节点;   若它的子树不为空,则子树上所有节点的值均小于根节点; 它的左右子树都是二叉查找树。

    首先构造一个结点类,存储数据,并且有左孩子,右孩子的引用。在这里属性不设置成私有主要是为了便于访问,若想设为私有属性,可以设置get 、set方法访问。

    package org.TT.BinarySeachTree;
    
    
    /**结点数据结构*/  
    public class BinaryNode<T>{  
           T data;  
           BinaryNode<T> left;  
           BinaryNode<T> right;  
           public BinaryNode(T data) {  
               this(data,null,null);  
           }  
           public BinaryNode( T data, BinaryNode<T> left, BinaryNode<T> right) {  
               this.data =data;  
               this.left = left;  
               this.right =right;  
           }  
     }

    查找树: 只已知一个根节点,构造函数初始化一棵空树。

    判断是否为空:直接判断根节点是否为空。

     清除树,直接将根节点的应用置为空即可,虚拟机可进行垃圾回收是发现引用为空,将进行垃圾回收。

    <span style="white-space:pre">	</span>private BinaryNode<T> rootTree;
    
    
    <span style="white-space:pre">	</span>/** 构造一颗空的二叉查找树 */
    <span style="white-space:pre">	</span>public BinarySearchTree() {
    <span style="white-space:pre">		</span>rootTree = null;
    <span style="white-space:pre">	</span>}
    
    
    <span style="white-space:pre">	</span>/** 清空二叉查找树 */
    <span style="white-space:pre">	</span>public void clear() {
    <span style="white-space:pre">		</span>rootTree = null;
    <span style="white-space:pre">	</span>}
    
    
    <span style="white-space:pre">	</span>/** 判断是否为空 */
    <span style="white-space:pre">	</span>public boolean isEmpty() {
    <span style="white-space:pre">		</span>return rootTree == null;
    <span style="white-space:pre">	</span>}

    插入: 每次插入寻找正确的位置并插入,保证插入后还是一棵二叉查找树。

    	/** 插入元素 */
    	public void insert(T t) {
    		rootTree = insert(t, rootTree); // 第一次插入时,直接创建新节点并赋值给根节点
    	}
    
    	/** 在某个位置开始判断插入元素,采用递归实现不断寻找插入位置,代码简洁*/
    	public BinaryNode<T> insert(T t, BinaryNode<T> parent) {
    		if (parent == null) {
    			return new BinaryNode<T>(t, null, null);  // 创建一个新节点
    		}
    		int result = t.compareTo(parent.data);  //若 t 小于 parent 返回负数, 大于返回正数,等于返回0
    		if (result < 0)   
    			parent.left = insert(t, parent.left);
    		else if (result > 0)
    			parent.right = insert(t, parent.right);
    		else
    			;// 若两个元素相等,什么也做,如果有需要可以在节点记录里附加域来指示重复元素插入的信息
    		return parent;
    	}
    插入过程: 插入过程

    查找: 每次查找与根结点比较,(1)相等则返回   (2)小于,在左子树中查找   (3)大于,在右子树中查找

    	/** 查找指定的元素,默认从根结点出开始查询 */
    	public boolean find(T t) {
    		return find(t, rootTree);
    
    	}
    
    	/** 从某个结点出开始查找元素,
    	 * 用递归实现并不断将关键字与父节点比较,大于往右子树走,小于往左子树走等于返回 */
    	public boolean find(T t, BinaryNode<T> node) {
    		if (node == null)
    			return false;
    		int result = t.compareTo(node.data);  
    		if (result > 0)
    			return find(t, node.right);
    		else if (result < 0)
    			return find(t, node.left);
    		else
    			return true;
    	}
    查找最大值、最小值:  若查找最小值,直接在左子树上查找,一直往左查找。 若查找最大值,直接在右子树上查找,一直往右查找。 
    	/** 查找二叉查找树中的最小值 */
    	public T findMin() {
    		if (isEmpty()) {
    			System.out.println("二叉树为空");
    			return null;
    		} else
    			return findMin(rootTree).data;
    
    	}
    
    	/** 查找出最小元素所在的结点 */
    	public BinaryNode<T> findMin(BinaryNode<T> node) {
    		if (node == null)
    			return null;
    		else if (node.left == null)
    			return node;
    		return findMin(node.left);// 尾递归查找
    	}
    
    	/** 查找二叉查找树中的最大值 */
    	public T findMax() {
    		if (isEmpty()) {
    			System.out.println("二叉树为空");
    			return null;
    		} else
    			return findMax(rootTree).data;
    	}
    
    	/** 查找出最大元素所在的结点 */
    	public BinaryNode<T> findMax(BinaryNode<T> node) {
    		if (node != null) {
    			while (node.right != null)
    				node = node.right;
    		}
    		return node;
    	}
    删除: 删除结点才用递归实现。

    (1) 删除结点是叶子节点,直接删除 。

    (2)只有左子树、右子树,只需重新连接。

    (3)删除有两个孩子的节点:用右子树最小节点代替删除节点,并删除右子树最小节点

    	/** 删除元素 */
    	public void remove(T t) {
    		rootTree = remove(t, rootTree);
    	}
    
    	/** 在某个位置开始判断删除某个结点,同样用递归实现 */
    	public BinaryNode<T> remove(T t, BinaryNode<T> node) {
    		if (node == null)
    			return node;
    		int result = t.compareTo(node.data);
    		if (result > 0)
    			node.right = remove(t, node.right);
    		else if (result < 0)
    			node.left = remove(t, node.left);
    		else if (node.left != null && node.right != null) { 
    			// 删除有两个孩子的节点:用右子树最小节点代替删除节点,并删除右子树最小节点
    			node.data = findMin(node.right).data;   // 找到删除节点右子树的最小节点
    			node.right = remove(node.data, node.right); // 删除右子树最小节点
    		} else  
    			node = (node.left != null) ? node.left : node.right;
    		//删除没有子节点的节点(叶子)和只有一个节点的节点
    		return node;
    	}

    遍历及测试:
    package org.TT.BinarySeachTree;
    
    /**
     * 二叉查找树的性质:
     *  1.对于树中的每个节点X,它的左子树中所有项的值小于X,而它的右子树中所有项的值大于X, 
     *  		Java实现二叉查找树(递归的编写二叉查找树的各种操作) 
     *    2.树的所有节点的平均深度为 O(logN) 
     *    3.所有操作的平均运行时间也是 O(logN)
     *    4.此处的操作:插入结点,构造二叉查找树、清空二叉树、判断树是否为空、查找指定结点、删除结点、查找最大值、查找最小值
     */
    public class BinarySearchTree<T extends Comparable<? super T>> {
    
    	private BinaryNode<T> rootTree;
    
    	/** 构造一颗空的二叉查找树 */
    	public BinarySearchTree() {
    		rootTree = null;
    	}
    
    	/** 清空二叉查找树 */
    	public void clear() {
    		rootTree = null;
    	}
    
    	/** 判断是否为空 */
    	public boolean isEmpty() {
    		return rootTree == null;
    	}
    	
    	/** 插入元素 */
    	public void insert(T t) {
    		rootTree = insert(t, rootTree); // 第一次插入时,直接创建新节点并赋值给根节点
    	}
    
    	/** 在某个位置开始判断插入元素,采用递归实现不断寻找插入位置,代码简洁*/
    	public BinaryNode<T> insert(T t, BinaryNode<T> parent) {
    		if (parent == null) {
    			return new BinaryNode<T>(t, null, null);  // 创建一个新节点
    		}
    		int result = t.compareTo(parent.data);  //若 t 小于 parent 返回负数, 大于返回正数,等于返回0
    		if (result < 0)   
    			parent.left = insert(t, parent.left);
    		else if (result > 0)
    			parent.right = insert(t, parent.right);
    		else
    			;// 若两个元素相等,什么也做,如果有需要可以在节点记录里附加域来指示重复元素插入的信息
    		return parent;
    	}
    	
    	/** 查找指定的元素,默认从根结点出开始查询 */
    	public boolean find(T t) {
    		return find(t, rootTree);
    
    	}
    
    	/** 从某个结点出开始查找元素,
    	 * 用递归实现并不断将关键字与父节点比较,大于往右子树走,小于往左子树走等于返回 */
    	public boolean find(T t, BinaryNode<T> node) {
    		if (node == null)
    			return false;
    		int result = t.compareTo(node.data);  
    		if (result > 0)
    			return find(t, node.right);
    		else if (result < 0)
    			return find(t, node.left);
    		else
    			return true;
    	}
    
    	/** 查找二叉查找树中的最小值 */
    	public T findMin() {
    		if (isEmpty()) {
    			System.out.println("二叉树为空");
    			return null;
    		} else
    			return findMin(rootTree).data;
    
    	}
    
    	/** 查找出最小元素所在的结点 */
    	public BinaryNode<T> findMin(BinaryNode<T> node) {
    		if (node == null)
    			return null;
    		else if (node.left == null)
    			return node;
    		return findMin(node.left);// 尾递归查找
    	}
    
    	/** 查找二叉查找树中的最大值 */
    	public T findMax() {
    		if (isEmpty()) {
    			System.out.println("二叉树为空");
    			return null;
    		} else
    			return findMax(rootTree).data;
    	}
    
    	/** 查找出最大元素所在的结点 */
    	public BinaryNode<T> findMax(BinaryNode<T> node) {
    		if (node != null) {
    			while (node.right != null)
    				node = node.right;
    		}
    		return node;
    	}
    
    	/** 删除元素 */
    	public void remove(T t) {
    		rootTree = remove(t, rootTree);
    	}
    
    	/** 在某个位置开始判断删除某个结点,同样用递归实现 */
    	public BinaryNode<T> remove(T t, BinaryNode<T> node) {
    		if (node == null)
    			return node;
    		int result = t.compareTo(node.data);
    		if (result > 0)
    			node.right = remove(t, node.right);
    		else if (result < 0)
    			node.left = remove(t, node.left);
    		else if (node.left != null && node.right != null) { 
    			// 删除有两个孩子的节点:用右子树最小节点代替删除节点,并删除右子树最小节点
    			node.data = findMin(node.right).data;   // 找到删除节点右子树的最小节点
    			node.right = remove(node.data, node.right); // 删除右子树最小节点
    		} else  
    			node = (node.left != null) ? node.left : node.right;
    		//删除没有子节点的节点(叶子)和只有一个节点的节点
    		return node;
    	}
    
    	/** 前序遍历 */
    	public void preOrder(BinaryNode<T> node) {
    		if (node != null) {
    			System.out.print(node.data + ",");
    			preOrder(node.left);
    			preOrder(node.right);
    		}
    	}
    
    	/** 后序遍历 */
    	public void postOrder(BinaryNode<T> node) {
    		if (node != null) {
    			postOrder(node.left);
    			postOrder(node.right);
    			System.out.print(node.data + ",");
    		}
    	}
    
    	/** 中序遍历 */
    	public void inOrder(BinaryNode<T> node) {
    		if (node != null) {
    			inOrder(node.left);
    			System.out.print(node.data + ",");
    			inOrder(node.right);
    		}
    	}
    
    	public static void main(String[] args) {
    
    		int[] value = { 6,8,3,7,10,1,9 };
    		BinarySearchTree<Integer> tree = new BinarySearchTree<>();
    		for (int v : value) {
    			tree.insert(v);
    		}
    		System.out.println("前序遍历");
    		tree.preOrder(tree.rootTree);
    		System.out.println();
    		System.out.println("后序遍历");
    		tree.postOrder(tree.rootTree);
    		System.out.println();
    		System.out.println("中序遍历");
    		tree.inOrder(tree.rootTree);
    		System.out.println();
    		System.out.println("最小值==" + tree.findMin());
    		System.out.println("最大值==" + tree.findMax());
    		System.out.println("查找8: " + tree.find(8));
    		System.out.println("是否为空: " + tree.isEmpty());
    		System.out.println();
    
    		tree.remove(8);
    		System.out.println("删除节点值为8的节点,再中序遍历");
    		System.out.println("查找8: " + tree.find(8));
    		tree.inOrder(tree.rootTree);
    	}
    
    }
    测试

    展开全文
  • 单链表的基本操作,二叉树的遍历,折半查找二叉排序树,内部排序等共四个实验的实现过程。
  • 折半查找 算法思想: 先确定待查记录的范围。 给定的值中间记录进行比较 若相等,则找到, 返回位置。 若不相等,则缩小范围在前半部分或后半部分。 重复2,直到找到或不存在范围找不到结束。 二、动态查找 动态...

    查找

    一、静态查找(Static Search Table)

    顺序查找的存储结构

    typedef struct {
    	int key; //关键字
    }ElemType;
    
    typedef struct {
    	ElemType *elem; //数据元素存储空间基址 
    	int length; //表长度 
    

    顺序查找(Sequential Search)

    //顺序查找
    int Search_Seq(SSTable ST, int key) 
    {//在顺序表ST中顺序查找其关键字等于key的元素,若找到,怎函数值为该元素在表中的位置,否则为0 
    	ST.elem[0].key = key;
    	//起到监视哨的作用,目的在于免去查找过程中每一步都要检测整个表是否查找完毕 
    	int i;
    	for(i = ST.length; ST.elem[i].key != key; i-- );
    			return i;
    }
    
    

    折半查找(Binary Search)

    算法思想:

    1. 先确定待查记录的范围。
    2. 给定的值与中间记录进行比较
      若相等,则找到, 返回位置。
      若不相等,则缩小范围在前半部分或后半部分。
    3. 重复2,直到找到或不存在范围找不到结束。
    //折半查找
    int Search_Bin(SSTable ST, int key)
    {//关键字有序
    	int min, max, mid;
    	min = 1;
    	max = ST.length;
    	while(min <= max)
    	{
    		mid = (min + max)/2;
    		if(ST.elem[mid].key == key)
    			return mid;
    		else if(ST.elem[mid].key > key)
    			max = mid - 1;
    		else
    			min = mid + 1;
    	}
    	return 0;
    }
    

    二、动态查找(Dynamic Search Table)

    动态查找表的特点:

    • 表结构本身是在查找过程中动态生成的。即对给定值key, 若表中有其关键字等于key的记录,则查找成功返回,否则插入关
      键字等于key的记录。

    二叉排序树(Binary Sort Tree)

    什么是二叉排序树?(二叉查找树)
    或者是一棵空树,或者是具有下面性质的二叉树:

    1. 若它的左子树不空,则左子树上所有结点的值均小于它的根的值;
    2. 若它的右子树不空,则右子树上所有结点的值均大于它的根的值;
    3. 它的左、右子树也分别是二叉排序树。
    //二叉排序树
    BiTree SearchBST(BiTree T,int key)
    {//查找成功,返回指向该数据元素结点的指针,否则返回空指针 
    	//小于关键字在左子树中继续查找,大于关键字在右子树中继续查找
    	if(!T || T->key == key)
    		return T; //查找结束 
    	else if(T->key > key)
    		return SearchBST(T->lchild,key);
    	else
    		return SearchBST(T->rchild,key);
    }
    

    二叉排序树的插入

    二叉排序树是一种动态树表。其特点是:

    1. 树的结构通常不是一次生成的,而是在查找的过程中,当 不存在关键字等于给定值的结点时在进行插入。
    2. 新插入的结点一定是叶子,并且是查找不成功时查找路径 上最后一个结点的左子女或右子女。
    //插入操作
    int SearchBST(BiTree T, int key, BiTree &p)
    {//查找成功,指针p指向该数据元素结点,并返回1;
    //查找不成功,指针p指向查找路径上访问的最后一个结点,并返回0。 
    	if(!T)
    		return 0; //查找不成功
    	else if(T->key == key)
    	{
    		p = T;
    		return 1; //查找成功 
    	} 
    		
    	else if(T->key > key)
    	{
    		p = T;
    		return SearchBST(T->lchild,key, p);
    	}
    	else
    	{
    		p = T;
    		return SearchBST(T->rchild,key, p);
    	}
    }
    
    int InsertBST(BiTree &T, int key)
    {//当二叉排序树T中不存在关键字等于key的元素时,插入key并返回1,否则返回0 
    	
    	BiTree p, q;
    	p = NULL;
    	if(SearchBST(T,key,p) == 1)
    		return 0;
    
    	q = (BiTree)malloc(sizeof(BTree));
    	q->key = key;
    	q->lchild = NULL;
    	q->rchild = NULL;
    	if(p == NULL)
    		T = q;
    	else if(p->key > key)
    		p->lchild = q;
    	else
    		p->rchild = q;
    	return 1;
    }
    
    展开全文
  • 基于树的查找二叉排序树、平衡二叉排序树、B-树和B+树) 基于散列表的查找 2 基于线性表的查找 2.1 定义和分类 基于线性表的查找主要是两部分:(索引顺序表用的不是很多) 顺序查找(适用于两种存储结构)...
  • 折半查找 把low放在最左边,high放最右边,mid=(high+low)/2 如果low<=high则循环,当待查找数<mid,则high=mid-1,当待查数>mid,则low+1 当low=mid的时候,该值查找数相等,则输出,...二叉排序树 if左
  • 折半查找  对于关键码有序的数列,用二分法查找。  比如123456789,要找2,先折半找5,2比5小,继续向左查找,找3,2比3小,继续向左查找,2匹配成功。  可以想到这是个递归的过程我这里递归非递归都写一遍。  ...
  • 实现折半查找与遍历二叉排序树 一、实验目的 掌握几种典型的查找方法(折半查找二叉排序树的查找、哈希查找)。 对各种查找算法的特点、使用范围和效率有进一步的了解。 了解图的典型应用的算法程序。 二、实验...
  • 【数据结构】折半查找及其二叉判定画法

    万次阅读 多人点赞 2019-09-25 23:55:40
    折半查找又叫二分查找,是数据结构中一种很重要的查找方式。 其特点有以下几个: 只能对有序的顺序表进行查找。 是一种静态查找。 查找的平均时间复杂度为o(log...折半查找二叉排序树查找的平均查找长度均取决...
  • 顺序查找 折半查找 二叉排序树

    千次阅读 2013-07-18 21:13:13
    1.顺序查找,折半查找二叉排序树操作定义 SeqSearch.h #include #define ARRAYLEN 8 int source[]={69, 65, 90, 37, 92, 6, 28, 54}; //静态查找表 int source1[ARRAYLEN + 1]={69, 65, 90, 37, 92, 6, 28, 54...
  • public class Search { public class BiTreeNode{ int m_nValue; BiTreeNode m_pLeft; BiTreeNode m_pRight; } //顺序查找,查到则返回该值下标,查不到返回-1. public...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,215
精华内容 2,486
关键字:

折半查找与二叉排序树的时间