Простое двоичное дерево поиска с использованием Java

задняя часть структура данных

период, термин:

Бинарное дерево — это особое дерево, каждый узел которого имеет не более двух дочерних узлов, один из этих двух узлов называется левым дочерним, а другой — правым дочерним.

Двоичное дерево поиска — это бинарное дерево, для каждого узла которогоx, значение всех узлов-потомков в его левом поддереве всегда меньше, чемx, значение всех потомков в его правом поддереве всегда больше, чемxзначение

Бинарное дерево поиска

一颗二叉查找树

1. Базовая реализация:

Общий BST записывает данные в виде пар ключ-значение.Для простоты в этой статье в качестве типа ключа используется строка, аValueКак тип значения (значение — универсальный тип, тип которого указывается при создании дерева). Если вам интересно, вы можете прочитать "Алгоритмы (четвертое издание)"

public class BST<Value> {
    private Node root;
    
    private class Node{
        private String key;
        private Value value;
        private Node left;
        private Node right;

        Node(String key,Value value){this.key=key;this.value=value;}
    }
    /*关于二叉查找树的一些方法，具体实现见下文*/
    //添加节点
    public void add(String key,Value value){}

    //根据键来获取值
    public Value get(String key){return 0;}

    //获取键最小的那个节点
    public Node min(){return null;}

    //获取键最大的那个节点
    public Node max(){return null;}

    //删除节点
    public void delete(String key){}

    //对二叉树进行中序遍历
    public Iterable<String> inorderTraverse(){return null;}
}

2. Найдите значение по ключу:

Поиск записей по ключу. Если дерево содержит ключ, найти попадание и вернуть значение, соответствующее ключу, если нет, найти промах и вернуть null

//根据键来获取值
public Value get(String key){
    return get(root,key);
}

private Value get(Node x,String key){
    //在以x节点为根节点的树中查找key
    //如果能找到，则返回键对应的值，如果找不到则返回null
    if(x==null) return null;                	    //如果当前节点为null，则直接返回null

    int cmp=key.compareTo(x.key);           	    //比较当前节点和待找节点的key
    if(cmp>0) 		return get(x.right,key);    //在当前节点的右子树中继续查找
    else if(cmp<0) 	return get(x.left,key);     //在当前节点的左子树中继续查找
    else 		return x.value;             //两者的key相等，则查找命中
}

3. Вставьте пару клавиша:

Дана пара ключ-значение, если в дереве нет кнопки, создаем узел и цепляем узел на пустую ссылку в конце поиска, если эта кнопка в дереве есть, соответствующее значение обновляется.

//插入新节点
public void add(String key,Value value){
    root=add(root,key,value);
}

private Node add(Node x,String key,Value value){
    //在以x节点为根节点的树中插入节点
    if(x==null) return new Node(key,value);     	//x为空，表示已经到达树的叶子节点
    												//则直接新键节点并挂在空链接上

    int cmp=key.compareTo(x.key);               	//比较将要插入的节点和节点x的key
    if(cmp>0)       x.right=add(x.right,key,value);     //在x的右子树中插入节点
    else if(cmp<0)  x.left=add(x.left,key,value);       //在x的左子树中插入节点
    else            x.value=value;              	//树已经有key对应的节点，则直接更新其值
    return x;                                   	//返回节点x的引用;
}

4. Получить узел с наименьшим ключом:

Если левая ссылка корневого узла пуста, наименьший узел в дереве является корневым узлом.

Если левая ссылка корневого узла не пуста, наименьший узел в левом поддереве корневого узла является наименьшим узлом всего дерева.

Таким образом, мы можем найти минимальный узел в соответствии с рекурсией

Алгоритм получения наибольшего узла аналогичен, отличие состоит в правом поддереве рекурсивного узла

//获取键最小的那个节点
public Node min(){
    return min(root);
}

private Node min(Node x){
    if(x.left==null) return x;
    return min(x.left);
}

5. Удалите узел с наименьшим ключом:

