一、数据结构
二叉查找树基于二叉树，每个节点储存着键和值，以及指向左右子树的链接，一颗二叉查找树代表了一组键值对的集合，类似于python中的字典（字典中的键值对储存是无序的）。在这里我们规定节点左子树中的节点的键都小于它，右子树中的节点都大于它，如果我们将所有节点向下投影到一条线上，可以得到一条有序的序列。
二、主要方法（默认为递归实现）
部分方法的迭代实现在末尾展示
1、查找和排序
在符号表中查找一个键，从根节点开始，如果节点的键和被查找的键相等，就返回节点的值，如果节点的值大于被查找的键的值，就在节点的左子树中查找，反之在右子树中查找，直到节点为空或查找命中。如果键在符号表中则查找命中，返回键对应的值，如果键不在符号表中则未命中，返回null（null为指向一个它可能会存在的空节点的链接）
在上一篇结尾处引入的方法有许多都用到了这个算法：
1 public Value get(Key key) {// 通过键从符号表中获取对应的值，返回键key对应的值 2 return get(root, key); 3 } 4 5 private Value get(Node x, Key key) {// 递归 6 if (key == null) { 7 return null; 8 } 9 int cmp = key.compareTo(x.key); 10 if (cmp < 0) { 11 return get(x.left, key); 12 } else if (cmp > 0) { 13 return get(x.right, key); 14 } else 15 return x.val; 16 } 17 18 19 public void put(Key key, Value val) {//修改或添加节点 20 root = put(root, key, val); 21 } 22 23 private Node put(Node x, Key key, Value val) { 24 if (x == null) {// 创建新节点 25 return new Node(key, val, 1); 26
