C语言二叉排序（搜索）树实例
本文实例为大家分享了C语言二叉排序（搜索）树实例代码，供大家参考，具体内容如下
/**1.实现了递归 非递归插入（创建）二叉排序（搜索）树；
分别对应Insert_BinSNode(TBinSNode* T,int k),NonRecursion_Insert_BinSNode(TBinSNode* T,int k);
2.实现了递归 非递归查找 二叉排序（搜索）树 ；
分别对应Find_BinSNode(TBinSNode *T,int s),NonRecursion_Find_BinSNode(TBinSNode *T,int s);
3. 实现了非递归删除 二叉排序（搜索）树；
分别对应Delete_BinSNode()；
4. 实现了递归先序、中序、后序遍历二叉排序（搜索）树；
分别对应Pre_Print_BinSNode(TBinSNode T),In_Print_BinSNode(TBinSNode T),Post_Print_BinSNode(TBinSNode T);
*/
#include<stdio.h>
#include<stdlib.h>
typedef struct BinSTreeNode{
int num;
struct BinSTreeNode *lchild,*rchild;
}BinSNode,*TBinSNode;
int Empty_Tree(TBinSNode T){
if(!T){
return 1;
}else{
return 0;
}
}
/*---------------------非递归方法 二叉排序树的删除-----------------*/
void Delete_BinSNode(TBinSNode *T,int del){
TBinSNode cur,pre,lt,rblast;
cur=*T;
pre=NULL;
//如果二叉排序树为空
if(Empty_Tree(cur)){
printf("Sorry,Tree is none");
return;
}
//如果二叉排序树不为空，先找到即将删除的元素del.这里再次实现一遍查找，当然也可以修改一下Find类的函数
while(cur && cur->num!=del){
if(del>cur->num){
pre=cur;
cur=cur->rchild;
}else{
pre=cur;
cur=cur->lchild;
}
}
if(!cur){
printf("Sorry,you want to delete the node ,which is non-existent");
return;
}
if(cur->num==del){
printf("find the delete node,wait a minute.......\n");
}
//如果找到待删除的结点，立刻判断该结点有无左子树
//情况一：待删除结点无左子树
if(!cur->lchild){
if(pre==NULL){
cur=*T;
*T=(*T)->rchild;
free(cur);
return;
}
if(pre->lchild && pre->lchild->num==del){
pre->lchild=cur->rchild;
free(cur);
return;
}
if(pre->rchild && pre->rchild->num==del){
pre->rchild=cur->rchild;
free(cur);
return;
}
}
//情况二：待删除的结点有左子树。
if(cur->lchild){
lt=cur->lchild;
//情况2.1：该左子树无右子树
if(!lt->rchild){
if(pre->lchild && pre->lchild->num==del){
pre->lchild=lt;
free(cur);
return;
}
if(pre->rchild && pre->rchild->num==del){
pre->rchild=lt;
free(cur);
return;
}
}
//情况2.2:该左子树有右子树
if(lt->rchild){
while(lt->rchild){
rblast=lt; //该左子树中最大的结点的前一个结点.
lt=lt->rchild;
}
cur->num=lt->num;
rblast->rchild=lt->lchild;
free(lt);
return;
}
}
}
/*--------------------递归方法 查找 二叉排序树-------------------*/
void Find_BinSNode(TBinSNode T,int s){
if(s==T->num){
printf("%d\n",T->num);
return;
}
if(s>T->num){
Find_BinSNode(T->rchild,s);
}else{
Find_BinSNode(T->lchild,s);
}
}
/*-------------------非递归方法 查找二叉排序树--------------------*/
void NonRecursion_Find_BinSNode(TBinSNode T,int s){
if(Empty_Tree(T)){
printf("Tree is none");
return;
}
while(T && s!=T->num ){
if(s>T->num){
T=T->rchild;
}else{
T=T->lchild;
}
}
if(!T){
printf("Sorry,Not Find!");
exit(0);
}
if(s==T->num){
printf("%d\n",T->num);
}
}
/*-----------------递归方法 创建/插入 二叉排序树------------------*/
void Insert_BinSNode(TBinSNode *T,int k){
// int n;
TBinSNode node;
// scanf("%d",&n);
if(Empty_Tree(*T)){
*T=(TBinSNode)malloc(sizeof(BinSNode));
(*T)->num=k;
(*T)->lchild=(*T)->rchild=NULL;
return;
}else{
if(k>(*T)->num){
Insert_BinSNode(&(*T)->rchild,k);
}else{
Insert_BinSNode(&(*T)->lchild,k);
}
}
}
/*----------------------先序遍历二叉排序树----------------------------------*/
void Pre_Print_BinSNode(TBinSNode T){
if(T){
printf("%d ",T->num);
Pre_Print_BinSNode(T->lchild);
Pre_Print_BinSNode(T->rchild);
}
}
/*-----------------------中序遍历二叉排序树-----------------------------------*/
void In_Print_BinSNode(TBinSNode T){
if(T){
In_Print_BinSNode(T->lchild);
printf("%d ",T->num);
In_Print_BinSNode(T->rchild);
}
}
/*-----------------------后序遍历二叉排序树-----------------------------------*/
void Post_Print_BinSNode(TBinSNode T){
if(T){
Post_Print_BinSNode(T->lchild);
Post_Print_BinSNode(T->rchild);
printf("%d ",T->num);
}
}
/*---------------------非递归 创建/插入 二叉排序树---------------------------*/
void NonRecursion_Insert_BinSNode(TBinSNode *T,int k){
//如果为空的二叉排序树
TBinSNode cur,p,t;
t=*T;
if(!*T){
*T=(TBinSNode)malloc(sizeof(BinSNode));
(*T)->num=k;
(*T)->lchild=(*T)->rchild=NULL;
return;
}else{ //二叉排序树不为空。
while(t){
if(k>t->num){
cur=t;
t=t->rchild;
}else{
cur=t;
t=t->lchild;
}
}
p=(TBinSNode)malloc(sizeof(BinSNode));
p->num=k;
p->lchild=p->rchild=NULL;
if(k>cur->num){
cur->rchild=p;
}
if(k<cur->num){
cur->lchild=p;
}
}
}
int main(void){
TBinSNode T=NULL;
int k,s,del;//创建的 查找的 删除的
while(scanf("%d",&k) && k){
// Insert_BinSNode(&T,k);
NonRecursion_Insert_BinSNode(&T,k);
}
// scanf("%d",&s);
// Find_BinSNode(T,s);
// NonRecursion_Find_BinSNode(T,s);
Pre_Print_BinSNode(T);
scanf("%d",&del);
Delete_BinSNode(&T,del);
Pre_Print_BinSNode(T);
return 0;
}
以上是 C语言二叉排序（搜索）树实例 的全部内容， 来源链接： utcz.com/z/349789.html
