网站链接: ngui
当前位置: 首页 > 学习教程  > 互联网媒体

算法导论-AVL树的C++实现

2020/12/22 23:03:45 人评论 文章标签: 陈姓洋气女孩插入剪贴画

代码主要来自网上流传的一份南京大学陈氏三姐妹的大作业。 花了一些时间测试和修改&#xff0c;代码基本OK了&#xff0c;结构也比较清晰。 我两把刷子&#xff0c;裸写的话没一个礼拜真下不来。 #include <stdio.h> #include <malloc.h> #include <stdlib.h&…

代码主要来自网上流传的一份南京大学陈氏三姐妹的大作业。

花了一些时间测试和修改,代码基本OK了,结构也比较清晰。

我两把刷子,裸写的话没一个礼拜真下不来。

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)<(b))
#define LQ(a,b) ((a)>(b))
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
#define maxSize 20
#define maxWidth 20

typedef struct BSTNode
{
int data;
int bf; //结点的平衡因子
struct BSTNode *lchild,*rchild;//左、右孩子指针
}BSTNode,*BSTree;

void R_Rotate(BSTree &p); //对以*p为根的二叉排序树作右旋处理
void L_Rotate(BSTree &p); //对以*p为根的二叉排序树作左旋处理
void LeftBalance(BSTree &T); //对以指针T所指结点为根的二叉树作左平衡旋转处理
void RightBalance(BSTree &T);//对以指针T所指结点为根的二叉树作右平衡旋转处理
bool InsertAVL(BSTree &T,int e,bool &taller);//插入结点e
bool SearchBST(BSTree &T,int key);//查找元素key是否在树T中
void DispTree(BSTree T);//按中序遍历输出二叉树的元素
void CreatBST(BSTree &T); //创建平衡二叉树,(注意:以输入-1为二叉树建立的结束)
void LeftBalance_div(BSTree &p,int &shorter);//删除结点时左平衡旋转处理
void RightBalance_div(BSTree &p,int &shorter);//删除结点时右平衡旋转处理
void Delete(BSTree q,BSTree &r,int &shorter);//删除结点
int  DeleteAVL(BSTree &p,int x,int &shorter);//平衡二叉树的删除操作


int main()
{
	int input,search;
	bool taller=false;
	int shorter=0;
	BSTree T,T1,T2;
	T=(BSTree)malloc(sizeof(BSTNode));
	T=T1=T2=NULL;
	while(1)
	{
		printf("1.Create Tree\t2.Search\t3.Insert\t4.DeleteNode\t5.Exit\n");
		printf("Choose what you want:\t");
		scanf("%d",&input);
		getchar();
		switch(input)
		{
		case 1:
			CreatBST(T); break;
		case 2:
			printf("Input the value you want to search:");
			scanf("%d",&search); getchar();
			if(SearchBST(T,search)) printf("Success!\n",search);
			else printf("Faild!\n");
			break;
		case 3:
			printf("Input the value you want to insert:");
			scanf("%d",&search); getchar();
			InsertAVL(T,search,taller);
			DispTree(T); break;
		case 4:
			printf("Input the value you want to delete:");
			scanf("%d",&search); getchar();
			DeleteAVL(T,search,shorter);
			DispTree(T); break;
		case 5:
            return 1;
			break;
		default:printf("Error,input again!");break;
		}
		printf("To be continue..."); getchar();
	}
	return 1;
}


//对以*p为根的二叉排序树作右旋处理,LL型平衡旋转法
void R_Rotate(BSTree &p)
{
	BSTree lc;
	lc = p->lchild; //lc指向的*p左子树根结点
	p->lchild = lc->rchild; //lc的右子树挂接为*p的左子树
	lc->rchild = p;
	p = lc; //p指向新的结点
}


//对以*p为根的二叉排序树作左旋处理,RR型平衡旋转法
void L_Rotate(BSTree &p)
{
	BSTree rc;
	rc = p->rchild; //rc指向的*p右子树根结点
	p->rchild = rc->lchild; //rc的左子树挂接为*p的右子树
	rc->lchild = p;
	p = rc; //p指向新的结点
}


