首页 / 软件开发 / 数据结构与算法 / 浅谈算法和数据结构 七 二叉查找树

浅谈算法和数据结构 七 二叉查找树2015-02-27前文介绍了符号表的两种实现，无序链表和有序数组，无序链表在插入的时候具有较高的灵活性，而有序数组在查找时具有较高的效率，本文介绍的二叉查找树（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。

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。