『数据结构与算法』二叉查找树（BST）

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了『数据结构与算法』二叉查找树（BST），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含12608字，纯文字阅读大概需要19分钟。

内容图文

微信搜索：码农StayUp
主页地址：https://gozhuyinglong.github.io
源码分享：https://github.com/gozhuyinglong/blog-demos

1. 二叉查找树（Binary Search Tree）

二叉查找树又叫二叉排序树（Binary Sort Tree），或叫二叉搜索树，简称BST。BST是一种节点值之间有次序的二叉树。其特性是：

若任意节点的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
若任意节点的右子树不空，则右子树上所有节点的值均大于或等于它的根节点的值；
任意节点的左、右子树也分别为二叉查找树；

『数据结构与算法』二叉查找树（BST） - 文章图片

二叉查找树相比于其他数据结构的优势在于查找、插入的时间复杂度较低，为$O(logN)$。用大$O$符号表示的时间复杂度：

算法	平均	最差
空间	$O(N)$	$O(N)$
搜索	$O(logN)$	$O(N)$
插入	$O(logN)$	$O(N)$
删除	$O(logN)$	$O(N)$

2. BST的实现

二叉查找树要求所有的节点元素都能够排序，所以我们的Node节点类需要实现Comparable接口，树中的两个元素可以使用compareTo方法进行比较。
我们节点中元素的类型为int型，所以该接口泛型为Comparable<Integer>，下面是具体实现：

2.1 节点类

element 为数据元素
left 为左子节点
right 为右子节点

class Node implements Comparable<Integer> {
    private final int element; // 数据元素
    private Node left; // 左子树
    private Node right; // 右子树

    private Node(Integer element) {
        this.element = element;
    }

    @Override
    public int compareTo(Integer o) {
        return o.compareTo(element);
    }
}

2.2 二叉查找树类

root 为树根，所有的操作均始于此

后面会在该类中增加其他方法，如添加、查找、删除等

class BinarySearchTree {
        private Node root; // 树根
}

3. 插入节点

向二叉查找树中插入的节点总是叶子节点，插入过程如下：

若root为空，则将插入节点设为root
当前元素与插入元素通过compareTo进行比较，若插入元素值小，并且左子节点left为空，则插入至当前节点左子节点；否则继续递归
若插入元素值大，且右子节点right为空，则插入至当前节点右子节点；否则继续递归。
若插入元素等于当前节点元素，则插入失败。注：也可以将其插入到右子节点，我这里为了方便直接放弃插入。

具体实现：
在BinarySearchTree类中添加两个方法：

public boolean add(int element) 为公开方法
private boolean add(Node node, int element)为私有方法，内部递归使用

       // 添加元素
       public boolean add(int element) {
            if (root == null) {
                root = new Node(element);
                return true;
            }
            return add(root, element);
        }
        // 添加元素（递归）
        private boolean add(Node node, int element) {
            if (node.compareTo(element) < 0) {
                if (node.left == null) {
                    node.left = new Node(element);
                    return true;
                } else {
                    return add(node.left, element);
                }
            } else if (node.compareTo(element) > 0) {
                if (node.right == null) {
                    node.right = new Node(element);
                    return true;
                } else {
                    return add(node.right, element);
                }
            } else {
                return false;
            }
        }

4. 查找节点

通过二叉查找树查找元素，其过程如下：

若root为空，则查找失败
将当前元素与目标元素对比，若相等则查找成功。
若不相等，则继续递归查找：若目标值小于当前节点值，则查找左子树；否则，查找右子树。

具体实现：
在BinarySearchTree类中添加两个方法：

public Node find(int element) 为公开方法
private Node find(Node node, int element) 为私有方法，内部递归使用

      // 查找元素
      public Node find(int element) {
            if (root == null) {
                return null;
            }
            return find(root, element);
        }

        // 查询元素（递归）
        private Node find(Node node, int element) {
            if (node == null) {
                return null;
            }
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {
                return find(node.left, element);
            } else if (compareResult > 0) {
                return find(node.right, element);
            } else {
                return node;
            }
        }

5. 遍历节点

BST是一个有序二叉树，通过中序遍历可顺序输出树中节点。
中序遍历过程如下：

递归遍历左子节点
输出当前节点
递归遍历右子节点

具体实现：
在BinarySearchTree类中添加两个方法：

public void orderPrint() 为公开方法
private void orderPrint(Node node) 为私有方法，内部递归使用

      // 遍历节点
      public void orderPrint() {
            orderPrint(root);
        }

        // 遍历节点（递归）
        private void orderPrint(Node node) {

            if (node == null) {
                return;
            }

            // 递归左子节点
            if (node.left != null) {
                orderPrint(node.left);
            }

            // 输出当前节点
            System.out.println(node.element);

            // 递归右子节点
            if (node.right != null) {
                orderPrint(node.right);
            }

        }