//对以指针T所指结点为根的二叉树作左平衡旋转处理,LR型平衡旋转法
void LeftBalance(BSTree &T)
{
	BSTree lc,rd;
	lc = T->lchild; //lc指向*T的左子树根结点
	switch(lc->bf) //检查*T的左子树的平衡度,并作相应平衡处理
	{
	case LH: //新结点插入在*T的左孩子的左子树上,要作单右旋处理
		T->bf = lc->bf = EH;
		R_Rotate(T); break;
	case RH: //新结点插入在*T的左孩子的右子树上,要作双旋处理
		rd = lc->rchild; //rd指向*T的左孩子的右子树根
		switch(rd->bf) //修改*T及其左孩子的平衡因子
		{
		case LH:T->bf = RH; lc->bf = EH; break;
		case EH:T->bf = lc->bf = EH; break;
		case RH:T->bf = EH; lc->bf = LH; break;
		}
		rd->bf = EH;
		L_Rotate(T->lchild); //对*T的左子树作左旋平衡处理
		R_Rotate(T); //对*T作右旋平衡处理
	}
}


//对以指针T所指结点为根的二叉树作右平衡旋转处理,RL型平衡旋转法
void RightBalance(BSTree &T)
{
	BSTree rc,ld;
	rc = T->rchild; //rc指向*T的右子树根结点
	switch(rc->bf) //检查*T的右子树的平衡度,并作相应平衡处理
	{
	case RH: //新结点插入在*T的右孩子的右子树上,要作单左旋处理
		T->bf = rc->bf =EH;
		L_Rotate(T); break;
	case LH: //新结点插入在*T的右孩子的左子树上,要作双旋处理
		ld = rc->lchild; //ld指向*T的右孩子的左子树根
		switch(ld->bf) //修改*T及其右孩子的平衡因子
		{
		case LH: T->bf = EH; rc->bf = RH; break;
		case EH: T->bf = rc->bf =EH; break;
		case RH: T->bf = LH; rc->bf = EH; break;
		}
		ld->bf = EH;
		R_Rotate(T->rchild);//对*T的右子树作左旋平衡处理
		L_Rotate(T); //对*T作左旋平衡处理
	}
}


//插入结点e,若T中不存在和e相同关键字的结点,则插入一个数据元素为e的新结点,并返回1,否则返回0
bool InsertAVL(BSTree &T,int e,bool &taller)
{
	if(!T)//插入新结点,树"长高",置taller为true
	{
		T = (BSTree)malloc(sizeof(BSTNode));
		T->data = e;
		T->lchild = T->rchild =NULL;
		T->bf = EH; taller = true;
	}
	else
	{
		if(EQ(e,T->data)) //树中已存在和有相同关键字的结点则不再插入
		{
			taller = false;
			printf("The node have already exist!\n");
			return 0;
		}
		if(LT(e,T->data)) //应继续在*T的左子树中进行搜索
		{
			if(!InsertAVL(T->lchild,e,taller))
				return 0;//未插入
			if(taller) //已插入到*T的左子树中且左子树"长高"
			{
				switch(T->bf) //检查*T的平衡度
				{
                case LH: //原本左子树比右子树高,需要作左平衡处理
                LeftBalance(T);
				taller = false; break;
                case EH: //原本左子树、右子等高,现因左子树增高而使树增高
                T->bf = LH;
				taller = true; break;
                case RH: //原本右子树比左子树高,现左、右子树等高
                T->bf = EH;
				taller = false; break;
				}
			}
		}
		else //应继续在*T的右子树中进行搜索
		{
			if(!InsertAVL(T->rchild,e,taller))
				return 0;//未插入
			if(taller) //已插入到*T的右子树中且右子树"长高"
			{
				switch(T->bf) //检查*T的平衡度
				{
				case LH: //原本左子树比右子树高,现左、右子树等高
					T->bf = EH; taller = false; break;
				case EH: //原本左子树、右子等高,现因右子树增高而使树增高
					T->bf = RH; taller = true; break;
				case RH: //原本右子树比左子树高,需要作右平衡处理
					RightBalance(T); taller = false; break;
				}
			}
		}
	}
	return 1;
}//InsertAVL


//查找元素key是否在树T中
bool SearchBST(BSTree &T,int key)
{
	if(!T) return false;
	else if(EQ(key,T->data)) return true;
	else if(LT(key,T->data)) return SearchBST(T->lchild,key);
	else return SearchBST(T->rchild,key);
}


