devbox
不正经
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

BST 二叉搜索树_二叉搜索树查找算法压缩包

作者：不正经 | 2024-05-15 10:11:12

赞

踩

二叉搜索树查找算法压缩包

目录

一、BST概念

二、BST的查找、插入和遍历

1、查找

2、插入

3、遍历

（1）前序

（2）中序（递增显示）

（3）后序

（4）深度优先（DFS）

（5）广度优先（BFS）

4、删除

（1）无左子结点时

（2）有左子结点时

三、定义一个树接口

四、实现BST类 

五、数据压缩：哈夫曼编码

一、BST概念

前几天学习了堆排序，其实堆排序用到的结构就是二叉树。

那么BST是满足如下规则的二叉树：

树中的任意结点，左子树的值都小于结点的，右子树的值都大于结点的（左小右大）

二、BST的查找、插入和遍历

1、查找

遵循BST“左小右大”的原则，查询时从根结点向下依次查找各个子树，直到 子树为空 或 已查询到 为止。否则设置的对比current结点将一直与目标值比较，小于当前结点时赋给current.left，大于当前结点时赋给current.right。

2、插入

设置一个parent结点（新元素的父结点）和current结点（定位结点）。如果树为空，就使用新元素创造一个新的根结点。否则遍历寻找新元素结点的父结点的位置，接下来的操作就和“查找”操作很像了。定位父结点成功后比较新元素和父元素大小，判断标准依旧是左大右小。

3、遍历

树的遍历方法主要有前序（preorder）、中序（inorder）、后序（postorder）、深度优先和广度优先。以下面这个二叉树为例：

（1）前序

访问current -> 递归访问current.left -> 递归访问current.right

遍历为：60 55 45 57 59 100 67 107 101

（2）中序（递增显示）

递归访问current.left -> 访问current -> 递归访问current.right

遍历为：45 55 57 59 60 67 100 101 107（注意是先101才107 因为左边优先级大于右边）

（3）后序

递归访问current.left -> 递归访问current.right -> 访问current

遍历为：45 59 57 55 67 101 107 100 60

（4）深度优先（DFS）

访问root -> 任意顺序递归访问其left和right（前序遍历算是深度优先遍历的一个特例）

（5）广度优先（BFS）

逐层访问。访问root -> 从左往右访问其子结点 -> 再从左往右访问其孙结点2

遍历为：60 55 100 45 57 67 107 59 101

4、删除

删除操作要比插入操作复杂很多。删除结点之前需要定位current和current，然后分为有current.left和无current.left两个情况：

（1）无左子结点时

当current只有右子结点时，只需要：

  1. 将current.right和parent连接
  2. 删除current

（2）有左子结点时

找出current左子树中的最大元素记为rightMost（注意rightMost可能有左结点但绝对没有右结点），记rightMost的父结点为parentOfrightMost。接下来：

  1. 替换current中的元素值为rightMost
  2. 然后连接parentOfrightMost和rightMost.left
  3. 最后删除rightMost

三、定义一个树接口

我们定义Tree接口为Collection接口的子类：

  1. import java.util.Collection;
  2.  
  3. public interface Tree<E> extends Collection<E> {
  4.     public boolean search(E e);
  5.  
  6.     public boolean insert(E e);
  7.  
  8.     public boolean delete(E e);
  9.  
  10.     public int getSize();
  11.  
  12.     public default void inorder(){
  13.     }
  14.  
  15.     public default void postorder(){
  16.     }
  17.  
  18.     public  default void preorder(){
  19.     }
  20.  
  21.     // 重写Collection中定义的方法
  22.     @Override
  23.     public default boolean isEmpty(){
  24.         return size() == 0;
  25.     }
  26.  
  27.     @Override
  28.     public default boolean contains(Object e){
  29.         return search((E)e);
  30.     }
  31.  
  32.     @Override
  33.     public default boolean add(E e){
  34.         return insert(e);
  35.     }
  36.  
  37.     @Override
  38.     public default boolean remove(Object e){
  39.         return delete((E)e);
  40.     }
  41.  
  42.     @Override
  43.     public default int size(){
  44.         return getSize();
  45.     }
  46.  
  47.     @Override
  48.     public default boolean containsAll(Collection<?> c){
  49.         return false;
  50.     }
  51.  
  52.     @Override
  53.     public default boolean addAll(Collection<? extends E> c){
  54.         return false;
  55.     }
  56.  
  57.     @Override
  58.     public default boolean removeAll(Collection<?> c){
  59.         return false;
  60.     }
  61.  
  62.     @Override
  63.     public default boolean retainAll(Collection<?> c){
  64.         return false;
  65.     }
  66.  
  67.     @Override
  68.     public default Object[] toArray(){
  69.         return null;
  70.     }
  71.  
  72.     @Override
  73.     public default <T> T[] toArray(T[] array){
  74.         return null;
  75.     }
  76. }

