文档介绍：排序二叉树 Binary Sort Tree 线性表知识回顾数组静态实现链表实现线性表知识回顾数组静态实现 data:array of [1..maxn] of integer 查找: 顺序查找 O(n ) 二分查找 O(logn ) 插入: O(n ) 删除: O(n ) 数组静态实现(查找) data:array of [1..maxn] of integer 查找: 顺序查找 O(n ) Function search(x:longint):longint ; {返回关键字为 x的节点编号,如不存在返回 0} var i:longint;b:boolean ; Begin i:=1;b:=false; while (i<= n)and not(b ) do if data[i ]=x then begin search:= i;b := true;end ; if i>n then search:=0; End; 数组静态实现(查找) data:array of [1..maxn] of integer 查找: 二分查找 O(logn ) Function search(x,i,j:longint):longint ; {在i至j范围内查找,返回关键字为 x的节点编号,如不存在返回 0} var m:longint ; Begin if i>j then begin search:=0;exit;end; if i=j then if x= data[i ] then search:=i else search:=0 else begin m:=( i+j ) div 2; if x= data[m ] then search:=m if data[m ]>x then search:=search(x,i,m-1); if data[m ]<x then search:=search(x,m+1,j); end; End; 数组静态实现(插入) data:array of [1..maxn] of integer 插入: O(n ) procedure insert(x,k:longint):longint ; {将关键字为 x的节点插入到 k号节点前面} var i:longint ; Begin for i:=n downto k do data[i+1]:= data[i ]; data[k ]:=x; n:=n+1; End; 数组静态实现(删除) data:array of [1..maxn] of integer 删除: O(n ) procedure delete(x:longint ); {删除 k号节点} var i:longint ; Begin for i:=k+1 to n do data[i-1]:= data[i ]; n:=n-1; End;线性表知识回顾链表实现 data:array of [1..maxn,1..2] of integer data[i,2] 表示元素 data[i,1] 的后继编号查找: 顺序查找 O(n ) 插入: O(1) 删除: O(1) data:array of [1..maxn,1..2] of integer Function search(x:longint):longint ; {返回关键字为 x的节点编号,如不存在返回 0,s为根结点编号} var i:longint;b:boolean ; Begin i:= s;b :=false; repeat if data[i,1]=x then begin search:= i;b := true;end else i:=data[i,2] until b or data[s,2]=0; if not(b ) then search:=0; End; 链表实现(查找 O(n )) data:array of [1..maxn,1..2] of integer procedure insert(x,i:longint ); {将关键字为 x的节点插入到 i号节点后面} Begin n:=n+1; data[n,2]:=data[i,2];data[n,1]:=x; dat