【专题三】二叉树

1.二叉查找树的创建

1.1二叉树的结点类

根据对图的观察，我们发现二叉树其实就是由一个一个的结点及其之间的关系组成的，按照面向对象的思想，我们设计一个结点类来描述结点这个事物。
结点类API设计：

类名	Node<Key,Value>
构造方法	Node(Key key, Value value, Node left, Node right)：创建Node对象
成员变量	1.public Node left:记录左子结点 2.public Node right:记录右子结点 3.public Key key:存储键 4.public Value value:存储值

代码实现：

private class Node<Key,Value>{
        //存储键
        public Key key;
        //存储值
        private Value value;
        //记录左子结点
        public Node left;
        //记录右子结点
        public Node right;
        public Node(Key key, Value value, Node left, Node right) {
            this.key = key;
            this.value = value;
            this.left = left;
            this.right = right;
        }
}

1.2.二叉查找树API设计

类名	BinaryTree,Value value>
构造方法	BinaryTree()：创建BinaryTree对象
成员变量	1.private Node root:记录根结点 2.private int N:记录树中元素的个数
成员方法	1. public void put(Key key,Value value):向树中插入一个键值对 2.private Node put(Node x, Key key, Value val)：给指定树x上，添加键一个键值对，并返回添加后的新树 3.public Value get(Key key):根据key，从树中找出对应的值 4.private Value get(Node x, Key key):从指定的树x中，找出key对应的值 5.public void delete(Key key):根据key，删除树中对应的键值对 6.private Node delete(Node x, Key key):删除指定树x上的键为key的键值对，并返回删除后的新树 7.public int size():获取树中元素的个数

  1 package cn.itcast.algorithm.Demo.tree;
  2 
  3 
  4 import cn.itcast.algorithm.linear.Queue;
  5 import cn.itcast.algorithm.tree.BinaryTree;
  6 
  7 import java.security.Key;
  8 
  9 public class BinaryTreeDemo<key extends Comparable<key>, Value> {
 10     //成员变量
 11     //1.private Node root:记录根结点
 12     //2.private int N:记录树中元素的个数
 13     private Node root;
 14     private int N;
 15 
 16     public class Node {
 17 
 18         //1.public Node left:记录左子结点
 19         //2.public Node right:记录右子结点
 20         //3.public Key key:存储键
 21         //4.public Value value:存储值
 22         public Node left;
 23         public Node right;
 24         public Key key;
 25         public Value value;
 26 
 27         public Node(Key key, Value value, Node left, Node right) {
 28             this.key = key;
 29             this.value = value;
 30             this.left = left;
 31             this.right = right;
 32         }
 33         //BinaryTree()：创建BinaryTree对象
 34 
 35         //成员方法
 36         //1. public void put(Key key,Value value):向树中插入一个键值对
 37         public void put(Key key, Value value) {
 38             root = put(root, key, value);
 39 
 40         }
 41 
 42         //2.private Node put(Node x, Key key, Value val)：给指定树x上，添加键一个键值对，并返回添加后的新树
 43         private Node put(Node x, Key key, Value value) {
 44            /*
 45            插入方法put实现思想：
 46                 1.如果当前树中没有任何一个结点，则直接把新结点当做根结点使用
 47                 2.如果当前树不为空，则从根结点开始：
 48                 2.1如果新结点的key小于当前结点的key，则继续找当前结点的左子结点；
 49                 2.2如果新结点的key大于当前结点的key，则继续找当前结点的右子结点；
 50                 2.3如果新结点的key等于当前结点的key，则树中已经存在这样的结点，替换该结点的value值即可。
 51             */
 52             //如果x子树为空，
 53             if (x == null) {
 54                 N++;
 55                 return new Node(key, value, null, null);
 56             }
 57             //如果x子树不为空
 58             //比较x结点的键和key的大小：
 59             int cmp = key.compareTo(x.key);
 60             if (cmp > 0) {
 61                 //如果key大于x结点的键，则继续找x结点的右子树
 62                 x.right = put(x.right, key, value);
 63             } else if (cmp < 0) {
 64                 //如果key小于x结点的键，则继续找x结点的左子树
 65                 x.left = put(x.left, key, value);
 66             } else {
 67                 //如果key等于x结点的键，则替换x结点的值为value即可
 68                 x.value = value;
 69             }
 70             return x;
 71         }
 72 
 73         //3.public Value get(Key key):根据key，从树中找出对应的值
 74         public Value get(Key key) {
 75             return get(root, key);
 76         }
 77 
 78         //4.private Value get(Node x, Key key):从指定的树x中，找出key对应的值
 79         private Value get(Node x, Key key) {
 80             /*
 81             查询方法get实现思想：
 82                 从根节点开始：
 83                 1.如果要查询的key小于当前结点的key，则继续找当前结点的左子结点；
 84                 2.如果要查询的key大于当前结点的key，则继续找当前结点的右子结点；
 85                 3.如果要查询的key等于当前结点的key，则树中返回当前结点的value。
 86              */
 87 
 88             //x树为null
 89             if (x == null) {
 90                 return null;
 91             }
 92 
 93             //x树不为null
 94 
 95             //比较key和x结点的键的大小
 96             int cmp = key.compareTo(x.key);
 97             if (cmp > 0) {
 98                 //如果key大于x结点的键，则继续找x结点的右子树
 99                 return get(x.right, key);
100 
101             } else if (cmp < 0) {
102                 //如果key小于x结点的键，则继续找x结点的左子树
103                 return get(x.left, key);
104             } else {
105                 //如果key等于x结点的键，就找到了键为key的结点，只需要返回x结点的值即可
106                 return x.value;
107             }
108         }
109 
110         //5.public void delete(Key key):根据key，删除树中对应的键值对
111         public void delete(Key key) {
112             delete(root, key);
113         }
114 
115         //6.private Node delete(Node x, Key key):删除指定树x上的键为key的键值对，并返回删除后的新树
116         private Node delete(Node x, Key key) {
117             /*
118             删除方法delete实现思想：
119             1.找到被删除结点；
120             2.找到被删除结点右子树中的最小结点minNode
121             3.删除右子树中的最小结点
122             4.让被删除结点的左子树称为最小结点minNode的左子树，让被删除结点的右子树称为最小结点minNode的右子树
123             5.让被删除结点的父节点指向最小结点minNode
124              */
125 
126             //x树为null
127             if (x == null) {
128                 return null;
129             }
130 
131             //x树不为null
132             //比较key和x结点的键的大小
133             int cmp = key.compareTo(x.key);
134             if (cmp > 0) {
135                 //如果key大于x结点的键，则继续找x结点的右子树
136                 return delete(x.right, key);
137             } else if (cmp < 0) {
138                 //如果key小于x结点的键，则继续找x结点的左子树
139                 return delete(x.left, key);
140             } else {
141                 //如果key等于x结点的键，完成真正的删除结点动作，要删除的结点就是x；
142 
143                 //让元素个数-1
144                 N--;
145                 //得找到右子树中最小的结点
146                 if (x.right == null) {
147                     return x.left;
148                 }
149                 if (x.left == null) {
150                     return x.right;
151                 }
152 
153                 Node minNode = x.right;
154                 while (minNode != null) {
155                     minNode = x.left;
156                 }
157 
158                 //删除右子树中最小的结点
159                 Node n = x.right;
160                 while (n.left != null) {
161                     if (n.left.left == null) {
162                         n.left = null;
163                     } else {
164                         //变换n结点即可
165                         n = n.left;
166                     }
167                 }
168                 //让x结点的左子树成为minNode的左子树
169                 minNode.left = x.left;
170                 //让x结点的右子树成为minNode的右子树
171                 minNode.right = x.right;
172                 //让x结点的父结点指向minNode
173                 x = minNode;
174             }
175             return x;
176         }
177 
178         //7.public int size():获取树中元素的个数
179         public int size() {
180             return N;
181         }
182 
183         //8.找出整个树中最小的键
184         public Key min() {
185             return min(root).key;
186         }
187 
188         //找出指定树x中最小的键所在的结点
189         private Node min(Node x) {
190             if (x.left == null) {
191                 return min(x.left);
192             } else {
193                 return x;
194             }
195         }
196 
197         //9.找出整个树中最大的键
198         public Key max() {
199             return max(root).key;
200         }
201 
202         //找出指定树x中最小的键所在的结点
203         private Node max(Node x) {
204             if (x.left == null) {
205                 return max(x.left);
206             } else {
207                 return x;
208             }
209         }
210 
211         //10.前序遍历
212         //使用前序遍历，获取整个树中的所有键
213         public Queue<Key> preErgodic() {
214             Queue<Key> keys = new Queue<>();
215             preErgodic(root, keys);
216             return keys;
217         }
218 
219         //使用前序遍历，把指定树x中的所有键放入到keys队列中
220         private void preErgodic(Node x, Queue<Key> keys) {
221             if (x == null) {
222                 return;
223             }
224             //把x结点的key放入到keys中
225             keys.enqueue(x.key);
226             //递归遍历x结点的左子树
227             if (x.left != null) {
228                 //递归
229                 preErgodic(x.left, keys);
230             }
231 
232             //递归遍历x结点的右子树
233             if (x.right != null) {
234                 preErgodic(x.right, keys);
235             }
236         }
237 
238     }
239 }