//删除键最小的那个节点
public void deleteMin(){
    if(root==null) return;
    root=deleteMin(root);
}

private Node deleteMin(Node x){
    if(x.left==null) x=x.right;		       //如果x的左子节点为空，则说明x即为将要删除的最小节点
    						//此时将x引用（x父节点的左链接）赋予x的右子节点
    						//原来的节点因为没有指向它的引用而被垃圾回收
    else x.left=deleteMin(x.left);
    return x;
}

6. Удалите любой узел:

Алгоритм удаления узлов бинарного дерева по ключу более сложен, основные шаги таковы:

  1. Найдите узел для удаления, используйте временную переменную t, чтобы указать на узел
  2. Найдите наименьший узел в правом поддереве узла t и используйте временную переменную x, чтобы указать на этот узел.
  3. Используйте метод deleteMin, чтобы удалить наименьший узел в правом поддереве t и восстановить правое поддерево.
  4. Левая ссылка x указывает на левое поддерево t, а правая ссылка x указывает на правое поддерево t.
  5. соединить x с родителем t
//删除节点
public void delete(String key){
    root=delete(root,key);
}

private Node delete(Node x,String key){

    if(x==null) return null;                    //未找到键值为key的节点
    int cmp=key.compareTo(x.key);
    if(cmp>0) x.right=delete(x.right,key);      //从x的左节点删除节点
    else if(cmp<0) x.left=delete(x.left,key);   //从x的右节点删除节点
    else{
        if(x.right==null) return x.left;        
        if(x.left==null) return x.right;
        Node t=x;
        x=min(t.right);
        x.right=deleteMin(t.right);				//删除t的右子树中的最小节点并恢复右子树
        x.left=t.left;
    }
    return x;
}

7. Неупорядоченный обход бинарного дерева поиска

Неупорядоченный обход бинарного дерева поиска приводит к набору узлов, упорядоченных по ключу.

Код для рекурсивного обхода не сложен

//对二叉树进行中序遍历
public List<Node> inorderTraverse(){
    List<Node> list=new ArrayList<>();
    inorderTraverse(root,list);
    return list;
}

private void inorderTraverse(Node x,List<Node> list){
    if(x==null) return;
    inorderTraverse(x.left,list);
    list.add(x);
    inorderTraverse(x.right,list);
}

8. Распечатайте бинарное дерево поиска в консоли

public void print(){
    System.out.println("***************************************");
    print(root,0);
    System.out.println("***************************************");
}

private void print(Node x,int floor){
    if(x==null) return ;
    print(x.left,floor+1);
    for (int i = 0; i < floor; i++) {
        System.out.print("----");
    }
    System.out.println(x.key+" "+x.value);
    print(x.right,floor+1);
}

9. Тестовые случаи

Ключ в примере имеет тип String, а значение имеет тип Integer. Тестовый пример принимается в консоли как$add stringДобавлено в виде данных, строка для ключа, добавлен порядок соответствующей строки символов,$del stringудалить,$showдля печати,$exitдля выхода

public static void main(String[] args) {
    BST<Integer> sibst = new BST<>();

    int i=1;
    String str;
    boolean flag=true;
    Scanner in = new Scanner(System.in);
    String[] words;

    while(flag){
        str=in.nextLine();
        if(str.equals("")) continue;
        words = str.split(" ");
        switch (words[0]){
            case "$exit": {
                flag=false;
                break;
            }
            case "$add":{
                sibst.add(words[1],i++);
                break;
            }
            case "$del":{
                sibst.delete(words[1]);
                break;
            }
            case "$show":{
                sibst.print();
                break;
            }
            default:{
                System.out.println("错误命令");
            }
        }
    }
}

10. Полный код

