二叉排序树(C语言)

《二叉排序树(C语言)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、#include#includetypedefintKeyType;typedefstructBinSearchNode{KeyTypekey;/*结点的关键码字段*/structBinSearchNode*llink,*rlink;/*二叉树的左、右指针*/}DicElement;typedefstruct{intMAXNUM;/*字典中元素的个数上界*/intn;/*为字典中实际元素的个数*/int*element;/*存放字典中的元素*/}SeqDictionary;structBi

2、nSearchNode;typedefstructBinSearchNode*PBinSearchNode;typedefstructBinSearchNode*BinSearchTree;/*二叉排序树*/typedefBinSearchTree*PBinSearchTree;intsearch(PBinSearchTreeptree,KeyTypekey,PBinSearchNode*position){PBinSearchNodep,q;p=*ptree;q=p;while(p!=NULL){q=p;/*用q记录父结点的

3、位置*/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)in

4、Order(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");return0;}/*申请空间出错*/p->key=key

5、;p->llink=p->rlink=NULL;/*对新结点的赋值*/if(position==NULL)*ptree=p;/*原树为空树*/elseif(keykey)position->llink=p;/*插入position的左子树*/elseposition->rlink=p;/*插入position的右子树*/return1;}intcreatSearchTree(PBinSearchTreeptree,SeqDictionary*dic)//新建二叉排序树{inti;*ptree=NULL;/

6、*将二叉排序树置空*/printf("请输入字典中允许的最大元素个数");scanf("%d",&dic->MAXNUM);dic->element=(int*)malloc(sizeof(int));printf("请输入当前要插入的元素的个数");scanf("%d",&dic->n);printf("请输入%d个大小不一样的整数",dic->n);for(i=0;in;i++){scanf("%d",&dic->element[i]);if(!insert(ptree,dic->element[i

7、]))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;/*不

8、存在*/if(p->llink==NULL){/*无左子树*/if(parentp==NULL)/*删除根结点*/*ptree=p->rlink;elseif(parentp->llink==p)/*将右子树链到父结点的左链*/parentp->llink=p->rlink;