View Code

测试代码：

 1 package cn.itcast.algorithm.test;
 2 
 3 import cn.itcast.algorithm.tree.BinaryTree;
 4 
 5 public class BinaryTreeTest {
 6     public static void main(String[] args) {
 7         //创建二叉查找树对象
 8         BinaryTree<Integer, String> tree = new BinaryTree<>();
 9 
10         //测试插入
11         tree.put(1,"张三");
12         tree.put(2,"李四");
13         tree.put(3,"王五");
14         System.out.println("插入完毕后元素的个数："+tree.size());
15 
16         //测试获取
17         System.out.println("键2对应的元素是："+tree.get(2));
18 
19         //测试删除
20 
21         tree.delete(3);
22         System.out.println("删除后的元素个数："+tree.size());
23         System.out.println("删除后键3对应的元素:"+tree.get(3));
24 
25 
26     }
27 
28 }

View Code

2.二叉树的实际应用（应用场景）

哈夫曼编码，来源于哈夫曼树（给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为赫夫曼树(Huffman tree)。即带权路径长度最短的树），在数据压缩上有重要应用，提高了传输的有效性，详见《信息论与编码》。
海量数据并发查询，二叉树复杂度是O(K+LgN)。二叉排序树就既有链表的好处，也有数组的好处，在处理大批量的动态的数据是比较有用。
C++ STL中的set/multiset、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。查找最大（最小）的k个数，红黑树，红黑树中查找/删除/插入，都只需要O(logk)。
B-Tree，B+-Tree在文件系统中的目录应用。
路由器中的路由搜索引擎。