二分搜索树基础

一、树结构本身是一种天然的组织结构

将数据使用树结构后，出奇的高效。

二、二叉树

和链表一样，动态数据结构

　　class Node{

　　　　E e;

　　　　Node left;

　　　　Node right;

　　}

二叉树（多叉树）

二叉树具有唯一根节点

　　class Node{

　　　　E e;

　　　　Node left;　　<-- 左孩子　　

　　　　Node right;　　<-- 右孩子

　　}

二叉树每个节点最多有两个孩子节点

二叉树每个节点最多有一个父节点

二叉树具有天然递归结构

　　每个节点的左子树也是二叉树

　　每个节点的右子树也是二叉树

二叉树不一定是“满”的，

如： 10 一个节点也是二叉树

NULL 空也是二叉树

三、二分搜索树（Binary Search Tree）

二分搜索树是二叉树

二分搜索树的每个节点的值：

　　大于其左子树的所有节点的值

　　小于其右子树的所有节点的值

每一棵子树也是二分搜索树

存储的元素必须有可比较性

 1 public class BST<E extends Comparable<E>> {
 2     
 3     private class Node {
 4         public E e;
 5         public Node left, right;
 6         
 7         public Node(E e) {
 8             this.e = e;
 9             left = null;
10             right = null;
11         }
12     }
13     
14     private Node root;
15     private int size;
16     
17     public BST(){
18         root = null;
19         size = 0;
20     }
21     
22     public int size(){
23         return size;
24     }
25     
26     public boolean isEmpty(){
27         return size == 0;
28     }
29     
30     // 向二分搜索树中添加新的元素e
31     public void add(E e){
32         if(null == root){
33             root = new Node(e);
34             size++;
35         }else{
36             add(root,e); // 待写
37         }
38 
39         //size++;
40     }
41 
42     
43     // 向以node为根的二分搜索树中插入元素e，递归算法
44     private void add(Node node, E e){
45         /*
46         if(null == node || node.e == e){ // 注意区分 == 与 equals 的区别
47             node = new Node(e);
　　　　　　　　　size++;
48             return;
49         }else if(node.e > e){
50             add(node.left,e);
51         }else{
52             add(node.right,e);
53         }
54         */
55         if(e.equals(node.e)){
56             return;
57         }else if(e.compareTo(node.e) < 0 && null == node.left){
58             node.left = new Node(e);
59             size++;
60             return;
61         }else if(e.compareTo(node.e) > 0 && null == node.right){
62             node.right = new Node(e);
63             size++;
64             return;
65         }
66 
67         if(e.compareTo(node.e) < 0 ){
68             add(node.left, e);
69         }else{
70             add(node.right, e);
71         }
72 
73     }
74 }

add 的改进

 1  // 向二分搜索树中添加新的元素e
 2 31     public void add(E e){
 3            root = add(root,e);
 4 40     }
 5 41 
 6 42     
 7 43     // 向以node为根的二分搜索树中插入元素e，递归算法
 8 44     private Node add(Node node, E e){
 9 45        
10 55         if(null == node){
11                  size++;
12 56             return new Node(e);
13 57         }else if(e.compareTo(node.e) < 0){
14 58             node.left = add(node.left, e);
15 61         }else if(e.compareTo(node.e) > 0){
16 62             node.right = add(node.right, e);
17 65         }
18 74 }

二分搜索树基础

推荐阅读