四、实现BST类 

  1. class BST<E extends Comparable<E>> implements Tree<E>{
  2.     protected TreeNode<E> root;
  3.     protected int size = 0;
  4.  
  5.     public BST(){
  6.     }
  7.  
  8.     public BST(E[] objects) {
  9.         for(int i =0; i < objects.length; i++) {
  10.             add(objects[i]);
  11.         }
  12.     }
  13.  
  14.     // 查找
  15.     @Override
  16.     public boolean search(E e){
  17.         TreeNode current = root;
  18.  
  19.         while(current != null){  //不为空时->
  20.             if(e.compareTo((E) current.element) < 0){  // 小于->
  21.                 current = current.left;  //指到left->
  22.             }else if(e.compareTo((E) current.element) > 0){  // 大于->
  23.                 current = current.right;  //指到right->
  24.             }else return true; // 相同即找到
  25.         }
  26.         return false;  // 没找到
  27.     }
  28.  
  29.     /* 递归search
  30.     public boolean search(E e) {
  31.         return search(root, e);
  32.     }
  34.     public boolean search(TreeNode<E> root, E e) {
  35.         if (root == null)
  36.             return false;
  37.         else if (e.compareTo(root.element) < 0)
  38.             return search(root.left, e);
  39.         else if (e.compareTo(root.element) > 0)
  40.             return search(root.right, e);
  41.          else
  42.             return true;
  43.     }
  44.     * */
  45.  
  46.     // 插入
  47.     @Override
  48.     public boolean insert(E e){
  49.         if(root == null){
  50.             root = createNewNode(e); //如果树为空，创建一个新的根结点
  51.         }else {
  52.             // 否则寻找新元素父节点的位置
  53.             TreeNode<E> parent = null;
  54.             TreeNode<E> current = root;
  55.  
  56.             while(current != null){
  57.                 if(e.compareTo(current.element) < 0){
  58.                     parent = current;
  59.                     current = current.left;
  60.                 }else if(e.compareTo(current.element) > 0){
  61.                     parent = current;
  62.                     current = current.left;
  63.                 }else return false;
  64.             }
  65.             // 链接父结点
  66.             if(e.compareTo(parent.element) < 0)
  67.                 parent.left = createNewNode(e);
  68.             else
  69.                 parent.right = createNewNode(e);
  70.         }
  71.         size++;
  72.         return true;
  73.     }
  74.  
  75.     protected TreeNode<E> createNewNode(E e){
  76.         return new TreeNode<>(e);
  77.     }
  78.  
  79.     // 中序遍历
  80.     @Override
  81.     public void inorder(){
  82.         inorder(root);
  83.     }
  84.     protected void inorder(TreeNode<E> root){
  85.         if(root == null){  // 树为空时结束递归
  86.             return;
  87.         }
  88.         inorder(root.left);  //递归左结点
  89.         System.out.print(root.element + " ");  // 中间结点
  90.         inorder(root.right);  // 递归右结点
  91.     }
  92.  
  93.     // 后序遍历
  94.     @Override
  95.     public void postorder(){
  96.         postorder(root);
  97.     }
  98.     protected void postorder(TreeNode<E> root){
  99.         if(root == null){
  100.             return;
  101.         }
  102.         postorder(root.left);
  103.         postorder(root.right);
  104.         System.out.print(root.element + " ");
  105.     }
  106.  
  107.     // 前序遍历
  108.     public void preorder(){
  109.         preorder(root);
  110.     }
  111.     protected void preorder(TreeNode<E> root){
  112.         if(root == null){
  113.             return ;
  114.         }
  115.         System.out.print(root.element + " ");
  116.         preorder(root.left);
  117.         preorder(root.right);
  118.     }
  119.  
  120.     // 树结点class
  121.     public static class TreeNode<E>{
  122.         protected E element;
  123.         protected TreeNode<E> left;
  124.         protected TreeNode<E> right;
  125.  
  126.         public TreeNode(E e){
  127.             element = e;
  128.         }
  129.     }
  130.  
  131.     @Override
  132.     public int getSize(){
  133.         return size;
  134.     }
  135.  
  136.     public TreeNode<E> getRoot(){
  137.         return root;
  138.     }
  139.  
  140.     // 以数组线性表返回结点路径
  141.     public java.util.ArrayList<TreeNode<E>> path(E e){
  142.         java.util.ArrayList<TreeNode<E>> list = new java.util.ArrayList<>();
  143.         TreeNode<E> current = root;
  144.  
  145.         while(current != null){
  146.             list.add(current);
  147.             if(e.compareTo(current.element) < 0){
  148.                 current = current.left;
  149.             }else if(e.compareTo(current.element) > 0){
  150.                 current = current.right;
  151.             }else break;
  152.         }
  153.         return list;
  154.     }
  155.  
  156.     /**删除*/
  157.     @Override
  158.     public boolean delete(E e){
  159.         TreeNode<E> parent = null;
  160.         TreeNode<E> current = root;
  161.  
  162.         // 定位current和parent
  163.         while(current != null){
  164.             if(e.compareTo(current.element) < 0){
  165.                 parent = current;
  166.                 current = current.left;
  167.             }else if(e.compareTo(current.element) > 0){
  168.                 parent = current;
  169.                 current = current.right;
  170.             }else break;
  171.         }
  172.  
  173.         if(current == null){
  174.             return false;  // 结点不在树中
  175.         }
  176.  
  177.         // 1、无左子结点
  178.         if(current.left == null){
  179.             if(parent == null){
  180.                 root = current.right;  // 没有父结点 就设为根结点
  181.             }else {
  182.                 if(e.compareTo(parent.element) < 0){  // 删除current结点
  183.                     parent.left = current.right;
  184.                 }else {
  185.                     parent.right = current.right;
  186.                 }
  187.             }
  188.         }else{  // 2、有左子结点
  189.             TreeNode<E> parentOfRightMost = current;
  190.             TreeNode<E> rightMost = current.left;
  191.  
  192.             // 定位rightMost和parentOfRightMost
  193.             while (rightMost.right != null){
  194.                 parentOfRightMost = rightMost;
  195.                 rightMost = rightMost.right;
  196.             }
  197.             current.element = rightMost.element;  // 用rightMost替换current
  198.  
  199.             // 删除rightMost结点
  200.             if(parentOfRightMost.right == rightMost){
  201.                 parentOfRightMost.right = rightMost.left;
  202.             }else{
  203.                 parentOfRightMost.left = rightMost.left;
  204.             }
  205.         }
  206.         size--;
  207.         return true;
  208.     }
  209.  
  210.     // 遍历迭代器
  211.     @Override
  212.     public java.util.Iterator<E> iterator() {
  213.         return new InorderIterator();
  214.     }
  215.     private class InorderIterator implements java.util.Iterator<E>{
  216.         private java.util.ArrayList<E> list = new java.util.ArrayList<>();
  217.         private int current = 0;
  218.  
  219.         public InorderIterator(){
  220.             inorder();
  221.         }
  222.  
  223.         private void inorder(){
  224.             inorder(root);
  225.         }
  226.  
  227.         private void inorder(TreeNode<E> root){
  228.             if(root == null){
  229.                 return;
  230.             }
  231.             inorder(root.left);
  232.             list.add(root.element);
  233.             inorder(root.right);
  234.         }
  235.  
  236.         @Override
  237.         public boolean hasNext(){
  238.             if(current < list.size()){
  239.                 return true;
  240.             }
  241.             return false;
  242.         }
  243.  
  244.         @Override
  245.         public E next(){
  246.             return list.get(current++);
  247.         }
  248.  
  249.         @Override
  250.         public void remove(){
  251.             if(current == 0){
  252.                 throw new IllegalStateException();
  253.             }
  254.             delete(list.get(--current));
  255.             list.clear();
  256.             inorder();
  257.         }
  258.     }
  259.  
  260.     @Override
  261.     public void clear(){
  262.         root = null;
  263.         size = 0;
  264.     }
  265. }

