/********************************运行环境：http://www.anycodes.cn/zh/原文：http://blog.csdn.net/u014488381/article/details/41719765/二叉排序树的查找算法的C代码实现修改以直接测试待C++类封装版本*********************************/#include<stdio.h>#include<stdlib.h>typedefintElemtype;typedefstructBiTNode{Elemtypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;/*/在给定的BST中插入结点，其数据域(数值)为element/*/voidBSTInsert(BiTree*t,Elemtypeelement){/*/每次插入开辟空间/*/if(NULL==*t){(*t)=(BiTree)malloc(sizeof(BiTNode));(*t)->data=element;(*t)->lchild=(*t)->rchild=NULL;}/*/依据二叉搜索树性质/*/if(element==(*t)->data)return;/*/不允许有重复的数据，若遇到直接不处理/*/elseif(element<(*t)->data)BSTInsert(&(*t)->lchild,element);elseBSTInsert(&(*t)->rchild,element);}/*/创建BST/*/voidCreateBST(BiTree*t,Elemtype*a,intn){(*t)=NULL;for(inti=0;i<n;i++)BSTInsert(t,a[i]);}/*/BST的递归查找/*/voidSearchBST(BiTreet,Elemtypekey){BiTreep;p=t;if(p){if(key==p->data)printf("查找成功!\n");elseif((key<p->data)&&(NULL!=p->lchild))SearchBST(p->lchild,key);elseif((key>p->data)&&(NULL!=p->rchild))SearchBST(p->rchild,key);elseprintf("无此元素!\n");}}/*/BST的迭代查找/*/void_SearchBST(BiTreet,Elemtypekey){BiTreep;p=t;while(NULL!=p&&key!=p->data)/*/结点存在而数值不等时/*/{if(key<p->data)p=p->lchild;elsep=p->rchild;}/*/走出循环后p指针总是指向找到的元素或者叶子结点下的空结点/*/if(NULL!=p)printf("查找成功!\n");elseprintf("无此元素!\n");}/*/BST结点的删除本二叉树内容重点/*/voidDelBSTNode(BiTreet,Elemtypekey){BiTreep,q;p=t;Elemtypetemp;/*/先遍历找这元素/*/while(NULL!=p&&key!=p->data){q=p;/*/q总是在结点p的上方（当p不是根结点时q总是父亲）p就是我们要删的元素/*/if(key<p->data)p=p->lchild;elsep=p->rchild;}if(NULL==p)printf("无此元素!\n");/*/找到元素会有如下几个情况1.2.3.qqq/\/\/\pppppp/\/\/\xxxxxx/*/else{/*/情况1:结点p的双亲结点为q，且p为叶子结点，则直接将其删除。/*/if(NULL==p->lchild&&NULL==p->rchild){if(p==q->lchild)q->lchild=NULL;if(p==q->rchild)q->rchild=NULL;free(p);p=NULL;}/*/情况2:结点p的双亲结点为q，且p只有左子树或只有右子树，则可将p的左子树或右子树直接改为其双亲结点q的左子树或右子树。/*/elseif((NULL==p->rchild&&NULL!=p->lchild)){/*/p只有左子树/*/if(p==q->lchild)q->lchild=p->lchild;elseif(p==q->rchild)q->rchild=p->lchild;free(p);p=NULL;}elseif(NULL==p->lchild&&NULL!=p->rchild){/*/p只有右子树/*/if(p==q->lchild)q->lchild=p->rchild;if(p==q->rchild)q->rchild=p->rchild;free(p);p=NULL;}/*/情况3:结点p的双亲结点为q，且p既有左子树又有右子树。本代码使用直接前驱（也可以直接后继）这里找的是左子树中最大的元素/*/elseif(NULL!=p->lchild&&NULL!=p->rchild){BiTrees,sParent;sParent=p;s=sParent->lchild;while(NULL!=s->rchild){/*/找到p的直接前驱/*/sParent=s;s=s->rchild;/*/左子树最大的总是在左子树中最右下角/*/}temp=s->data;/*/此时s指向的是最大的右下叶子结点为一般情况1直接删除/*/DelBSTNode(t,temp);p->data=temp;/*/最后将原来要删除的p的数据改为temp/*/}}}/*/待递归版本的删除传引用的妙处中序遍历打印BST/*/voidPrintBST(BiTreet){if(t){PrintBST(t->lchild);printf("%d",t->data);PrintBST(t->rchild);}}voiduse(){intn;int*a;Elemtypekey;BiTreet;printf("请输入二叉查找树的结点数:\n");scanf("%d",&n);a=(int*)malloc(sizeof(int)*n);printf("请输入二叉找树的结点数据:\n");for(inti=0;i<n;i++)scanf("%d",&a[i]);CreateBST(&t,a,n);printf("当前二叉查找树的中序遍历结果为:\n");PrintBST(t);printf("\n##############################################\n");printf("请输入要查找的元素:\n");scanf("%d",&key);printf("BST递归查找结果:\n");SearchBST(t,key);//递归查找printf("##############################################\n");printf("请输入要删除的元素:\n");scanf("%d",&key);DelBSTNode(t,key);printf("当前二叉查找树的中序遍历结果为:\n");PrintBST(t);printf("\n##############################################\n");printf("请输入要查找的元素:\n");scanf("%d",&key);printf("BST迭代查找结果:\n");_SearchBST(t,key);//迭代查找}voidtest(){intn;Elemtypekey;BiTreet;inta[]={5,8,2,1,4,7,9,6,3};printf("请输入二叉查找树的结点数:\n");n=9;printf("请输入二叉找树的结点数据:\n");CreateBST(&t,a,n);printf("当前二叉查找树的中序遍历结果为:\n");PrintBST(t);printf("\n##############################################\n");printf("请输入要查找的元素:\n");key=8;printf("BST递归查找结果:\n");SearchBST(t,key);//递归查找printf("##############################################\n");printf("请输入要删除的元素:\n");key=5;DelBSTNode(t,key);printf("当前二叉查找树的中序遍历结果为:\n");PrintBST(t);printf("\n##############################################\n");printf("请输入要查找的元素:\n");key=5;printf("BST迭代查找结果:\n");_SearchBST(t,key);//迭代查找}intmain(void){printf("Hello,CworldofAnycodeX!\n");test();returnEXIT_SUCCESS;}