二叉查找树是数据结构里面很重要的树结构，二叉查找树的树结构很容易看懂，但是，一旦我们利用算法来实现的时候，就没有那么容易了。因此，我们在这里主要利用示例讲算法原理！定义一个数组，然后在定义要搜寻，删除的结点的元素值。首先呢，我们定义结构体来定义二叉树：
typedefstructNode{DataTypedata;structNode*lChild,*rChild;}BiTreeNode,*BiTree;typedefstruct{keyTypekey;}DataType;
我们利用二叉查找结构体的变量的二级指针来传递地址，在二叉查找树中插入元素：
BiTreeT=NULL,p; DataTypetable[]={37,32,35,62,82,95,73,12,5}; DataTypex={73},s={32};//x是要搜寻的结点，s是要删除的结点 intn=sizeof(table)/sizeof(table[0]); for(inti=0;in;i++) { BSTInsert(T,table[i]); }
看看插入函数的实现：
intBSTInsert(BiTree*T,DataTypex){ BiTreep,cur,parent=NULL; cur=*T; while(cur!=NULL) { if(cur-data.key==x.key) return0; parent=cur;//找到前驱结点 if(x.keycur-data.key)//如果关键字小于p所指向的结点的值，则在左子树中查找 cur=cur-lChild; else cur=cur-rChild; } p=(BiTree)malloc(sizeof(BiTree)*); if(!p) exit(-1); p-data=x; p-lChild=NULL; p-rChild=NULL; if(!parent)//如果二叉树为空，则第一结点成为根结点 *T=p; elseif(x.keyparent-data.key) { parent-lChild=p; } else parent-rChild=p;}
为什么利用二级指针呢？就是利用二级指针来判断二叉查找树，以便插入。什么时候执行while呢？就是我们执行完一次for循环给二叉查找树安插了第一个结点之后，我们就能进入while了。parent结点指针指向某一元素的双亲结点，我们就是利用while来找到双亲结点，该双亲结点就是我们要插入的结点的双亲结点。在这里，尤其注意：
p=(BiTree)malloc(sizeof(BiTree)*);
在《windows在**.exe中触发了一个断点，其原因可能是堆被损坏，这说明...dll中有bug》一文中，我阐述了这句代码的重要性，如果没有分配足够的内存空间，就会出现那篇文章里的错误！下面，我们看看删除函数：
voidDeleteNode(BiTree*s)//删除结点{ BiTreeq,x,y; if(!(*s)-rChild)//若该结点没有右子树 { q=*s; *s=(*s)-lChild; free(q); } elseif(!(*s)-lChild)//若该结点没有左子树 { q=*s; (*s)=(*s)-rChild; free(q); } else//若该结点既有左结点又有右子树 { x=*s; y=(*s)-lChild; while(y-rChild) { x=y; y=y-rChild; } (*s)-data=y-data; if(x!=*s)//也就是程序进入了while，要删除的结点下的左子树没有右子树 x-rChild=y-lChild; else x-lChild=y-lChild; free(y); }}intBSTDelete(BiTree*T,DataTypex){ if(!*T) return0; else { if(x.key==(*T)-data.key) DeleteNode(T); elseif(x.key(*T)-data.key) BSTDelete((*T)-lChild,x); else BSTDelete((*T)-rChild,x); return1; }}
在这里，我们主要看看DeleteNode函数，该函数实现的就是删除结点的功能。我们需要为我们所删除的结点考虑三种情况：只有左子树，右子树，既有左子树，右子树。当只有左子树的时候，就直接将该结点的左子树的元素链接到要删除的元素的位置。只有右子树的时候，也是一样的。那么，要是又有右子树，又有左子树呢？我们先这样分析：在用中序遍历输出二叉排序树的所有的元素的时候，该序列是严格的递增的，而我们的序列是这样的：假设我们删除32，那么删除后的序列是：5123537627也就是说，我们删除的32的直接前驱元素！那么，怎么找到前驱元素呢？如果我们删除了这个元素之后，根据二叉查找树的结构特点，我们需要找到该结点的左子树中的最大值，那么怎么做呢？很简单：
x=*s;//定义一个结点x，给它赋值为要查找的结点y=(*s)-lchild；//在要删除的结点中左子树中查找，因此给y赋值第一个左子树while(y-rChild){ x=y; y=y-rChild;//在y的右子树中查找，直到没有结点了}
下面看看实现：完整的程序：
#includestdio.h#includewindows.htypedefintkeyType;typedefstruct{ keyTypekey;}DataType;typedefstructNode{ DataTypedata; structNode*lChild,*rChild;}BiTreeNode,*BiTree;intBSTInsert(BiTree*T,DataTypex){ BiTreep,cur,parent=NULL; cur=*T; while(cur!=NULL) { if(cur-data.key==x.key) return0; parent=cur;//找到前驱结点 if(x.keycur-data.key) cur=cur-lChild; else cur=cur-rChild; } p=(BiTree)malloc(sizeof(BiTree)*); if(!p) exit(-1); p-data=x; p-lChild=NULL; p-rChild=NULL; if(!parent) *T=p; elseif(x.keyparent-data.key) { parent-lChild=p; } else parent-rChild=p;}voidInOrderTraverse(BiTreeT)//中序遍历{ if(T) { InOrderTraverse(T-lChild); printf(%d,T-data.key); InOrderTraverse(T-rChild); }}BiTreeBSTSearch(BiTreeT,DataTypex)//查找结点{ BiTreep; if(T!=NULL) { p=T; while(p!=NULL) { if(p-data.key==x.key) { returnp; } elseif(x.keyp-data.key) p=p-lChild; else p=p-rChild; } } returnNULL;}voidDeleteNode(BiTree*s)//删除结点{ BiTreeq,x,y; if(!(*s)-rChild)//若该结点没有右子树 { q=*s; *s=(*s)-lChild; free(q); } elseif(!(*s)-lChild)//若该结点没有左子树 { q=*s; (*s)=(*s)-rChild; free(q); } else//若该结点既有左结点又有右子树 { x=*s; y=(*s)-lChild; while(y-rChild) { x=y; y=y-rChild; } (*s)-data=y-data; if(x!=*s) x-rChild=y-lChild; else x-lChild=y-lChild; free(y); }}intBSTDelete(BiTree*T,DataTypex){ if(!*T) return0; else { if(x.key==(*T)-data.key) DeleteNode(T); elseif(x.key(*T)-data.key) BSTDelete((*T)-lChild,x); else BSTDelete((*T)-rChild,x); return1; }}intmain(){ BiTreeT=NULL,p; DataTypetable[]={37,32,35,62,82,95,73,12,5}; DataTypex={73},s={32};//x是要搜寻的结点，s是要删除的结点 intn=sizeof(table)/sizeof(table[0]); for(inti=0;in;i++) { BSTInsert(T,table[i]); } printf(中序遍历的结果:\n); InOrderTraverse(T); p=BSTSearch(T,x); if(p!=NULL) printf(\n二叉排序树查找，关键字%d存在\n,x.key); else printf(查找失败!\n); BSTDelete(T,s); printf(输出删除结点的元素值为32后的元素:\n); InOrderTraverse(T); system(pause); return0;}
文章来源：C++技术网原创文章版权所有，未经授权，禁止转载。