//层次法打印树
void DispTree(BSTree BT)
{
    BSTree stack[maxSize],p;
    int level[maxSize][2],top,n,i,width=4;
    if(BT!=NULL)
    {
        printf("Display a tree by hollow means.\n");
        top=1;
        stack[top]=BT;//push root point to stack.
        level[top][0]=width;
        while(top>0)
        {
            p=stack[top];
            n=level[top][0];
            for(i=1;i<=n;i++)
                printf(" ");
            printf("%d",p->data);
            for(i=n+1;i<maxWidth;i+=2)
                printf("--");
            printf("\n");
            top--;
            if(p->rchild!=NULL)
            {
                top++;
                stack[top]=p->rchild;
                level[top][0]=n+width;
                level[top][1]=2;
            }
            if(p->lchild!=NULL)
            {
                top++;
                stack[top]=p->lchild;
                level[top][0]=n+width;
                level[top][1]=1;
            }
        }
    }
}

//创建平衡二叉树,(注意:以输入-1为二叉树建立的结束)
void CreatBST(BSTree &T)
{
	int e;
	bool taller=false;
	T = NULL;
	printf("\nPlease input a key-value(end up with -1):");
	scanf("%d",&e);getchar();
	while(e != -1)
	{
		InsertAVL(T,e,taller);
		printf("\nPlease input a key-value(end up with -1):");
		scanf("%d",&e);getchar();taller=false;
	}
	if(T) DispTree(T);
	else printf("Empty tree.\n");
}


//删除结点时左平衡旋转处理
void LeftBalance_div(BSTree &p,int &shorter)
{
	BSTree p1,p2;
	if(p->bf==1) //p结点的左子树高,删除结点后p的bf减1,树变矮
	{
		p->bf=0; shorter=1;
	}
	else if(p->bf==0)//p结点左、右子树等高,删除结点后p的bf减1,树高不变
	{
		p->bf=-1; shorter=0;
	}
	else //p结点的右子树高
	{
		p1=p->rchild;//p1指向p的右子树
		if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理,树高不变
		{
			L_Rotate(p);
			p1->bf=1;
			p->bf=-1;
			shorter=0;
		}
		else if(p1->bf==-1)//p1的右子树高,左旋处理后,树变矮
		{
			L_Rotate(p);
			p1->bf=p->bf=0; shorter=1;
		}
		else //p1的左子树高,进行双旋处理(先右旋后左旋),树变矮
		{
			p2=p1->lchild;
			p1->lchild=p2->rchild; p2->rchild=p1; p->rchild=p2->lchild; p2->lchild=p;
			if(p2->bf==0)
			{
				p->bf=0; p1->bf=0;
			}
			else if(p2->bf==-1)
			{
				p->bf=1;p1->bf=0;
			}
			else
			{
				p->bf=0;
				p1->bf=-1;
			}
			p2->bf=0;
			p=p2;
			shorter=1;
		}
	}
}


//删除结点时右平衡旋转处理
void RightBalance_div(BSTree &p,int &shorter)
{
	BSTree p1,p2;
	if(p->bf==-1)
	{
		p->bf=0; shorter=1;
	}
	else if(p->bf==0)
	{
		p->bf=1; shorter=0;
	}
	else
	{
		p1=p->lchild;
		if(p1->bf==0)
		{
			R_Rotate(p);
			p1->bf=-1; p->bf=1; shorter=0;
		}
		else if(p1->bf==1)
		{
			R_Rotate(p);
			p1->bf=p->bf=0; shorter=1;
		}
		else
		{
			p2=p1->rchild;
			p1->rchild=p2->lchild; p2->lchild=p1; p->lchild=p2->rchild; p2->rchild=p;
			if(p2->bf==0)
			{
				p->bf=0;
				p1->bf=0;
			}
			else if(p2->bf==1)
			{
				p->bf=-1;
				p1->bf=0;
			}
			else
			{
				p->bf=0; p1->bf=1;
			}
			p2->bf=0; p=p2; shorter=1;
		}
	}
}


