树、二叉树、二分搜索树

拼搏现实的明天。 2021-09-23 21:42 387阅读 0赞

## **将数据使用树结构存储后，出去的高效！** ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]

## 二叉树基本概念 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]

## 二叉树也具有天然的递归结构 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]

## 二叉树不一定是“满”的。以下均为二叉树 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]

## 二分搜索树基本概念 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]

**二分搜索树代码示例**

package BinarySearchTree;
    
    //二分搜索树同样也是支持泛型的 但是泛型的类型要可比较
    public class BinarySearchTree<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 BinarySearchTree() { 
            root = null;
            size = 0;
        }
    
        public int size() { 
            return size;
        }
    
        public boolean isEmpty() { 
            return size == 0;
        }
    }

## 二分搜索树添加新元素 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 6]

**复杂写法:**

//向二分搜索树添加新的元素e
        public void add(E e) { 
            if (root == null) { 
                root = new Node(e);
                size++;
            } else { 
                add(root, e);
            }
        }
    
        //向以node为根的二分搜索树插入新的元素e 递归算法
        private void 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.right, e);
            } else { 
                add(node.right, e);
            }
        }

**条理写法:**

//向二分搜索树添加新的元素e
        public void add(E e) { 
            root = add(root, e);
        }
    
        //向以node为根的二分搜索树插入新的元素e 递归算法
        private Node add(Node node, E e) { 
            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;
        }

## 二分搜索树查询操作 ##

//查看二分搜索树是否包含元素e
        private boolean contains(E e) { 
            return contains(root, e);
        }
    
        //查看以node为根的二分搜索树是否包含元素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_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70]: /images/20210923/fe3891684ef54d979a86cd9e9d779093.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 1]: /images/20210923/f163a92f7f5a489ea9f7949fddf78b96.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 2]: /images/20210923/27495967a8774152a0a9e9d470e22062.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 3]: /images/20210923/de272b29ed4c43579f4f9845383b44e7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 4]: /images/20210923/60518e44dbdb4bc58f01e37b85b11cb0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 5]: /images/20210923/57c381471f3d45ef834be6a6a88879ff.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMjI5NTQz_size_16_color_FFFFFF_t_70 6]: /images/20210923/af01f3cfc2484eb9af8b06744a0b1fa2.png