五、数据压缩：哈夫曼编码

哈夫曼编码中的字符编码基于字符出现的次数使用二叉树构建。使用贪心算法，算法总是选择具有最小权重的两棵树，并且创造一个新的父结点：

 接下来编写一个程序，用户输入字符串，程序将会输出每个字符出现的次数以及其哈夫曼编码：

  1. import java.util.Scanner;
  2.  
  3. public class HuffmanCode {
  4.     public static void main(String[] args){
  5.         Scanner input = new Scanner(System.in);
  6.         System.out.print("Enter text: ");
  7.         String text = input.nextLine();
  8.  
  9.         // 计算字符出现次数
  10.         int[] counts = getCharacterFrequency(text);
  11.  
  12.         System.out.printf("%-15s%-15s%-15s%-15s\n","ASCII Code","Character","Frequency","Code");
  13.  
  14.         // 基于counts得到哈夫曼树
  15.         Tree tree = getHuffmanTree(counts);
  16.         String[] codes = getCode(tree.root);
  17.  
  18.         for(int i = 0; i < codes.length; i++){
  19.             if(counts[i] != 0){
  20.                 System.out.printf("%-15s%-15s%-15s%-15s\n",i, (char)i + "",counts[i],codes[i]);
  21.             }
  22.         }
  23.     }
  24.  
  25.     // 获取每个叶子结点中字符的编码
  26.     public static String[] getCode(Tree.Node root) {
  27.         if(root == null){
  28.             return null;
  29.         }
  30.         String[] codes = new String[2 *128];
  31.         assignCode(root,codes);
  32.         return codes;
  33.     }
  34.  
  35.     // 给树中每个结点赋予编码
  36.     private static void assignCode(Tree.Node root, String[] codes){
  37.         if(root.left != null){
  38.             root.left.code = root.code + "0";
  39.             assignCode(root.left, codes);
  40.  
  41.             root.right.code = root.code + "1";
  42.             assignCode(root.right,codes);
  43.         }else {
  44.             codes[(int) root.element] = root.code;
  45.         }
  46.     }
  47.  
  48.     // 返回一颗哈夫曼树
  49.     public static Tree getHuffmanTree(int[] counts){
  50.         // 创建单结点树并添加到堆中
  51.         Heap<Tree> heap = new Heap<>();
  52.         for(int i = 0; i < counts.length; i++){
  53.             if(counts[i] > 0){
  54.                 heap.add(new Tree(counts[i],(char)i));
  55.             }
  56.         }
  57.  
  58.         // while迭代
  59.         while(heap.getSize() > 1){
  60.             Tree t1 = heap.remove(); //每次将权重最小的两个子树从堆中删除
  61.             Tree t2 = heap.remove();
  62.             heap.add(new Tree(t1, t2));  //t1,t2组合成新树。接着添加新树到堆中
  63.         }
  64.         return heap.remove();
  65.     }
  66.  
  67.     // 创建一个数组计算256个ASCII字符出现的次数
  68.     public static int[] getCharacterFrequency(String text){
  69.         int[] counts = new int[256];
  70.  
  71.         for(int i = 0; i < text.length(); i++){
  72.             counts[(int)text.charAt(i)]++;
  73.         }
  74.         return counts;
  75.     }
  76.  
  77.     public static class Tree implements Comparable<Tree>{
  78.         Node root;
  79.  
  80.         public Tree(Tree t1, Tree t2){
  81.             root = new Node();
  82.             root.left = t1.root;
  83.             root.right = t2.root;
  84.             root.weight = t1.root.weight + t2.root.weight;
  85.         }
  86.  
  87.         public Tree(int weight, char element) {
  88.             root  = new Node(weight, element);
  89.         }
  90.  
  91.         @Override
  92.         public int compareTo(Tree t) {
  93.             if(root.weight < t.root.weight){
  94.                 return 1;
  95.             }else if(root.weight == t.root.weight){
  96.                 return 0;
  97.             }else return -1;
  98.         }
  99.  
  100.         public class Node{
  101.             char element;
  102.             int weight;
  103.             Node left;
  104.             Node right;
  105.             String code = "";
  106.  
  107.             public Node() {
  108.             }
  109.  
  110.             public Node(int weight, char element){
  111.                 this.weight = weight;
  112.                 this.element = element;
  113.             }
  114.         }
  115.     }
  116. }

运行结果如下： 

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/不正经/article/detail/572345
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号