//删除结点
void Delete(BSTree q,BSTree &r,int &shorter)
{
	if(r->rchild==NULL)
	{
		q->data=r->data; q=r;
		r=r->lchild; free(q);
		shorter=1;
	}
	else
	{
		Delete(q,r->rchild,shorter);
		if(shorter==1)
			RightBalance_div(r,shorter);
	}
}


//平衡二叉树的删除操作
int DeleteAVL(BSTree &p,int x,int &shorter)
{
	int k;
	BSTree q;
	if(p==NULL)
	{
		printf("Hava no such node !!\n");
		return 0;
	}
	else if(x<p->data)//在p的左子树中进行删除
	{
		k=DeleteAVL(p->lchild,x,shorter);
		if(shorter==1)
			LeftBalance_div(p,shorter);
		return k;
	}
	else if(x>p->data)//在p的右子树中进行删除
	{
		k=DeleteAVL(p->rchild,x,shorter);
		if(shorter==1)
			RightBalance_div(p,shorter);
		return k;
	}
	else
	{
		q=p;
		if(p->rchild==NULL) //右子树空则只需重接它的左子树
		{
			p=p->lchild;
			free(q);
			shorter=1;
		}
		else if(p->lchild==NULL)//左子树空则只需重接它的右子树
		{
			p=p->rchild;
			free(q);
			shorter=1;
		}
		else//左右子树均不空
		{
			Delete(q,q->lchild,shorter);
			if(shorter==1)
				LeftBalance_div(p,shorter);
			p=q;
		}
		return 1;
	}
}


运行结果:


本文链接: http://www.dtmao.cc/news_show_130858.html

附件下载

