前文介绍了符号表的两种实现，无序链表和有序数组，无序链表在插入的时候具有较高的灵活性，而有序数组在查找时具有较高的效率，本文介绍的二叉查找树(Binary Search Tree，BST)这一数据结构综合了以上两种数据结构的优点。
二叉查找树具有很高的灵活性，对其优化可以生成平衡二叉树，红黑树等高效的查找和插入数据结构，后文会一一介绍。
一 定义
二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树：
1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树。
4. 没有键值相等的节点（no duplicate nodes）。
如下图，这个是普通的二叉树：
在此基础上，加上节点之间的大小关系，就是二叉查找树：
二 实现
在实现中，我们需要定义一个内部类Node，它包含两个分别指向左右节点的Node，一个用于排序的Key，以及该节点包含的值Value，还有一个记录该节点及所有子节点个数的值Number。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
public class BinarySearchTreeSymbolTable<TKey, TValue> : SymbolTables<TKey, TValue> where TKey : IComparable<TKey>, IEquatable<TValue> { private Node root; private class Node { public Node Left { get; set; } public Node Right { get; set; } public int Number { get; set; } public TKey Key { get; set; } public TValue Value { get; set; } public Node(TKey key, TValue value, int number) { this.Key = key; this.Value = value; this.Number = number; } } ... } |
查找
查找操作和二分查找类似，将key和节点的key比较，如果小于，那么就在Left Node节点查找,如果大于，则在Right Node节点查找，如果相等，直接返回Value。
该方法实现有迭代和递归两种。
递归的方式实现如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
public override TValue Get(TKey key) { TValue result = default(TValue); Node node = root; while (node != null) { if (key.CompareTo(node.Key) > 0) { node = node.Right; } else if (key.CompareTo(node.Key) < 0) { node = node.Left; } else { result = node.Value; break; } } return result; } |
迭代的如下：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public TValue Get(TKey key) { return GetValue(root, key); } private TValue GetValue(Node root, TKey key) { if (root == null) return default(TValue); int cmp = key.CompareTo(root.Key); if (cmp > 0) return GetValue(root.Right, key); else if (cmp < 0) return GetValue(root.Left, s="crayon-h"> 0) return GetValue(root.Left, 有序数组在查找时具有较高的效率，本文介绍的二叉查找树(Binary Search Tree，BST)这一数据结构综合了以上两种数据结构的优点。
二叉查找树具有很高的灵活性，对其优化可以生成平衡二叉树，红黑树等高效的查找和插入数据结构，后文会一一介绍。 一 定义二叉查找树（Binary Search Tree），也称有序二叉树（ordered binary tree）,排序二叉树（sorted binary tree），是指一棵空树或者具有下列性质的二叉树： 1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 2. 若任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 3. 任意节点的左、右子树也分别为二叉查找树。 4. 没有键值相等的节点（no duplicate nodes）。 如下图，这个是普通的二叉树：
在此基础上，加上节点之间的大小关系，就是二叉查找树：
二 实现在实现中，我们需要定义一个内部类Node，它包含两个分别指向左右节点的Node，一个用于排序的Key，以及该节点包含的值Value，还有一个记录该节点及所有子节点个数的值Number。
查找查找操作和二分查找类似，将key和节点的key比较，如果小于，那么就在Left Node节点查找,如果大于，则在Right Node节点查找，如果相等，直接返回Value。
该方法实现有迭代和递归两种。 递归的方式实现如下：
迭代的如下：
|
