二叉排序树查找过程的描述是一个递归过程，若用链式存储结构存储，其查找操作的递归算法如下所示：typedefstructNODE{ ElemType elem; /*数据元素字段*/structNODE *lc,*rc; /*左、右指针字段*/}NodeType; /*二叉树结点类型*/第30页，共73页，星期日，2025年，2月5日intSearchElem(NodeType*t,NodeType**p,NodeType**q,KeyTypekx){/*在二叉排序树t上查找关键码为kx的元素，若找到，返回1，且q指向该结点，p指向其父结点；*//*否则，返回0，且p指向查找失败的最后一个结点*/int flag=0; *q=t;while(*q) /*从根结点开始查找*/{ if(kx(*q)-elem.key) /*kx大于当前结点*q的元素关键码*/ {*p=*q; *q=(*q)-rc; }/*将当前结点*q的右子女置为新根*/ else {if(kx(*q)-elem.key) /*kx小于当前结点*q的元素关键码*/ {*p=*q; *q=(*q)-lc;} /*将当前结点*q的左子女置为新根*/ else {flag=1;break;} /*查找成功，返回*/ } }/*while*/ returnflag;}第31页，共73页，星期日，2025年，2月5日intSearchBST(BSTreeT,KeyTypekval,BSTreef,BSTreep)
{
//根指针T所指二叉查找树中递归查找关键字等于kval的数据元素,若查找成
//功,则指针p指向该数据元素结点,并返回TRUE,否则指针p指向查找路径上访
//问的最后一个结点并返回FALSE,指针f指向T的双亲,其初始调用值为NULL
if(!T){p=f;return0;}//查找不成功
elseif(key==T-data.key)
{p=T;return1;}//查找成功
elseif(keyT-data.key)
returnSearchBST(T-lchild,key,T,p);
//返回在左子树中继续查找所得结果
elsereturnSearchBST(T-rchild,key,T,p);
//返回在右子树中继续查找所得结果
}//SearchBST第32页，共73页，星期日，2025年，2月5日7.3.3二叉排序树的插入在一棵二叉排序树中插入一个结点可以用一个递归的过程实现，即：若二叉排序树为空，则新结点作为二叉排序树的根结点；否则，若给定结点的关键字值小于根结点关键字值，则插入在左子树上；若给定结点的关键字值大于根结点的值，则插入在右子树上。第33页，共73页，星期日，2025年，2月5日下面是二叉排序树插入操作的递归算法。intInsertNode(NodeType*t,KeyTypekx){ /*在二叉排序树*t上插入关键码为kx的结点*/NodeType*p=*t,*q,*s; intflag=0; if(!SearchElem(*t,p,q,kx)); /*在*t为根的子树上查找*/ {s=(NodeType*)malloc(sizeof(NodeType));/*申请结点，并赋值*/ s-elem.key=kx;s-lc=NULL;s-rc=NULL; flag=1; /*设置插入成功标志*/if(!p)t=s; /*向空树中插入时*/ else {if(kxp-elem.key)p-rc=s;/*插入结点为p的右子女*/ else p-lc=s; /*插入结点为p的左子女*/ } }第34页，共73页，星期日，2025年，2月5日这个算法也可以用非递归的形式实现，如下所示：voidbt_insert2(Bin_Sort_Tree*bt,Bin_Sort_Tree_Node*pn){p=bt; while(p!=NULLp-key!=pn-key){q=p;if(p-keypn-key)p=p-