相关教程

  • 潮阳“陈”姓源流

    潮阳“陈”姓源流 2010年03月05日陈姓是中国大望族之一&#xff0c;1997年8月中国科学院遗传研究所出版《中华姓氏大辞典》中&#xff0c;显示全国李、王、张、刘、陈为五大姓氏&#xff0c;陈姓居中国第五位民。但在潮阳却是列居第一位&#xff0c;是聚居村落最多人数的姓氏。…

    2020/12/22 23:04:00
  • 陈式太极拳小架一路拳谱(陈鑫拳架)

    陈鑫拳架六十四式三段十三势分节六十四式的英文译名按香港出版的 CHEN STYLE SHADOW BOXING(TAJIJUAN)第一段 为第一至五势第一势 只一势 言太极阴阳之理预备势 preparing form 开歩正立一 金刚捣碓 buddhas warrior attendant pounds mortar两臂前掤 蹲身捋按 左腿提收 上歩前…

    2020/12/22 23:03:59
  • 2015.4.20.14.09_素数_8.28_java素数的求法_0.01

    Java求素数 只有1和它本身两个因数的自然数&#xff0c;叫质数&#xff08;或称素数&#xff09;。&#xff08;如&#xff1a;由212&#xff0c;221&#xff0c;可知2的因数只有1和它本身2这两个约数&#xff0c;所以2就是质数。与之相对立的是合数&#xff1a;“除了1和它本…

    2020/12/22 23:03:58
  • 筛选法

    #include<iostream> using namespace std;const int MAXV 10000; //素数表范围bool flag[MAXV1]; //标志一个数是否为素数int prime[MAXV1]; //素数表,下标从0开始int size; //素数个数void genPrime(int max){memset(flag, true, sizeof(flag));for(int i 2; i < …

    2020/12/22 23:03:57
  • 龙格库塔法

    分享一下我老师大神的人工智能教程&#xff01;零基础&#xff0c;通俗易懂&#xff01;http://blog.csdn.net/jiangjunshow也欢迎大家转载本篇文章。分享知识&#xff0c;造福人民&#xff0c;实现我们中华民族伟大复兴&#xff01;龙格库塔法经典四阶龙格库塔法龙格-库塔(Run…

    2020/12/22 23:03:56
  • springMVC

    spring&#xff2d;VC SpringMVC架构流程&#xff1a; 1.用户发送请求至前端控制器DispatcherServlet2.DispatcherServlet收到请求调用HandlerMapping处理器映射器。3.处理器映射器根据请求url找到具体的处理器&#xff0c;生成处理器对象及处理器拦截器(如果有则生成)一并返回…

    2020/12/22 23:03:55
  • 素数算法(转载)

    2019独角兽企业重金招聘Python工程师标准>>> 关于素数的算法是信息学竞赛和程序设计竞赛中常考的数论知识&#xff0c;在这里我跟大家讲一下寻找一定范围内素数的几个算法。看了以后相信 对大家一定有帮助。 正如大家都知道的那样&#xff0c;一个数 n 如果是合数…

    2020/12/22 23:03:54
  • 一文搞定MyBatis各种标签

    文章目录select标签使用 Map 接口传递多个参数使用 Java Bean 传递多个参数insert、update、delete和sql标签< insert>元素1&#xff09;主键&#xff08;自动递增&#xff09;回填2&#xff09;自定义主键< update>与< delete>元素< sql> 元素if标签c…

    2020/12/22 23:03:53
  • 数据库(一)——数据库需求与关系建模

    前言 在数据库建设过程中&#xff0c;哪一步最重要&#xff1f;绝大多数资料会告诉你&#xff0c;是需求分析阶段。这一步的好坏甚至直接决定数据库项目的成败。 需求分析阶段&#xff0c;也被称为ER建模(entity-relationship modeling)阶段&#xff0c;也常被称为需求可视化&a…

    2020/12/22 23:03:52
  • 人件管理与中国古代史:程序员豫让

    人件管理与中国古代史&#xff1a;程序员豫让[Mental Studio]猛禽 http://mental.mentsu.com但凡混迹于软件业者&#xff0c;日日追逐新技术&#xff0c;身心俱疲&#xff0c;不免偶尔郁闷一下&#xff0c;我亦不能免俗。我不知道别人郁闷时一般会干些什么&#xff0c;反正我的…

    2020/12/22 23:03:50
  • 围棋:“我学到了一切”

    梁宁写了"蒋涛的围棋智慧 ",我要赶紧写一篇回应,不然.. Trackback: http://tb.donews.net/TrackBack.aspx?PostId733799 从围棋中能学到什么? 50年一出的天才李昌镐说:“我学到了一切。”(为什么不是百年一出,因为30年代还有一个吴清源) 当他再进行详细说明的…

    2020/12/22 23:03:48
  • 周末北大学拳散记--搜狐畅游招聘

    每周日早上都去北大俄文楼学习吴式太极拳&#xff0c;已坚持快5年了。 这周日过去发现很多学生聚在一起&#xff0c;原来是搜狐畅游招聘 左边是程序员 左边第二列是3D程序员 右边是行政人员 大家看到没有&#xff1f;要想找到好工作的机会&#xff0c;研究3D吧&#xff0c;竞争…

    2020/12/22 23:03:48
  • 发布“陈氏太极老架”APP到APPSTORE流程 【2016年3月版】

    关键字&#xff1a;钥匙串&#xff0c;签名证书&#xff0c;APP ID&#xff0c;PP 文件 &#xff0c;bundle id &#xff0c;XCODE 上传 &#xff0c;发布 不发布APP到APP STORE&#xff08;真机调试&#xff09; 关于真机调试证书的获取和使用可以参考这篇文章。 现在Xcode7不…

    2020/12/22 23:03:47
  • 陈氏太极老架一路招式、技法、王西安大师教学视频

    [img]http://dl.iteye.com/upload/attachment/270317/1ec3c79b-8f88-3c2d-8ce3-5880a6d1120a.jpg[/img][colorbrown]陈氏太极拳不但具有强大的技击性能&#xff0c;而且还具有独特的养生健身价值&#xff0c;要练好陈氏太极拳&#xff0c;首先要对陈氏太极拳在健身方面的重要价…

    2020/12/22 23:03:46
  • 算法导论-AVL树的C++实现

    代码主要来自网上流传的一份南京大学陈氏三姐妹的大作业。 花了一些时间测试和修改&#xff0c;代码基本OK了&#xff0c;结构也比较清晰。 我两把刷子&#xff0c;裸写的话没一个礼拜真下不来。 #include <stdio.h> #include <malloc.h> #include <stdlib.h&…

    2020/12/22 23:03:45
  • 新浪网中的一角 (关于陈氏的言论)

    很欣赏这位老兄,中国人素质偏下是一个根本性的原因! http://comment.news.sina.com.cn/cgi-bin/comment/comment.cgi?channelkj&newsid530081&page5 一群卑鄙的枪手还在叫嚣 我说的肮脏不是这收购本身 而是盛大的发家史&#xff0c;多少亿多少亿都是孩子们 的零花钱…

    2020/12/22 23:03:44
  • 震惊!某陈姓青年偶获Stanford cs20,一天入门TensorFlow!

    最近又重新回顾了一下tensorflow的基础知识&#xff0c;检索各大搜索引擎&#xff0c;终于决定选择了斯坦福的cs20作为学习的目标。因为最近毕设加上过年的杂事&#xff0c;并没有很多时间&#xff0c;因此只上了该课的三节课&#xff0c;将基本的知识过了一遍&#xff0c;同时…

    2020/12/22 23:03:43
  • 一文读懂APU/BPU/CPU/DPU/EPU/FPU/GPU等处理器

    致谢&#xff1a;一文读懂APU/BPU/CPU/DPU/EPU/FPU/GPU等处理器随着AI概念火爆全球&#xff0c;做AI芯片的公司也层出不穷。为了让市场和观众能记住自家的产品&#xff0c;各家在芯片命名方面都下了点功夫&#xff0c;既要独特&#xff0c;又要和公司产品契合&#xff0c;还要朗…

    2020/12/22 23:03:41
  • 【欧拉猜想】是否有无穷多个不可约分的正整数解

    证明或否定: 不定方程 a^4 b^4 c^4 d^4 (*)有正整数解。 形如 a^3b^3c^3 a^4b^4c^4d^4 a^5b^5c^5d^5e^5 ……这样的不定方程&#xff0c;是否有正整数解&#xff1f; 这类问题被称为 &#xff1a;欧拉猜想, 其中4和5的都有正整数解, 3的被证明了无整数解,其它的都还不知道。…

    2020/12/22 23:03:40
  • 第五回 人似秋鸿来有信,事如春梦了无痕

    第五回 人似秋鸿来有信&#xff0c;事如春梦了无痕 《正月二十日与潘郭二生出郊寻春忽记去》&#xff1a; 宋 苏轼 东风未肯入东门&#xff0c;走马还寻去岁村。 人似秋鸿来有信&#xff0c;事如春梦了无痕。 江城白酒三杯酽&#xff0c;野老苍颜一笑温。 已约年年为此会&#…

    2020/12/22 23:03:39
  • 中国了不起的数学家

    华罗庚 华罗庚(1910.11.12—1985.6.12)&#xff0c;出生于江苏常州金坛区&#xff0c;祖籍江苏丹阳。数学家&#xff0c;中国科学院院士&#xff0c;美国国家科学院外籍院士&#xff0c;第三世界科学院院士&#xff0c;联邦德国巴伐利亚科学院院士。中国第一至第六届全国人大常…

    2020/12/22 23:03:38
  • 陈氏太极拳的刚与柔

    陈氏太极拳五层功夫 练习太极拳同学生上学是同样道理&#xff0c;从小学到大学&#xff0c;逐步掌握越来越多的知识 。没有小学、中学的文化基础&#xff0c;就接受不了大学的课程。学习太极拳也是一层 一层由浅入深&#xff0c;循序渐进&#xff0c;如果违背了这个原则&#…

    2020/12/22 23:03:37
  • 陈氏超混沌系统相图

    陈氏超混沌系统相图&#xff08;该系统由陈关荣提出&#xff0c;故命名&#xff1a;Chen’s hyperchaos&#xff09; 建立函数&#xff1a; function dydtHyChen(t,y) global a b c d r a35; b3; c12; d7; r0.58;%input(r); dydt[a*y(2,:)-a*y(1,:)y(4,:) d*y(1,:)c*…

    2020/12/22 23:03:36
  • 陈氏太极拳的健身与技击作用

    “户枢不蠹”这句古代的名言&#xff0c;远在《吕氏春秋》就有记载&#xff0c;它在我国人民中广为流传&#xff0c;说明我国人民很早就懂得了“运动”有增强体质防治疾病的作用。我国古代的史学家陈寿在《三国志魏书华陀传》中&#xff0c;记载了、华陀所创的《五禽戏》&#…

    2020/12/22 23:03:35

共有条评论 网友评论

验证码: 看不清楚?