6. 删除节点

删除节点最为复查，共有三种情况：

6.1 目标元素为叶子节点

叶子节点最容易删除，过程如下：

找到目标节点的父节点
判断目标节点是父节点的左子树还是右子树
若是左子树，将父节点的left设为空；否则将父节点的right设为空

6.2 目标元素即有左子树，也有右子树

该情况删除操作最为复杂，过程如下：

找到目标节点的父节点
判断目标节点是父节点的左子树还是右子树
找到右子树中最小元素（叶子节点），将其赋给临时变量minNode，再将该元素从树中删除
将目标元素的属性赋予minNode。
若目标元素是父节点的左子树，将父节点的left设为minNode；否则将父节点的right设为minNode

6.3 目标元素只有左子树，或只有右子树

删除过程如下

找到目标节点的父节点
判断目标节点是父节点的左子树还是右子树
若是左子树，将父节点的left设为目标节点不为空的子树；否则将父节点的right设为目标节点不为空的子树

具体实现
在BinarySearchTree类中添加两个方法：

public boolean remove(int element) 为公开方法
private boolean remove(Node parentNode, Node node, int element)为私有方法，内部递归使用

      // 删除节点
      public boolean remove(int element) {
            if (root == null) {
                return false;
            }
            // 如果删除的元素是root
            if (root.compareTo(element) == 0) {
                if (root.right == null) {
                    root = root.left;
                } else {
                    root.right.left = root.left;
                    root = root.right;
                }
                return true;
            }
            return remove(null, root, element);
        }

        // 删除节点（递归）
        private boolean remove(Node parentNode, Node node, int element) {
            if (node == null) {
                return false;
            }
            // 先找到目标元素
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {
                return remove(node, node.left, element);
            }
            if (compareResult > 0) {
                return remove(node, node.right, element);
            }

            // 找到目标元素，判断该节点是父节点的左子树还是右子树
            boolean isLeftOfParent = false;
            if (parentNode.left != null && parentNode.left.compareTo(element) == 0) {
                isLeftOfParent = true;
            }

            // 删除目标元素
            if (node.left == null && node.right == null) { // （1）目标元素为叶子节点，直接删除
                if (isLeftOfParent) {
                    parentNode.left = null;
                } else {
                    parentNode.right = null;
                }
            } else if (node.left != null && node.right != null) { // （2）目标元素即有左子树，也有右子树
                // 找到右子树最小值（叶子节点），并将其删除
                Node minNode = findMin(node.right);
                remove(minNode.element);
                // 将该最小值替换要删除的目标节点
                minNode.left = node.left;
                minNode.right = node.right;
                if(isLeftOfParent) {
                    parentNode.left = minNode;
                } else {
                    parentNode.right = minNode;
                }

            } else { // （3）目标元素只有左子树，或只有右子树
                if (isLeftOfParent) {
                    parentNode.left = node.left != null ? node.left : node.right;
                } else {
                    parentNode.right = node.left != null ? node.left : node.right;
                }
            }
            return true;
        }
    }

7. 完整代码

该代码根据下图二叉查找树实现，其操作包括：添加、查找、遍历、删除、查询最小值、查询最大值。

『数据结构与算法』二叉查找树（BST） - 文章图片

public class BinarySearchTreeDemo {

    public static void main(String[] args) {
        BinarySearchTree tree = new BinarySearchTree();

        System.out.println("----------------------添加元素");
        Integer[] array = {5, 2, 7, 1, 4, 3, 7, 6, 9, 8};
        for (Integer element : array) {
            System.out.printf("添加元素[%s] --> %s\n", element, tree.add(element));
        }

        System.out.println("----------------------顺序输出（中序遍历）");
        tree.orderPrint();

        System.out.println("----------------------查找元素");
        System.out.println(tree.find(7));

        System.out.println("----------------------查找最小元素");
        System.out.println(tree.findMin());

        System.out.println("----------------------查找最大元素");
        System.out.println(tree.findMax());

        System.out.println("----------------------是否包含元素");
        System.out.println("是否包含[0] --> \t" + tree.contains(0));
        System.out.println("是否包含[2] --> \t" + tree.contains(2));

        System.out.println("----------------------删除目标元素");
        System.out.println("删除[0] --> \t" + tree.remove(0));
        tree.orderPrint();
        System.out.println("删除[1] --> \t" + tree.remove(1));
        tree.orderPrint();
        System.out.println("删除[4] --> \t" + tree.remove(4));
        tree.orderPrint();
        System.out.println("删除[7] --> \t" + tree.remove(7));
        tree.orderPrint();

    }

