可以运行。设计了测试用例覆盖了所有的情况,测试后结果正确。
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 1
typedef 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 insert
tp : the tree or the sun tree x will insert to
pback: : null - the function is complete. if it is not null, it means
a 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 coordinate
the tree;
the node is right to tp
output:
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 node
int 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 insert
tp->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 node
BiTree 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 delete
tree : the tree to search for the node to delete
p : point to a node whose low2 or low3 equal to the key to delete
output:
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,2
BiTree 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 delete
clean();
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 node
BiTree f=pop();//father node
BiTree ff=pop();//father node 's father node
deleteNode(&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 function
BiTree 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;
}
- 大小: 18.9 KB
- 大小: 22.7 KB
- 大小: 18.5 KB
分享到:
相关推荐
源代码包括二叉树的创建,先序遍历,中序遍历,后序遍历 crc 校验, 经典算法的加密和解密算法,huffman编码 队列的创建、插入、删除,堆栈的创建、pop和push操作, 图:----用邻接矩阵构造无向图-------- -------...
主要内容包括SQL的基础理论、查询优化、查询算法及复杂度,以及在使用子查询、表表达式、排名函数、数据聚合和透视转换、TOP和APPLY、数据修改、分区表、特殊数据结构等实际应用时会遇到的各种高级查询问题和解决...
主要内容包括SQL的基础理论、查询优化、查询算法及复杂度,以及在使用子查询、表表达式、排名函数、数据聚合和透视转换、TOP和APPLY、数据修改、分区表、特殊数据结构等实际应用时会遇到的各种高级查询问题和解决...
2-3. cleanup:一个增强的和广义的删除logfile 的脚本 3-1. 代码块和I/O 重定向 3-2. 将一个代码块的结果保存到文件 3-3. 在后台运行一个循环 3-4. 备份最后一天所有修改的文件. 4-1. 变量赋值和替换 4-2. 一般的变量...
2.7.15 树结构操作实例 2.8 图结构 2.8.1 什么是图结构 2.8.2 图的基本概念 2.8.3 准备数据 2.8.4 创建图 2.8.5 清空图 2.8.6 显示图 2.8.7 遍历图 2.8.8 图结构操作实例 2.9 小结 第3章 基本算法思想 3.1 常用算法...
2.源代码使用方法参见《附录A 源代码的使用方法》文件。 __________________________________________________________________ 注意: 1.建议读者下载源文件后,将该源文件进行备份,读者使用副本源文件...
该资料是《Oracle SQL高级编程》的源代码 对应的书籍资料见: Oracle SQL高级编程(资深Oracle专家力作,OakTable团队推荐) 基本信息 原书名: Pro Oracle SQL 原出版社: Apress 作者: (美)Karen Morton Kerry ...
(1)输入学生信息并保存到文件 (2)读取文件并输出学生信息 (3)按学号及学期查询 (4)按姓名及学期查询 (5)按学号及学期修改信息 (6)插入信息 (7)按学号及学期删除信息 (8)按数据结构降序(冒泡)排序 (9)按...
《远程控制编程技术》源代码 内含(重启、图片操作、ip操作、键盘与鼠标、客户端以及服务端、文件传输等实例源码) 多个VC++加密解密算法库(CRYPT++) 详细讲解了Crypt++的加密解密的使用以及其它的加密解密方法...
“库文件名”以.lib或.obj为后缀的将被视为静态库,可使用绝对路径或相对路径(相对当前源代码所在目录),如依赖多个静态库请分别列出并以逗号分隔;“在库中的对应命令名”请务必准确填写静态库中公开导出的符号...
7、 编写一个程序,将10进制数转换为其它(2-9)进制数。可以将要转换的数重复除以基数,然后讲除的余数按反方向排列来实现; 8、 已知A[n]为正数数组,试写出实现下列运算的递归算法; a. 求数组A中的...
源代码使用方法是(以实例1为例): 将该实例的源码,比如实例1的1.c文件(可以在001目录下找到), 拷贝到tc编译器目录下,运行tc.exe,打开编译器, 按【F3】键或者“File->Open”菜单命令,打开1.c文件, 按...
红黑树是重要的数据结构,而其操作又很复杂,如果能够可视化地展示插入与删除过程,则学习起来会容易得多。 为了学习它们,我翻译以下文章(论文)并实现了相应算法,并放到网络上,与说中文的程序爱好者共同进步。...
1.2 源代码表示 1 1.2.1 将拥塞窗口设置为1 1 1.2.2 印刷约定 2 1.3 历史 2 1.4 应用编程接口 3 1.5 程序示例 4 1.6 系统调用和库函数 6 1.7 网络实现概述 6 1.8 描述符 7 1.9 mbuf与输出处理 11 1.9.1 包含插口地址...
《TCP-IP详解》共3卷,其他卷请到我空间下载,第2卷共分两个part,请下载完两个part后在解压。本书完整而详细地介绍了TCP/IP协议是如何实现的。书中给出了约500个图例,15 000行实际操作的C代码,采用举例教学的方法...
内含源代码、可执行程序以及相应的说明文档 实验的功能包括: [实现提示] (1) 初始,平衡二叉树为空树,操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后,应...
Visual.C++编程技巧精选500例源代码 内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与...
Visual.C++编程技巧精选500例源代码 内含各种例子(vc下各种控件的使用方法、标题栏与菜单栏、工具栏与状态栏、图标与光标、程序窗口、程序控制、进程与线程、字符串、文件读写操作、文件与文件夹属性操作、文件与...
(3)赫夫曼树编码和译码算法。 交通咨询系统开发 项目要求: (1)系统功能:要求设计一个简易的交通咨询系统,可让用户咨询任意两 个城市之间的最短距离、最低花费或最少时间等问题。 (2)对于不同的咨询要求,...