9.25 FUNC SqSearch(s:SqList; k:KeyType):integer;
(监视哨设在降序顺序表高下标端，顺序查找关键字为K的数据元素。若存在，)
{则返回其在顺序表中的位置，否则，返回0}
r[n+1].key:=K; i:=1;
WHILE r[i].key>K DO i:=i+1;
IF r[I].key=K THEN return(i MOD (n+1))
ELSE return(0)
查找过程的判定树是单支树。
查找成功的平均查找长度为
ASL=∑PICI =1/n*∑i = 1/2*(n+1)
查找不成功的平均查找长度为 ASL=1/(n+1)(∑i+(n+1))=(n+2)/2
9.26 FUNC BinSearch(s:SqList;low,high:integer;K:KeyType):integer;
{在有序的顺序表s的s.elem[low..high]中递归地折半查找关键字为K的数}
{据元素，若存在，则返回其在有序顺序表中的位置，否则，返回0。found是}
{全程变量，调用时初值是false，返回后判其值，如未变，则未查到）
IF (low<=high) AND NOT FOUND THEN
[ mid:=(low+high) DIV 2;
IF s.elem[mid].key<K
THEN BinSearch:=BinSearch(s,mid+1,high,K)
ELSE IF s.elem[mid].key>K
THEN BinSearch:=BinSearch(s,low,mid-1,K)
ELSE [ BinSearch:= mid; found:=true]
]
9.31 FUNC BiSortTree(t:BiTree; VAR pre:
BiTree ):Boolean;
(二叉排序树的判定。Pre为指向当前访问的结点的前驱结点的指针，起初值)
（为NIL。FALG是标志，初值为true）
IF (t<>NIL) AND flag
THEN
[
flag:=BiSortTree(t^.lchild,pre)
IF pre=NIL
THEN pre:=t
ELSE IF pre^.data > t^.data THEN flag:=false
ELSE pre:=t;
IF flag THEN flag:=BiSortTree(t^.rchild,pre)
]
9.33 PROC OrderedOut(t:BiTree; x:KeyType
);
(递归地从大到小输出二叉排序树t中所有关键字不小于x的元素。)
{found是全程变量，调用本过程时初值是false}
IF
NOT found THEN
[IF t^.rchild<>NIL
THEN OrderedOut(t^.rchild,x)
IF t^.data >=x THEN write(t^.data) ELSE found:=true;
IF NOT found AND (t^.lchild<>NIL) THEN OrderedOut(t^.lchild,x)
]
**** PROC Insert( VAR t:BiTree; K:KeyType) {增加题}
{在二叉排序树t上插入关键字为K的结点。 算法思想是首先查找，若有}
{,found为true，则不必插入；否则，在适当位置插入之。Found初值false}
IF NOT found THEN
IF t=NIL
THEN [new(s); s^.data:=K; s^,lchild:=s^.rchild:=NIL;t:=s]
ELSE IF t^.data=K
THEN found:=true
ELSE IF K<t^.data
THEN IF t^.lchild=NIL
THEN [new(s); s^.data:=K;
s^,lchild:=s^.rchild:=NIL;
t^.lchild:=s
]
ELSE Insert(t^.lchild, K)
ELSE IF t^.rchild=NIL
THEN [new(s); s^.data:=K;
s^,lchild:=s^.rchild:=NIL;
t^.rchild:=s
]
ELSE Insert(t^.rchild, K)
{ END OF 插入关键字为K 的结点}
**** PROC Delete( VAR t:BiTree; K:KeyType) {增加题}
{在二叉排序树t上删除关键字为K的结点. 算法思想是首先查找，}
{若有,则删除，q是当前结点p的双亲结点 }
p:=t; q:=NIL; found:=false;
WHILE (p<>NIL) AND NOT found DO {查找关键字为K的结点}
IF p^.data=K
THEN found:=true
ELSE IF K<p^.data
THEN [q:=p; p:=p^.lchild]
ELSE [q:=p; p:=p^.rchild]
IF p=NIL
THEN write(‘无关键字为K的结点’)
ELSE IF p^.lchild=NIL {关键字为K的结点无左子女}
THEN IF q=NIL THEN t:=p^.rchild {关键字为K的结点是根}
ELSE IF q^.lchild=p THEN q^.lchild:=p^.rchild
ELSE q^.rchild:=p^.rchild
ELSE[ {关键字为K的结点有左子树，查左子树在中序遍历下}
{的最后结点，以便将被删结点的右子树作为该结点的}
{右子树。最后删除关键字为K的结点}
r:=p^.lchild;
WHILE r^.rchild<>NIL DO r:=r^.rchild
r^.rchild:=p^.rchild {链入关键字为K的结点的右子女}
IF q=NIL THEN t:=p^.lchild {被删结点是根}
ELSE IF q^.lchild=p THEN q^.lchild:=p^.lchild
ELSE q^.rchild:=p^.lchild
]