    private static class BinarySearchTree {
        private Node root; // 树根

        /**
         * 添加元素
         *
         * @param element
         * @return
         */
        public boolean add(int element) {
            if (root == null) {
                root = new Node(element);
                return true;
            }
            return add(root, element);
        }

        /**
         * 添加元素（递归）
         *
         * @param node
         * @param element
         * @return
         */
        private boolean add(Node node, int element) {
            if (node.compareTo(element) < 0) {
                if (node.left == null) {
                    node.left = new Node(element);
                    return true;
                } else {
                    return add(node.left, element);
                }
            } else if (node.compareTo(element) > 0) {
                if (node.right == null) {
                    node.right = new Node(element);
                    return true;
                } else {
                    return add(node.right, element);
                }
            } else {
                return false;
            }
        }

        /**
         * 查询元素
         *
         * @param element
         * @return
         */
        public Node find(int element) {
            if (root == null) {
                return null;
            }
            return find(root, element);
        }

        /**
         * 查询元素（递归）
         *
         * @param node
         * @param element
         * @return
         */
        private Node find(Node node, int element) {
            if (node == null) {
                return null;
            }
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {
                return find(node.left, element);
            } else if (compareResult > 0) {
                return find(node.right, element);
            } else {
                return node;
            }
        }

        /**
         * 查找最大值
         *
         * @return
         */
        public Node findMax() {
            return findMax(root);
        }

        /**
         * 查找最大值（递归）
         *
         * @param node
         * @return
         */
        private Node findMax(Node node) {
            if (node.right == null) {
                return node;
            }
            return findMax(node.right);
        }

        /**
         * 查找最小值
         *
         * @return
         */
        private Node findMin() {
            return findMin(root);
        }

        /**
         * 查找最小值（递归）
         *
         * @param node
         * @return
         */
        private Node findMin(Node node) {
            if (node.left == null) {
                return node;
            }
            return findMin(node.left);
        }

        /**
         * 顺序输出
         */
        public void orderPrint() {
            orderPrint(root);
        }


        /**
         * 顺序输出（递归）
         *
         * @param node
         */
        private void orderPrint(Node node) {

            if (node == null) {
                return;
            }

            // 递归左子节点
            if (node.left != null) {
                orderPrint(node.left);
            }

            // 输出当前节点
            System.out.println(node.element);

            // 递归右子节点
            if (node.right != null) {
                orderPrint(node.right);
            }

        }

        /**
         * 是否包含某值
         *
         * @param element
         * @return
         */
        public boolean contains(int element) {
            if (find(element) == null) {
                return false;
            }
            return true;
        }

        /**
         * 删除目标元素
         *
         * @param element
         * @return
         */
        public boolean remove(int element) {
            if (root == null) {
                return false;
            }
            // 如果删除的元素是root
            if (root.compareTo(element) == 0) {
                if (root.right == null) {
                    root = root.left;
                } else {
                    root.right.left = root.left;
                    root = root.right;
                }
                return true;
            }
            return remove(null, root, element);
        }

        /**
         * 删除目标元素（递归），有三种情况：
         * （1）目标元素为叶子节点
         * （2）目标元素即有左子树，也有右子树
         * （3）目标元素只有左子树，或只有右子树
         *
         * @param parentNode 当前节点的父节点
         * @param node       当前节点（若当前节点上的元素与要删除的元素匹配，则删除当前节点）
         * @param element    要删除的元素
         * @return
         */
        private boolean remove(Node parentNode, Node node, int element) {
            if (node == null) {
                return false;
            }
            // 先找到目标元素
            int compareResult = node.compareTo(element);
            if (compareResult < 0) {
                return remove(node, node.left, element);
            }
            if (compareResult > 0) {
                return remove(node, node.right, element);
            }

            // 找到目标元素，判断该节点是父节点的左子树还是右子树
            boolean isLeftOfParent = false;
            if (parentNode.left != null && parentNode.left.compareTo(element) == 0) {
                isLeftOfParent = true;
            }

            // 删除目标元素
            if (node.left == null && node.right == null) { // （1）目标元素为叶子节点，直接删除
                if (isLeftOfParent) {
                    parentNode.left = null;
                } else {
                    parentNode.right = null;
                }
            } else if (node.left != null && node.right != null) { // （2）目标元素即有左子树，也有右子树
                // 找到右子树最小值（叶子节点），并将其删除
                Node minNode = findMin(node.right);
                remove(minNode.element);
                // 将该最小值替换要删除的目标节点
                minNode.left = node.left;
                minNode.right = node.right;
                if(isLeftOfParent) {
                    parentNode.left = minNode;
                } else {
                    parentNode.right = minNode;
                }

            } else { // （3）目标元素只有左子树，或只有右子树
                if (isLeftOfParent) {
                    parentNode.left = node.left != null ? node.left : node.right;
                } else {
                    parentNode.right = node.left != null ? node.left : node.right;
                }
            }
            return true;
        }
    }

