前几节介绍的都是有关静态查找表的相关知识，从本节开始介绍另外一种查找表——动态查找表。
动态查找表中做查找操作时，若查找成功可以对其进行删除；如果查找失败，即表中无该关键字，可以将该关键字插入到表中。
动态查找表的表示方式有多种，本节介绍一种使用
树
结构表示动态查找表的实现方法——二叉排序树（又称为“二叉查找树”）。
什么是二叉排序树？
二叉排序树要么是空
二叉树
，要么具有如下特点：
- 二叉排序树中，如果其根结点有左子树，那么左子树上所有结点的值都小于根结点的值；
- 二叉排序树中，如果其根结点有右子树，那么右子树上所有结点的值都大小根结点的值；
- 二叉排序树的左右子树也要求都是二叉排序树；
例如，
图
1 就是一个二叉排序树：