二叉排序树的插入算法
发布网友
发布时间：2022-04-30 03:24
共1个回答
热心网友
时间：2023-10-09 14:23
首先执行查找算法，找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意：新插入的结点总是叶子结点。 //在二叉排序树中插入查找关键字keyvoidInsertBST(t，key){ if(t==NULL) { t=newBiTree; t->lchild=t->rchild=NULL; t->data=key; return; } if(key<t->data) InsertBST(t->lchild,key); else InsertBST(t->rchild,key);}//n个数据在数组d中，tree为二叉排序树根voidCreateBiTree(tree,d[],n){ tree=NULL; for(i=0;i<n;i++) InsertBST(tree,d[i]);}最小值二叉树c例程： #include<stdio.h>#include<malloc.h>struct priorityqueue{ intcapacity; intsize; struct priorityqueue* elements;}*tryit;structpriorityqueue*initialize(int maxelements){ struct priorityqueue* h; h=malloc(sizeof(structpriorityqueue)); h->elements=malloc(sizeof(int)*(maxelements+1)); h->capacity=maxelements; h->size=0; h->elements[0]=-23767; return h;}voidinsert(int x,struct priorityqueue* h){ inti; for(i=++h->size;h->elements[i/2]>x;i/=2) h->elements[i]=h->elements[i/2]; h->elements[i]=x;}intdeletemin(struct priorityqueue* h){ int i,child; int minelement,lastelement; minelement=h->elements[1]; lastelement=h->elements[h->size--]; for(i=1;i*2<=h->size;i=child) { child=i*2; if(child!=h->size&&h->elements[child+1]<h->elements[child]) child++; if(lastelement>h->elements[child]) h->elements[i]=h->elements[child]; else break;} h->elements[i]=lastelement; return minelement;}main(){ tryit=initialize(10); insert(4,tryit); insert(5,tryit); insert(10,tryit); insert(3,tryit); printf(%d\n,deletemin(tryit)); printf(%d\ndeletemin(tryit)); printf(%d\n,deletemin(tryit)); printf(%d\n,deletemin(tryit)); getchar();}