    private static class Node implements Comparable<Integer> {
        private final Integer element; // 数据元素
        private Node left; // 左子树
        private Node right; // 右子树

        private Node(Integer element) {
            this.element = element;
        }

        @Override
        public int compareTo(Integer o) {
            return o.compareTo(element);
        }

        @Override
        public String toString() {
            return "Node{" +
                    "element=" + element +
                    '}';
        }
    }
}

输出结果：

----------------------添加元素
添加元素[5] --> true
添加元素[2] --> true
添加元素[7] --> true
添加元素[1] --> true
添加元素[4] --> true
添加元素[3] --> true
添加元素[7] --> false
添加元素[6] --> true
添加元素[9] --> true
添加元素[8] --> true
----------------------顺序输出（中序遍历）
1
2
3
4
5
6
7
8
9
----------------------查找元素
Node{element=7}
----------------------查找最小元素
Node{element=1}
----------------------查找最大元素
Node{element=9}
----------------------是否包含元素
是否包含[0] --> 	false
是否包含[2] --> 	true
----------------------删除目标元素
删除[0] --> 	false
1
2
3
4
5
6
7
8
9
删除[1] --> 	true
2
3
4
5
6
7
8
9
删除[4] --> 	true
2
3
5
6
7
8
9
删除[7] --> 	true
2
3
5
6
8
9

1. 定义算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作 2. 五个基本特性输入和输出算法具有零个或多个输入算法至少有一个或多个输出有穷性指算法在执行有限的步骤后，自动结束而不会出现循环，并且每一个步骤在可接受的时间内完成实际应用中合理的，可以接受的“有边界”确定性算法的每一步骤都具有确定的含义，不会出现二义性算法在一定条件下，只有一条执行路径，相同的输入...

浅谈算法和数据结构: 六符号表及其基本实现【代码】【图】

前面几篇文章介绍了基本的排序算法，排序通常是查找的前奏操作。从本文开始介绍基本的查找算法。在介绍查找算法，首先需要了解符号表这一抽象数据结构，本文首先介绍了什么是符号表，以及这一抽象数据结构的的API，然后介绍了两种简单的符号表的实现方式。一符号表在开始介绍查找算法之前，我们需要定义一个名为符号表（Symbol Table）的抽象数据结构，该数据结构类似我们再C#中使用的Dictionary，他是对具有键值对元素的一种抽象，...

数据结构和算法绪论（一）【图】

1、什么是数据结构？程序设计=数据结构+算法物理结构+逻辑结构=数据结构一、4大逻辑结构：集合结构，线性结构，树形结构，图形结构，二、物理结构顺序存储结构，链式存储结构，（指针也需要存储空间）原文：https://www.cnblogs.com/zhzJAVA11/p/9896616.html

MySQL索引背后的数据结构及算法原理

摘要本文以MySQL数据库为研究对象，讨论与数据库索引相关的一些话题。特别需要说明的是，MySQL支持诸多存储引擎，而各种存储引擎对索引的支持也各不相同，因此MySQL数据库支持多种索引类型，如BTree索引，哈希索引，全文索引等等。为了避免混乱，本文将只关注于BTree索引，因为这是平常使用MySQL时主要打交道的索引，至于哈希索引和全文索引本文暂不讨论。文章主要内容分为三个部分。第一部分主要从数据结构及算法理论层面讨论M...

数据结构算法【代码】【图】

#include<iostream> usingnamespace std;/* 算法算法概念算法是特定问题求解步骤的描述在计算机中表现为指令的有限序列算法是独立存在的一种解决问题的方法和思想。对于算法而言，语言并不重要，重要的是思想。算法和数据结构区别数据结构只是静态的描述了数据元素之间的关系高效的程序需要在数据结构的基础上设计和选择算法程序=数据结构+算法总结：算法是为了解决实际问题而设计的数据结构是算法需要处理的问题载体数据...

【数据结构】算法 Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历【代码】【图】

目录Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历TagBinary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历给一个二叉树的root，返回其节点值从上到下遍历，奇数层从左到右遍历，偶数层从右到左。Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]] /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right...

