TheponywasrevisedinJanuary2021二叉排序树C语言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;/*检索失败，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
key)position->llink=p;/*插入position的左子树*/elseposition->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;in;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;elsep=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;elsep=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*/elserr->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，重新建立二叉排序树！\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;}
浙公网安备 33021202002483