动态查找表定义二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个作为查找依据的关键字(key)，所有结点的关键字互不相同；左子树(如果存在)上所有结点的关键字都小于根结点的关键字；右子树(如果存在)上所有结点的关键字都大于根结点的关键字。左子树和右子树也是二叉排序树。35在二叉排序树上进行搜索，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它可以是一个递归的过程。假设要在二叉排序树中搜索关键字为x的元素，查找过程从根结点开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键字进行比较：如果给定值等于根结点的关键字，则查找成功。如果给定值小于根结点的关键字，则继续递归查找根结点的左子树；否则递归查找根结点的右子树。35BiTreeSearchBST(BiTreeT,KeyTypekey){//在根指针T所指二叉排序树中递归地查找某关键字等于key的数据元素，若查找成功，则返回指向该数据元素的指针，否则返回空指针。if((!T)║EQ(key,T->data.key))return(T);//查找结束elseif(LT(key,T->data.key))return(SearchBST(T->lchild,key));//在左子树中继续查找elsereturn(SearchBST(T->rchild,key));//在右子树中继续查找}//SearchBST二叉排序树的插入为了向二叉排序树中插入一个新元素，必须先检查这个元素是否在树中已经存在。在插入之前，先使用查找算法在树中检查要插入的元素是否已经存在。查找成功:树中已有这个元素,不再插入。查找不成功:树中原来没有关键字等于给定值的结点，把新元素加到查找操作停止的地方。二叉排序树的建立过程实际就是一个在二叉排序树上不断插入新元素的过程。插入算法：P228算法9.6输入数据，建立二叉排序树同样3个数据{1,2,3}，输入顺序不同，建立起来的二叉排序树的形态也不同，这直接影响到二叉排序树的查找性能。如果输入序列选得不好，会建立起一棵单支树，使得二叉排序树的高度达到最大。{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}二叉排序树的删除被删结点缺左子树，可以拿它的右子女结点顶替它的位置，再释放它。被删结点左、右子树都存在，可以在它的右子树中寻找中序下的第一个结点(或在它的左子树中寻找中序下的最后一个结点),用它的值填补到被删结点中，再来处理这个结点的删除问题。88平衡二叉树（AVL树）