详解二分搜索树

桃扇骨 2022-04-23 20:38 190阅读 0赞

## 二分搜索树 ##

**介绍**  
树结构在计算机领域应用极其广泛，树结构也分为多种，二叉树，完全二叉树和满二叉树，二分搜索树是一棵二叉树。  
**特点**

1.  动态数据结构。
2.  一棵二叉树。
3.  每个节点的值大于其左子树的所有节点的值。
4.  每个节点的值小于其右子树的所有节点的值。
5.  每一棵子树都是一棵二分搜索树。
6.  一般不存在可重复的元素，当然也可以定义重复元素。
7.  自身就具有很自然的递归特性。
8.  二叉树不一定是"满"的。
9.  一个节点也是二叉树
10. 空也是二叉树  
    **示例**  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]  
    以上这个二叉树都可以看出来它的特点：每个节点的值大于其左子树的所有节点的值，小于其右子树的所有节点的值。  
    **添加元素**  
    既然是动态的数据结构，就肯定擅长添加元素，上一篇博客讲解了递归的使用，所以这里用递归地实现方式。  
    首先写一个节点类  
    然后定义一个公共的add方法，用于添加元素并且判断头节点是否为空，如果为空添加头节点。  
    再定义一个递归的add方法进行递归逻辑的实现。

public class BST<E extends Comparable<E>> {
    
        private class Node {
            public E e;
            public Node left, right;
    
            public Node(E e) {
                this.e = e;
                left = null;
                right = null;
            }
        }
    
        private Node root;
        private int size;
    
        public BST(){
            root = null;
            size = 0;
        }
    
        public int size(){
            return size;
        }
    
        public boolean isEmpty(){
            return size == 0;
        }
    
        // 向二分搜索树中添加新的元素e
        public void add(E e){
    
            if(root == null){
                root = new Node(e);
                size ++;
            }
            else
                add(root, e);
        }
    
        // 向以node为根的二分搜索树中插入元素e，递归算法
        private Node add(Node node, E e){
            if(e.equals(node.e))
                return;
            else if(e.compareTo(node.e) < 0 && node.left == null){
                node.left = new Node(e);
                size ++;
                return;
            }
            else if(e.compareTo(node.e) > 0 && node.right == null){
                node.right = new Node(e);
                size ++;
                return;
            }
    
            if(e.compareTo(node.e) < 0)
                add(node.left, e);
            else //e.compareTo(node.e) > 0
                add(node.right, e);
        }
        public static void main(String[] args) {
            BST bst = new BST();
            bst.add(32);
            bst.add(22);
            bst.add(16);
            bst.add(18);
            bst.add(26);
            bst.add(22);
            bst.add(28);
            bst.add(40);
            bst.add(50);
            bst.add(44);
            bst.add(58);
        }
    }

**改进添加元素**  
直接在add的递归方法中使用判断node是否为空的方法，如果为空的话就直接进行添加，之前用了两次判断，一次是判断左右子树是否为空，另一个是调用递归方法，这样的话太麻烦，在add方法中进行优化。

if (node == null){
                size++;
                return new Node(e);
            }
    
            if (e.compareTo(node.e)<0)
                node.left = add(node.left,e);
            else if (e.compareTo(node.e)>0)
                node.right = add(node.right,e);
            return node;

**查询二叉树元素**  
传进去一个元素值，然后遍历二叉树进行查询。

//递归查询二叉树元素
        public boolean contains(E e){
            return contains(root,e);
        }
        private boolean contains(Node node,E e){
            if (node == null)
                return false;
            if (e.compareTo(node.e)==0)
                return true;
            else if (e.compareTo(node.e)<0)
                return contains(node.left,e);
            else
                return contains(node.right,e);
        }

**遍历二叉树**  
遍历二叉树分为深度优先遍历和广度优先遍历。  
深度优先遍历又分为前序遍历，中序遍历和后序遍历三种方式  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 1]

1.  前序遍历  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 2]

public void preOrderTraverse(Node<E> node) {
            System.out.print(node.value + " ");
            if (node.left != null)
                preOrderTraverse(node.left);
            if (node.right != null)
                preOrderTraverse(node.right);
        }

1.  中序遍历  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 3]

public void inOrderTraverse(Node<E> node) {
            if (node.left != null)
                inOrderTraverse(node.left);
            System.out.print(node.value + " ");
            if (node.right != null)
                inOrderTraverse(node.right);
        }

1.  后序遍历  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 4]

public void postOrderTraverse(Node<E> node) {
            if (node.left != null)
                postOrderTraverse(node.left);
            if (node.right != null)
                postOrderTraverse(node.right);
            System.out.print(node.value + " ");
        }

1.  广度优先

public void breadthFirstTraverse(Node<E> root) {
            Queue<Node<E>> queue = new LinkedList<Node<E>>();
            Node<E> currentNode = null;
            queue.offer(root);
            while (!queue.isEmpty()) {
                currentNode = queue.poll();
                System.out.print(currentNode.value + " ");
                if (currentNode.left != null)
                    queue.offer(currentNode.left);
                if (currentNode.right != null)
                    queue.offer(currentNode.right);
            }
        }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70]: /images/20220222/93883c3ab7ba4bc1a8e41dd52e99084c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 1]: /images/20220222/db2ae0288b1c4d0c997a9c5d7eca089b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 2]: /images/20220222/23d089ed31b845a2ac00807b199f34dd.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 3]: /images/20220222/8ba49ebdf8b8464186128200c238ea0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MTA1MTE1_size_16_color_FFFFFF_t_70 4]: /images/20220222/4433ef5bc3d142588e4bed017f65e8f1.png