2-3树的插于及删除操作源代码

可以运行。设计了测试用例覆盖了所有的情况，测试后结果正确。

2-3树具体的讲解请看文档，文档是东南大学邓建明老师上课使用的。

?

?

测试插入{11,22,34,42,6,3,28,24,36 }

删除28：

删除36：

?

//f.h#include <stdio.h>#include <malloc.h>#define NUM 10#define INTERIOR 0#define LEAF 1#define FALSE 0#define TRUE 1typedef struct Node//节点{int type;int key;int low2;int low3;struct Node * son1;struct Node * son2;struct Node * son3;}TreeNode,*BiTree;typedef struct sNode{struct sNode *preNode;BiTree pTree;}StackNode, *BiStack;typedef struct stackn{BiStack head;BiStack tail;}Stacks,*Stack;Stack stack;void push(BiTree bt){BiStack bs=(BiStack)malloc(sizeof(StackNode));bs->preNode=stack->head;bs->pTree=bt;stack->head=bs;}BiTree pop(){if (stack->head == stack->tail){return NULL;}BiTree bt=stack->head->pTree;BiStack bs=stack->head;if (bs!=stack->tail){stack->head=bs->preNode;}free(bs);return bt;}void clean(){while(stack->head!=stack->tail){BiStack tmp=stack->head;stack->head=stack->head->preNode;free(tmp);}}BiTree createNode(int type,int key){BiTree t=(BiTree)malloc(sizeof(TreeNode));t->type=type;t->low2=t->low3=0;t->son1=t->son2=t->son3=NULL;t->key=key;return t;}/************************************************************************//* input:x:the leaf node to inserttp:the tree or the sun tree x will insert topback::null - the function is complete. if it is not null, it meansa bother node of tp, it is created in the function because tp has three sun node,so the function created it to stored new node;It is used for father node(out function) to coordinatethe tree;the node is right to tpoutput:lowBack:it is the least key number of the nodes of pback;*//************************************************************************/int addson(BiTree x,BiTree* tp_point,BiTree *pBack){BiTree tp=*tp_point;int low_back=0;if (tp->type == LEAF){if (tp->key > x->key){BiTree tmp=x;x=tp;(*tp_point)=tmp;}*pBack=x;return (*pBack)->key;}//tp node is a interior nodeint child;//it means which child node to insert;BiTree tp_next;if (x->key < tp->low2){child =1;tp_next=tp->son1;}else if (x->key <tp->low3 || (tp->low3 ==0&&tp->son3 == NULL)){child =2;tp_next=tp->son2;}else{child =3;tp_next=tp->son3;}BiTree pNewBack=NULL;//set the tp_next as the tree to insert//iterate the function until dealing with the leaf node int low_number=addson(x,&tp_next,&pNewBack);if (pNewBack != NULL){if (tp->son3 == NULL)//if tp only have two child node, the new node which is create in the iteration function can be stored by tp node{if (child ==1){tp->son3=tp->son2;tp->son2=pNewBack;tp->son1=tp_next;//tp_next is a pointer who point to the node/tree to inserttp->low3=tp->low2;tp->low2=low_number;}else//child == 2{tp->son3=pNewBack;tp->son2=tp_next;tp->low3=low_number;}}else{//tp have three child node so a new interior node(tp's right bother) should be create to store the new child node*pBack=createNode(INTERIOR,0);if (child ==1){(*pBack)->son1=tp->son2;(*pBack)->son2=tp->son3;tp->son2=pNewBack;tp->son1=tp_next;tp->son3=NULL;(*pBack)->low2=tp->low3;low_back=tp->low2;tp->low2=low_number;tp->low3=0;}else if (child == 2){(*pBack)->son1=pNewBack;(*pBack)->son2=tp->son3;tp->son2=tp_next;tp->son3=NULL;(*pBack)->low2=tp->low3;tp->low3=0;low_back=low_number;}else{//child ==3(*pBack)->son1=tp_next;(*pBack)->son2=pNewBack;tp->son3=NULL;(*pBack)->low2=low_number;low_back=tp->low3;tp->low3=0;}}}return low_back;}void insert(int key,BiTree *ts){BiTree tree=*ts;BiTree x=createNode(LEAF,key);if (tree == NULL)//如果2-3树为空树{*ts=x;return;}BiTree tp=tree;BiTree pBack=NULL;int low_number=addson(x,&tp,&pBack);if (pBack!=NULL){//create a new interior node used as the new tree nodeBiTree newHead=createNode(INTERIOR,0);newHead->low2=low_number;newHead->son1=tp;newHead->son2=pBack;*ts=newHead;}return;}/************************************************************************//*find the node to delete by key.On the same time,stack will store the router of nodes which have been searched.intup:key:the key of the node which is supposed to deletetree:the tree to search for the node to deletep:point to a node whose low2 or low3 equal to the key to deleteoutput:if a node is searched successfully,return true;otherwise return false;*//************************************************************************/bool find_node(int key,BiTree tree,BiTree *p){if (tree==NULL){return false;}push(tree);if (tree->type == LEAF){if (tree->key == key){return true;}else{return false;}}if (key==tree->low2 || key ==tree->low3){*p=tree;}if (key<tree->low2){find_node(key,tree->son1,p);}else if (key == tree->low2 || key<tree->low3||tree->low3==0){find_node(key,tree->son2,p);}else{find_node(key,tree->son3,p);}}void changePpoint(BiTree a,BiTree p,int key){if (p->low2==a->key){p->low2=key;}else{p->low3=key;}}int getLeastKey(BiTree t){if (t->type==INTERIOR){return getLeastKey(t->son1);}else{return t->key;}}void deleteNode(BiTree *a_pointer,BiTree *f_pointer,BiTree *ff_pointer,BiTree p,BiTree *t_pointer){BiTree a=*a_pointer;printf("delete node begin! ");printf("node:%d %d %d %d\n",a->key,a->low2,a->low3,a->type);BiTree f=*f_pointer;BiTree ff=*ff_pointer;BiTree tLeft=NULL;BiTree tRight=NULL;int fchild=0;int achild=0;if (a==f->son1){achild=1;}else if (a==f->son2){achild=2;}else{achild=3;}if (f->low3!=0)//father node have three child node;{if (a==f->son3){f->son3=NULL;f->low3=0;free(a);}else if (a==f->son2){f->low2=f->low3;f->low3=0;f->son2=f->son3;f->son3=NULL;free(a);}else if (a==f->son1){if (a->type==LEAF&&p!=NULL){changePpoint(a,p,f->low2);}f->low2=f->low3;f->low3=0;f->son1=f->son2;f->son2=f->son3;f->son3=NULL;free(a);}else{printf("err:a不是f的子节点。\n");}}else{//father node have two child node,a =1,2BiTree b=NULL;if (achild ==1){b=f->son2;}else{b=f->son1;}if (ff==NULL)//f is the root node{*t_pointer=b;free(a);free(f);return;}if (f==ff->son1){tRight=ff->son2;fchild=1;}else if (f==ff->son2){tLeft=ff->son1;tRight=ff->son3;fchild=2;//ff->low2=getLeastKey(f);}else if (f == ff->son3){tLeft=ff->son2;fchild=3;//ff->low3=getLeastKey(f);}else{printf("err1:f not a child node of ff!\n");}//获得了父节点左右的分支，开始根据四种情况处理if (tLeft!=NULL&&tLeft->low3!=0){//父节点由一个兄弟节点在左边，并且有三个子节点. done!f->son2=b;f->son1=tLeft->son3;tLeft->son3=NULL;if (a->type=LEAF&&a->key<b->key&&p!=NULL){changePpoint(a,p,tLeft->low3);}int tmp=0;if (fchild==2){tmp=ff->low2;ff->low2=tLeft->low3;}else{tmp=ff->low3;ff->low3=tLeft->low3;}if (achild=2)//如果a是父节点的第二个孩子，则b为第一个孩子，将b改为f的第二个字孩子以后，可以从ff中获得b的最小节点值。{f->low2=tmp;}tLeft->low3=0;free(a);}else if (tRight!=NULL&&tRight->low3!=0){f->son1=b;f->son2=tRight->son1;tRight->son1=tRight->son2;tRight->son2=tRight->son3;tRight->son3=NULL;if (a->type=LEAF&&a->key<b->key&&p!=NULL){changePpoint(a,p,b->key);}int tmp=0;if (fchild==1){tmp=ff->low2;ff->low2=tRight->low2;}else{tmp=ff->low3;ff->low3=tRight->low2;}f->low2=tmp;if (tmp!=getLeastKey(f->son2)){printf("err:not equal to getLeastKey:2~");}//f->low2=getLeastKey(f->son2);tRight->low2=tRight->low3;tRight->low3=0;free(a);}else if (tLeft!=NULL)//左侧兄弟节点有两个儿子{tLeft->son3=b;if (achild==2)//修改tleft->low3{int tmp=0;if (fchild==2){tmp=ff->low2;}else{tmp=ff->low3;}tLeft->low3=tmp;}else{tLeft->low3=f->low2;}*a_pointer=*f_pointer;*f_pointer=*ff_pointer;BiTree bitmp=pop();*ff_pointer=bitmp;free(a);deleteNode(a_pointer,f_pointer,ff_pointer,p,t_pointer);}else{//右侧兄弟节点有两个儿子tRight->son3=tRight->son2;tRight->son2=tRight->son1;tRight->son1=b;if (a->type=LEAF&&a->key<b->key&&p!=NULL){changePpoint(a,p,b->key);}tRight->low3=tRight->low2;if (fchild==1){tRight->low2=ff->low2;}else{tRight->low2=ff->low3;}*a_pointer=*f_pointer;*f_pointer=*ff_pointer;BiTree bitmp=pop();*ff_pointer=bitmp;free(a);deleteNode(a_pointer,f_pointer,ff_pointer,p,t_pointer);}}//删除节点的父节点的对于该节点的low信息不需要使用}int deletes(int key,BiTree *t){BiTree tree=*t;BiTree p=NULL;//point to a node whose low2 or low3 equal to the key to deleteclean();if (tree==NULL||!find_node(key,tree,&p)){return FALSE;}if (tree->type=LEAF&&tree->key == key){free(tree);*t=NULL;}BiTree a=pop();//the LEFT nodeBiTree f=pop();//father nodeBiTree ff=pop();//father node 's father nodedeleteNode(&a,&f,&ff,p,t);return TRUE;}//main.cpp#include "f.h"void main(){stack=(Stack)malloc(sizeof(Stacks));stack->tail=(BiStack)malloc(sizeof(StackNode));stack->tail->preNode=NULL;stack->tail->pTree=NULL;stack->head=stack->tail;//for the delete functionBiTree t=NULL;//指向2-3树根节点int inputs=1;int input_set[10]={11,22,34,42,6,3,28,24,36,9};for (int i=0;i<10;i++){insert(input_set[i],&t);}/*while (inputs!=0){printf("\n请输入一个正整数插入到2-3树中：");scanf("%d",&inputs);if (inputs!=0){insert(inputs,&t);}}*/int key=-1;int key_set[9]={28,36,24,34,6,3,22,42,11};deletes(11,&t);/*for (int i=0;i<6;i++){if (i==14){int sss=0;}if (!deletes(key_set[i],&t)){printf("there is no node in the tree you want to delete");}}/*while(key!=0){printf("\n请输入要删除节点的key值：");scanf("%d",&key);if (!deletes(key,&t)){printf("there is no node in the tree you want to delete");}}*/int s;}