BST.java

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BST<Value> {

    private Node root;

    private class Node{
        private String key;
        private Value value;
        private Node left;
        private Node right;

        Node(String key,Value value){
            this.key=key;
            this.value=value;
        }
    }

    //添加节点
    public void add(String key,Value value){
        root=add(root,key,value);
    }

    public Node add(Node x,String key,Value value){
        //在以x节点为根节点的树中插入节点
        if(x==null) return new Node(key,value);         //x为空，表示已经到达树的叶子节点
                                                        //则直接新键节点并挂在空链接上

        int cmp=key.compareTo(x.key);                   //比较将要插入的节点和节点x的key
        if(cmp>0)       x.right=add(x.right,key,value); //在x的右子树中插入节点
        else if(cmp<0)  x.left=add(x.left,key,value);   //在x的左子树中插入节点
        else            x.value=value;                  //树已经有key对应的节点，则直接更新其值
        return x;                                       //更新节点x;
    }

    //根据键来获取值
    public Value get(String key){
        return get(root,key);
    }

    private Value get(Node x,String key){
        //在以x节点为根节点的树中查找key
        //如果能找到，则返回键对应的值，如果找不到则返回null
        if(x==null) return null;                //如果当前节点为null，则直接返回null

        int cmp=key.compareTo(x.key);           //比较当前节点和待找节点的key
        if(cmp>0) return get(x.right,key);      //在当前节点的右子树中继续查找
        else if(cmp<0) return get(x.left,key);  //在当前节点的右子树中继续查找
        else return x.value;                    //两者的key相等，则查找命中
    }

    //获取键最小的那个节点
    public Node min(){
        return min(root);
    }

    private Node min(Node x){
        if(x.left==null) return x;
        return min(x.left);
    }

    //删除键最小的那个节点
    public void deleteMin(){
        if(root==null) return;
        root=deleteMin(root);
    }

    private Node deleteMin(Node x){
        if(x.left==null) x=x.right;
        else x.left=deleteMin(x.left);
        return x;
    }

    //获取键最大的那个节点
    public Node max(){
        return null;
    }

    //删除节点
    public void delete(String key){
        root=delete(root,key);
    }

    private Node delete(Node x,String key){

        if(x==null) return null;                    //未找到键值为key的节点
        int cmp=key.compareTo(x.key);
        if(cmp>0) x.right=delete(x.right,key);      //从x的左节点删除节点
        else if(cmp<0) x.left=delete(x.left,key);   //从x的右节点删除节点
        else{
            if(x.right==null) return x.left;
            if(x.left==null) return x.right;
            Node t=x;
            x=min(t.right);
            x.right=deleteMin(t.right);
            x.left=t.left;
        }
        return x;
    }

    //对二叉树进行中序遍历
    public List<Node> inorderTraverse(){

        List<Node> list=new ArrayList<>();
        inorderTraverse(root,list);
        return list;
    }

    private void inorderTraverse(Node x,List<Node> list){
        if(x==null) return;
        inorderTraverse(x.left,list);
        list.add(x);
        inorderTraverse(x.right,list);
    }

    public void print(){
        System.out.println("***************************************");
        print(root,0);
        System.out.println("***************************************");
    }

    private void print(Node x,int floor){
        if(x==null) return ;
        print(x.left,floor+1);

        for (int i = 0; i < floor; i++) {
            System.out.print("----");
        }
        System.out.println(x.key+" "+x.value);

        print(x.right,floor+1);
    }

    public static void main(String[] args) {
        BST<Integer> sibst = new BST<>();

        int i=0;
        String str;
        boolean flag=true;
        Scanner in = new Scanner(System.in);
        String[] words;

        while(flag){
            str=in.nextLine();
            if(str.equals("")) continue;
            words = str.split(" ");
            switch (words[0]){
                case "$exit": {
                    flag=false;
                    break;
                }
                case "$add":{
                    sibst.add(words[1],i++);
                    break;
                }
                case "$del":{
                    sibst.delete(words[1]);
                    break;
                }
                case "$show":{
                    sibst.print();
                    break;
                }
                default:{
                    System.out.println("错误命令");
                }
            }
        }
    }
}
Категории