二叉排序树(C语言)

#include<stdio。h>#include<malloc。h>typedefintKeyType;typedefstructBinSearchNode{ KeyTypekey;/* 结点的关键码字段*/ structBinSearchNode*llink,*rlink;/* 二叉树的左、右指针*/}DicElement;typedefstruct{ intMAXNUM;/*字典中元素的个数上界*/ intn;/*为字典中实际元素的个数*/ int*element;/*存放字典中的元素*/} SeqDictionary;structBinSearchNode;typedefstructBinSearchNode*PBinSearchNode;typedefstructBinSearchNode*BinSearchTree;/*二叉排序树*/typedefBinSearchTree*PBinSearchTree;intsearch(PBinSearchTreeptree,KeyTypekey,PBinSearchNode*position){ PBinSearchNodep,q; p=*ptree; q=p; while(p!=NULL) { q=p;/* 用 q 记录父节点的位置*/ if(p>key==key) { *position=p; return1; }/* 检索成功*/ elseif(p>key>key)p=p>llink;/* 进入左子树继续检索*/ elsep=p>rlink;/* 进入右子树继续检索*/ } *position=q; return0;/* 检索失败二叉排序树 c，position 指向失败时的父结点*/}voidinOrder(BinSearchNode*p){ if(p) { if(p>llink) inOrder(p>llink); printf("%d",p>key); if(p>rlink) inOrder(p>rlink); }}intinsert(PBinSearchTreeptree,KeyTypekey){ PBinSearchNodep,position; if(search(ptree,key,&position)==1) return1; /* 已存在关键码为 key 的结点 */ p=(PBinSearchNode)malloc(sizeof(structBinSearchNode));/* 申请新结点 */ if(p==NULL) { printf("Error\n"); return0; }/* 申请空间出错 */ p>key=key; p>llink=p>rlink=NULL;/* 对新结点的赋值*/ if(position==NULL) *ptree=p;/* 原树为空树 */ elseif(key<position>key) position>llink=p; /* 插入 position 的左子树 */ else position>rlink=p;/* 插入 position 的右子树*/ return1;}intcreatSearchTree(PBinSearchTreeptree,SeqDictionary*dic)//新建二叉排序树{ inti;*ptree=NULL;/* 将二叉排序树置空 */ printf("请输入字典中允许的最大元素个数\n"); scanf("%d",&dic>MAXNUM); dic>element=(int*)malloc(sizeof(int)); printf("请输入当前应插入的元素的个数\n"); scanf("%d",&dic>n); printf("请输入%d 个大小不一样的整数\n",dic>n); for(i=0;i<dic>n;i++) { scanf("%d",&dic>element[i]); if(!insert(ptree,dic>element[i])) return0;/* 将新节点插入树中 */ } return1;}intdeleteNode_a(PBinSearchTreeptree,KeyTypekey){ PBinSearchNodeparentp,p,r; p=*ptree; parentp=NULL; while(p!=NULL) { if(p>key==key) break;/* 找到了关键码为 key 的节点*/ parentp=p;/*没有找到选子树*/ if(p>key>key) p=p>llink; else p=p>rlink; } if(p==NULL) return0;/*不存在*/ if(p>llink==NULL) {/* 无左子树 */ if(parentp==NULL)/* 删除根结点*/ *ptree=p>rlink; elseif(parentp>llink==p)/*将右子树链到父结点的左链*/ parentp>llink=p>rlink; else /* 将右子树链到父结点的右链上*/ parentp>rlink=p>rlink; } else/* 有左子树 */ { r=p>llink; while(r>rlink!=NULL) r=r>rlink;/* 在*p 的左子树中找更右下结点*r*/ r>rlink=p>rlink;/* 用*r 的右指针指向*p 的右子女*/ if(parentp==NULL) *ptree=p>llink; elseif(parentp>llink==p)/* 把*p 的左子结点链到父结点的左链*/ parentp>llink=p>llink; else/* 把左子结点链到父结点的右链*/ parentp>rlink=p>llink; } free(p); return1;}intdeleteNode_b(PBinSearchTreeptree,KeyTypekey){ PBinSearchNodeparentp,p,r; p=*ptree; parentp=NULL; while(p!=NULL) { if(p>key==key) break;/* 找到了关键码为 key 的节点*/ parentp=p; if(p>key>key) p=p>llink; else p=p>rlink; } if(p==NULL) return0; if(p>llink==NULL)/* 无左子树 */ { if(parentp==NULL)/* 删除根结点*/ *ptree=p>rlink; elseif(parentp>llink==p)/*将右子树链到父结点的左链*/ parentp>llink=p>rlink; else /* 将右子树链到父结点的右链上*/ parentp>rlink=p>rlink; }/* 用第二种方式删除*/ else/* 结点*p 有左子树*/ { PBinSearchNoderr=p; for(r=p>llink;r>rlink!=NULL;r=r>rlink)/* 找到 p 的左子树的最右结点*/ rr=r; p>key=r>key; /* 复制结点信息*/ if(rr==p) p>llink=r>llink; /**r 的父结点就是 *p*/ else rr>rlink=r>llink;/* 用*r 的左子结点代替*r*/ p=r;/* 为统一在以下释放存储*/ } free(p);/* 释放被删除节点的传输*/ return1;}voidinset_node(PBinSearchTree&ptree){ KeyTypekey; printf("请输入你应插入的元素（整数）\n"); scanf("%d",&key); insert(ptree,key);}voidshow(BinSearchNode*t,intlen=0)//数的形状{ if(t!=NULL) { show(t>rlink,len+1); for(inti=1;i<=len;i++) { printf(" "); } printf("%d\n",t>key); show(t>llink,len+1); }}voiddeletenode(PBinSearchTreeptree){ intdelet_kind=0,key; printf("请输入你要删除的元素!\n"); scanf("%d",&key); printf("你要以哪个方法删除？ \n 方式 1 请输入 1，方式 2 请输入 0\n"); scanf("%d",&delet_kind); if(delet_kind) { deleteNode_a(ptree,key); printf("以形式 1 删除后的二叉排序树为：\n"); show(*ptree); } else { deleteNode_b(ptree,key); printf("以形式 2 删除后的二叉排序树为：\n"); show(*ptree); }}voidinterface(void){ printf("\n&&&&&&&&&&&&&&输入序号执行相应操作&&&&&&&&&&&&&&&&&\n"); printf(" 输入 1二叉排序树 c，重新构建二叉排序树！ \n"); printf("\n"); printf(" 输入 2，展示我的二叉排序树！\n"); printf("\n"); printf(" 输入 3，中根周游我的二叉排序树！\n"); printf("\n"); printf(" 输入 4，插入新的元素！\n"); printf("\n"); printf(" 输入 5，删除二叉排序树中的元素！\n"); printf("\n"); printf(" 输入其它，退出操作！\n"); printf("\n");}voidoperation(PBinSearchTree&ptree,SeqDictionary*(&dic)){ intk=1,num; while(k) { interface(); scanf("%d",&num); switch(num) { case1: creatSearchTree(ptree,dic);//建立二叉排序树 break; case2: { show(*ptree);//展示我的二叉排序树 } break; case3: { printf("当前二叉排序树的中根周游序列为：\n"); inOrder(*ptree);//周游我的二叉排序树 } break; case4: { inset_node(ptree);//插入新的元素 } break; case5: { deletenode(ptree);//删除二叉排序树中的元素 } break; default: printf("您未指定任何操作！请再次输入操作序号！\n"); k=0; break; } }}intmain(){ PBinSearchTreeptree=(PBinSearchTree)malloc(sizeof(BinSearchNode*));//分配二叉排序树结点指针 SeqDictionary*dic=(SeqDictionary*)malloc(sizeof(SeqDictionary));//分配二叉排序树指针 creatSearchTree(ptree,dic);//建立二叉排序树 operation(ptree,dic); getchar(); getchar(); return0;}

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-144574-1.html