数据结构和算法【代码】

找出那个特殊的字母给定两个字符串s和t，它们只包含小写字母。字符串t由字符串s随机重排，然后在随机位置添加一个字母。请找出在t中被添加的字母。示例如果字符串s = "abcd";，t = "abdec";，则输出为e。方法一：使用异或运算求和char FindTheDiffAlp(const std::string s, const std::string t) {const std::string st = s + t;char c = 0;for (std::size_t i = 0; i < st.size(); ++i) {c ^= st.at(i);}return c; }方法二：分别...

Java数据结构和算法（十二）——2-3-4树【代码】【图】

通过前面的介绍，我们知道在二叉树中，每个节点只有一个数据项，最多有两个子节点。如果允许每个节点可以有更多的数据项和更多的子节点，就是多叉树。本篇博客我们将介绍的——2-3-4树，它是一种多叉树，它的每个节点最多有四个子节点和三个数据项。1、2-3-4 树介绍　　2-3-4树每个节点最多有四个字节点和三个数据项，名字中 2,3,4 的数字含义是指一个节点可能含有的子节点的个数。对于非叶节点有三种可能的情况：　　①、有一个数...

《常见算法与数据结构》符号表ST（3）——二叉查找树（附动画）【代码】【图】

符号表（3）——二叉查找树本系列文章主要介绍常用的算法和数据结构的知识，记录的是《Algorithms I/II》课程的内容，采用的是“算法（第4版）”这本红宝书作为学习教材的，语言是java。这本书的名气我不用多说吧？豆瓣评分9.4，我自己也认为是极好的学习算法的书籍。通过这系列文章，可以加深对数据结构和基本算法的理解（个人认为比学校讲的清晰多了），并加深对java的理解。符号表3二叉查找树二叉查找树1 代码框架2 节点表示3 取...

第4章数据结构算法【代码】

py内置数据结构算法常考常用内置的算法和数据结构sorted list/set/dict/tuple常用内置数据结构和算法数据结构/算法语言内置内置库线性结构list(列表)/tuple(元组)array(数组, 不常用)/collections.namedtuple链式结构collections.deque(双端队列)字典结构dict(集合)collections.Counte(计数器)/OrderedDict(有序字典)集合结构set(集合)/frozenset(不可变集合)排序算法sorted二分算法bisect模块堆算法heapq模块缓存算法functools.lr...

数据结构 - 相关标签

数据结构导论数据结构是什么数据结构习题数据结构严蔚敏数据结构与算法分析

算法 - 最热教程

浅谈SQLServer查询优化器中的JOIN算法有没那种可逆算法是密文比明文短的呢？...javascript-类似Excel里面的NORMDIST函...C++中的分治算法及常见题目汇总压缩感知重构算法综述-学习笔记 c++中内置函数qsort（快速排序）和bsea...一、fpga图像处理算法整合基于遗传算法（deap）的非线性函数寻优...集成学习-Bagging集成学习算法随机森林...机器学习笔记（九）聚类算法及实践（K-...

首页 / 算法 / 『数据结构与算法』二叉查找树（BST）

『数据结构与算法』二叉查找树（BST）

内容导读

内容图文

1. 二叉查找树（Binary Search Tree）

2. BST的实现

2.1 节点类

2.2 二叉查找树类

3. 插入节点

4. 查找节点

5. 遍历节点

6. 删除节点

6.1 目标元素为叶子节点

6.2 目标元素即有左子树，也有右子树

6.3 目标元素只有左子树，或只有右子树

7. 完整代码

推荐阅读

内容总结

内容备注

内容手机端

【『数据结构与算法』二叉查找树（BST）】教程文章相关的互联网学习教程文章

数据结构：二算法

浅谈算法和数据结构: 六符号表及其基本实现【代码】【图】

数据结构和算法绪论（一）【图】

MySQL索引背后的数据结构及算法原理

数据结构算法【代码】【图】

【数据结构】算法 Binary Tree Zigzag Level Order Traversal 二叉树的锯齿形层序遍历【代码】【图】

数据结构和算法【代码】

Java数据结构和算法（十二）——2-3-4树【代码】【图】

《常见算法与数据结构》符号表ST（3）——二叉查找树（附动画）【代码】【图】

第4章数据结构算法【代码】

Java数据结构和算法之栈与队列【图】

数据结构和算法_队列

【uva 1471】Defense Lines（算法效率--使用数据结构）

数据结构和算法————二分查找【代码】

数据结构与算法-数据结构和算法概述、评判程序优劣、数据结构【代码】

数据结构 - 相关标签

算法 - 相关标签

算法 - 最新教程

算法 - 最热教程