精华内容
下载资源
问答
  • word 资料 平衡二叉树操作的演示 需求分析 本程序是利用平衡二叉树实现动态查找表的基本功能创建表查找插入删除 具体功能 初始平衡二叉树为空树操作界面给出创建查找插入删除合并分裂六种操作供选择每种操作均提示...
  • 数据结构实习报告 题目平衡二叉树的操作演示 班级信息管理与信息系统 11-1 姓名y 学号201101050903 完成日期2013.06.25 需求分析 初始平衡二叉树为空树操作界面给出两棵平衡二叉树的显示查找插入删 除销毁合并两棵树...
  • word教育资料 数据结构实习报告 题目平衡二叉树的操作演示 班级信息管理与信息系统11-1 姓名崔佳 学号201101050903 完成日期2013.06.25 一需求分析 1. 初始平衡二叉树为空树操作界面给出两棵平衡二叉树的显示查找...
  • (1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后,更新平衡二叉树的显示。 (2) 平衡二叉树的显示采用凹入表现形式。 (3)输入的...
  • 利用平衡二叉树实现一个动态查找表。实现动态查找表的八种基本功能:构建、插入、删除、查找、合并、分裂、打印、销毁。初始状态下,平衡二叉树为空树。
  • 平衡二叉树进行演示操作,功能包括:创建平衡二叉树,查找,插入,删除,分裂和合并。
  • 平衡二叉树的操作演示,含插入、查找、删除和显示。
  • 平衡二叉树演示课设报告下载: 一、需求分析: (1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后,更新平衡二叉树的显示。 (2) 平衡...

    平衡二叉树的演示
    源文件加报告:https://download.csdn.net/download/m0_46140702/12130911
    一、需求分析:
    (1) 构建一个平衡二叉树并实现创建、插入、查找、删除、销毁等操作。每种操作均提示输入关键字。每次插入或删除一个结点后,更新平衡二叉树的显示。
    (2) 平衡二叉树的显示采用凹入表现形式。
    (3)输入的形式时数字,无论对功能的选择还是对数据的录入,都是以数字的形式进行输入,无需使用文件保存数据。 
    (4) 输出的形式时在dos界面进行输出,一旦检测到错误的输入就会报错提示用户从新输入。
    (5)程序所能达到的功能:
    A:创建一颗非空平衡二叉树
    B:向平衡二叉树中添加结点
    C:从平衡二叉树中删除结点
    D:在平衡二叉树中查找结点
    E:销毁平衡二叉树
    F:输出打印一棵平衡二叉树
    G:合并两棵平衡二叉树
    H:分裂一颗平衡二叉树

    #include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #include<conio.h> 
    #define OK 1
    #define ERROR 0
    #define TRUE 1
    #define FALSE 0
    #define OVERFLOW 0
    #define LH +1	//左子树比右子树高 
    #define EH 0	//等高 
    #define RH -1	//右子树比左子树高 
    typedef int Status;
    typedef int KeyType;
    typedef struct{
    	KeyType key;
    }RcdType;
    typedef struct BBSTNode{
    	RcdType data;
    	int bf;		//结点平衡因子
    	struct BBSTNode *lchild,*rchild; 
    }*BBSTree;		//平衡二叉树 
    
    void CreatBBST(BBSTree &T);		//构建一棵二叉平衡树 
    BBSTree SearchBBST(BBSTree T,KeyType Key);	//二叉平衡树非递归查找 
    void R_Rotate(BBSTree &p);		//对最小失衡子树p作右旋调整
    void L_Rotate(BBSTree &p);		//对最小失衡子树p作左旋调整
    void LeftBalance(BBSTree &T);	//左平衡处理操作
    void RightBalance(BBSTree &T);	//右平衡处理操作
    Status InsertAVL(BBSTree &T,RcdType e,Status &taller);		//将e插入到二叉树
    Status DeleteAVL(BBSTree &T,KeyType key,Status &shorter);	//删除值为key的结点
    void MergeBBST(BBSTree &T1,BBSTree &T2);	//合并两棵二叉树
    void Split(BBSTree T,KeyType e,BBSTree &T1,BBSTree &T2);	//分裂操作
    void SplitBBST(BBSTree T,KeyType e,BBSTree &T1,BBSTree &T2);	//防止在将二叉树T分裂好之前改变了T1或T2 
    void DestroyBBST(BBSTree &T);	//销毁树 
    void PrintBBST(BBSTree &T,int lev);		//凹入表形式显示方法
    int InsertMain(BBSTree &T,int taller);	//连续插入函数 
    void Start(BBSTree &T1,BBSTree &T2);	//操作演示界面
    int main();		//main函数 
    
    void CreatBBST(BBSTree &T){
    	//构建一棵二叉平衡树 
    	int num = 0,i,taller = 0,temp;
    	RcdType e;
    	printf("输入结点个数:");
    	if(scanf("%d",&num)==1){
    		if(num>0){
    			printf("请输入结点值\n");
    			for(i = 0;i < num;i++){
    				printf("第%d个结点的值:",i+1);
    				temp = scanf("%d",&e.key);
    				if(temp==1)
    					InsertAVL(T,e,taller); 
    				else{
    					printf("请规范输入!\n");
    					fflush(stdin);
    					i--;
    				}
    			} 
    			printf("构建成功!\n");
    		}
    		else
    			printf("构建失败!\n");
    	}
    	else 
    		printf("请规范输入!\n");
    	fflush(stdin);
    }
     
    BBSTree SearchBBST(BBSTree T,KeyType Key){
    	//二叉平衡树非递归查找 
    	while(T!=NULL){
    		if(T->data.key==Key)
    			return T;		//成功 
    		else if(T->data.key>Key)
    			T = T->lchild;		//在左子树中继续查找  
    		else 
    			T = T->rchild;		//在右子树中继续查找 
    	} 
    	return NULL;		//失败 
    }
    
    void R_Rotate(BBSTree &p){
    	//对最小失衡子树p作右旋调整
    	BBSTree lc = p->lchild;		//lc指向p结点的左孩子 
    	p->lchild = lc->rchild;		//lc结点的右子树置为p结点的左子树 
    	lc->rchild = p;		//置原根结点为lc结点的右孩子 
    	p = lc;		//p指向新的根结点 
    } 
    
    void L_Rotate(BBSTree &p){
    	//对最小失衡子树p作左旋调整
    	BBSTree rc = p->rchild;		//rc指向p结点的右孩子 
    	p->rchild = rc->lchild;	 	//rc结点的左子树置为p结点的右子树 
    	rc->lchild = p;		//置原根结点为rc结点的左孩子 
    	p = rc;		//p指向新的根结点 
    }
    
    void LeftBalance(BBSTree &T){
    	//左平衡处理操作
    	BBSTree lc,rd;
    	lc = T->lchild;		//lc指向T的左孩子
    	switch(lc->bf){		//检查T的左子树的平衡因子,并作相应处理 
    		case LH:		//LL型,需右旋调整 
    			T->bf = lc->bf = EH;	R_Rotate(T);	break;
    			//右旋后平衡因子等于0 
    		case RH:		//新结点插入在T的左孩子的右子树上属于LR型,双旋处理
    			rd = lc->rchild;
    			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作右旋调整
    			break; 
    	}  
    } 
    
    void RightBalance(BBSTree &T){
    	//右平衡处理操作
    	BBSTree rc,ld;
    	rc = T->rchild;		//lc指向T的右孩子
    	switch(rc->bf){		//检查T的右子树的平衡因子,并作相应处理
    		case RH:		//RR型,需左旋调整 
    			T->bf = rc->bf = EH;	L_Rotate(T);	break;
    		case LH:		//新结点插入在T的右孩子的左子树上属于RL型,双旋处理
    			ld = rc->lchild;
    			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作左旋调整
    	}
    }
    
    Status InsertAVL(BBSTree &T,RcdType e,Status &taller){
    	//将e插入到二叉树
    	if(T==NULL){	//T为空,树长高
    		T=(BBSTree)malloc(sizeof(BBSTNode));
    		T->data = e;
    		T->bf = EH;	T->lchild = NULL;	T->rchild = NULL;	taller = TRUE;
    	} 
    	else if(e.key==T->data.key){	//树中已经存在和e相等的结点 
    		taller = FALSE;	
    		return FALSE;	//未插入 
    	}
    	else if(e.key < T->data.key){	//插入到左子树
    		if(FALSE==InsertAVL(T->lchild,e,taller))
    			return FALSE;
    		if(TRUE==taller){
    			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{	//插入到右子树
    		if(FALSE==InsertAVL(T->rchild,e,taller))
    			return FALSE;
    		if(TRUE==taller){
    			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 TRUE;
    } 
    
    Status DeleteAVL(BBSTree &T,KeyType key,Status &shorter) {
    	//删除值为key的结点
        if(T == NULL) 
    		return FALSE;
        if(T->data.key == key) {
            BBSTree p = NULL;
            if(T->lchild == NULL) {	//被删结点的左子树为空
                p = T;
                T = T->rchild;	//直接将被删结点的右子树顶上 
                free(p);
                shorter = TRUE;	//树变矮 
            }
            else if(T->rchild == NULL) {	//被删结点的右子树为空
                p = T;
                T = T->lchild;
                free(p);
                shorter = TRUE;
            }
            else {	//被删结点左右子树都不为空
                p = T->lchild;
                while(p->rchild)	//找左子树的最大值,与删除结点交换数据
                    p = p->rchild;
                T->data.key = p->data.key;
                DeleteAVL(T->lchild,p->data.key,shorter);	//删除被替换的结点 
                if(shorter) {	//如果树变矮,调整平衡因子 
                    switch(T->bf) {
                        case LH:T->bf = EH; shorter = TRUE; break;
                        case EH:T->bf = RH; shorter = FALSE; break;
                        case RH:    //删除的结点在左子树,如果本来是右高,右旋 
                            RightBalance(T);	break;
                    }   
                }   
            }
        }
        else if(key < T->data.key) {	//在左子树中查找
            if(FALSE == DeleteAVL(T->lchild,key,shorter)) 
    		 	return FALSE;
            if(shorter) {	//在左子树中删除,如果树变矮 
                switch(T->bf) {
                    case LH:T->bf = EH; shorter = TRUE; break;
                    case EH:T->bf = RH; shorter = FALSE; break;
                    case RH:  
                        RightBalance(T);	break;
                }
            } 
        }
        else {	//在右子树中查找 
            if(FALSE == DeleteAVL(T->rchild,key,shorter)) 
    			return FALSE;
            if(shorter) {	//在右子树中删除,如果树变矮 
                switch(T->bf) {
                    case LH:  
                        LeftBalance(T);	break;
                    case EH:T->bf = LH; shorter = FALSE; break;
                    case RH:T->bf = EH; shorter = TRUE; break;                
                }
            }
        }
        return TRUE;
    }    
    
    void MergeBBST(BBSTree &T1,BBSTree &T2){
    	//合并两棵二叉树
    	int taller = 0;
    	if(!T2)
    		return;
    	MergeBBST(T1,T2->lchild);
    	InsertAVL(T1,T2->data,taller);
    	MergeBBST(T1,T2->rchild);
    	//中序遍历插入 
    } 
    
    //分裂一棵二叉树成为两棵 
    void Split(BBSTree T,KeyType e,BBSTree &T1,BBSTree &T2){
    	//分裂操作
    	int taller = 0;
    	if(!T)
    		return ;
    	Split(T->lchild,e,T1,T2);	//查找最左孩子 
    	if(T->data.key > e)
    		InsertAVL(T2,T->data,taller);
    	else
    		InsertAVL(T1,T->data,taller);
    	Split(T->rchild,e,T1,T2);
    	//中序遍历插入
    } 
    void SplitBBST(BBSTree T,KeyType e,BBSTree &T1,BBSTree &T2){
    	//防止在将二叉树T分裂好之前改变了T1或T2 
    	BBSTree t1 = NULL,t2 = NULL;
    	Split(T,e,t1,t2);
    	DestroyBBST(T1);
    	DestroyBBST(T2);	//将之前的树先销毁 
    	T1 = t1;
    	T2 = t2;
    }
    
    void DestroyBBST(BBSTree &T){
    	//销毁树 
    	if(T==NULL)	return ;
    	DestroyBBST(T->lchild);
    	DestroyBBST(T->rchild);
    	free(T);
    }
    
    void PrintBBST(BBSTree &T,int lev){
    	//凹入表形式显示方法
    	int i;
    	if(T->rchild)
    		PrintBBST(T->rchild,lev+1);
    	for(i = 0;i < lev;i++)
    		printf("  ");
    	printf("%d\n",T->data.key);
    	if(T->lchild)
    		PrintBBST(T->lchild,lev+1);
    }
    
    int InsertMain(BBSTree &T,int taller){
    	//连续插入函数 
    	int n = 0;
    	RcdType e;
    	while(scanf("%d",&e.key)==1){
    		if(InsertAVL(T,e,taller))
    			n++;
    	}
    	fflush(stdin);
    	return n;
    } 
    
    void Start(BBSTree &T1,BBSTree &T2){
    	//操作演示界面 
    	int cho=5,num,taller = 0,shorter = 0,temp;
    	RcdType e;
    	while(1){
    		system("cls");
    		printf("\n平衡二叉树操作的演示 \n");
    		printf("***********************************************************\n");
    		printf(" 平衡二叉树显示区 \n");
    		printf("T1树\n\n");
    		if(!T1)
    			printf("当前为空树\n");
    		else
    			PrintBBST(T1,1);
    		printf("\nT2树\n\n");
    		if(!T2)
    			printf(" 当前为空树\n");
    		else
    			PrintBBST(T2,1);
    		printf("\n***********************************************************\n");
    		printf("==========================================================\n");
    		printf("| T1树操作:1.创建 2.插入 3.查找 4.删除 5.销毁  11.分裂  |\n");
    		printf("| T2树操作:6.创建 7.插入 8.查找 9.删除 10.销毁 12.分裂  |\n");
    		printf("| 特殊操作:13.合并T1,T2   0.退出                        |\n");
    		printf("==========================================================\n");
    		printf("输入你要进行的操作:");
    		temp = scanf("%d",&cho);
    		fflush(stdin);	//输入多个字符,如果不清除缓冲区,那么就会进入死循环! 
    		if(temp!=1){	//输入操作不成功 
    			printf("请规范输入!\n"); 
    			printf("按任意键返回>>>\n");
    			getch();	continue;
    		}
    		switch(cho){
    			case 1: 
    				if(T1)
    					printf("树不为空!\n"); 
    				else 
    					CreatBBST(T1);
    				break;
    			case 2:
    				printf("输入要插入的值(输入任意非数字字符结束插入):"); 
    				if(num = InsertMain(T1,taller))
    					printf("成功插入了%d个结点!\n",num);	
    				else  
    					printf("插入失败!\n");
    				break;
    			case 3:
    				printf("请输入要查找关键字的值:");
    				temp = scanf("%d",&e.key);
    				fflush(stdin);
    				if(temp==1){
    					if(SearchBBST(T1,e.key))
    						printf("查找成功!\n");
    					else
    						printf("查找失败!\n");
    				}
    				else 
    					printf("请规范输入!\n");
    				break;
    			case 4:
    				printf("请输入要删除关键字的值:");
    				temp = scanf("%d",&e.key);
    				fflush(stdin);
    				if(temp==1){
    					if(DeleteAVL(T1,e.key,shorter))
    						printf("删除成功!\n");
    					else
    						printf("删除失败!\n");
    				}
    				else 
    					printf("请规范输入!\n");
    				break;
    			case 5:
    				DestroyBBST(T1);
    				T1 = NULL;	break;
    			case 6: 
    				if(T2)
    					printf("树不为空!\n"); 
    				else 
    					CreatBBST(T2);
    				break;
    			case 7:
    				printf("入要插入的值(输入任意非数字字符结束插入):");
    				if(num = InsertMain(T2,taller))
    					printf("成功插入了%d个结点!\n",num);	
    				else  
    					printf("插入失败!\n");
    				break;
    			case 8:
    				printf("请输入要查找关键字的值:");
    				temp = scanf("%d",&e.key);
    				fflush(stdin);
    				if(temp==1){
    					if(SearchBBST(T2,e.key))
    						printf("查找成功!\n");
    					else
    						printf("查找失败!\n");
    				}
    				else 
    					printf("请规范输入!\n");
    				break;
    			case 9:
    				printf("请输入要删除关键字的值:");
    				temp = scanf("%d",&e.key);
    				fflush(stdin);
    				if(temp==1){
    					if(DeleteAVL(T2,e.key,shorter))
    						printf("删除成功!\n");
    					else
    						printf("删除失败!\n");
    				}
    				else 
    					printf("请规范输入!\n");
    				break;
    			case 10:
    				DestroyBBST(T2);
    				T2 = NULL;	break;
    			case 11:
    				if(T1){
    					printf("请输入要分裂的中间值:");
    					temp = scanf("%d",&e.key);
    					fflush(stdin);
    					if(temp==1)
    						SplitBBST(T1,e.key,T1,T2);
    					else
    						printf("请规范输入!\n");
    				}
    				else 
    					printf("树为空!\n");
    				break;
    			case 12:
    				if(T2){
    					printf("请输入要分裂的中间值:");
    					temp = scanf("%d",&e.key);
    					fflush(stdin);
    					if(temp==1)
    						SplitBBST(T2,e.key,T1,T2);
    					else
    						printf("请规范输入!\n");
    				}
    				else 
    					printf("树为空!\n");
    				break;
    			case 13:
    				MergeBBST(T1,T2);
    				T2 = NULL;	break;
    			case 0:
    				system("cls");
    				exit(0);
    			default:
    				printf("请规范输入!\n");
    		}
    		printf("按任意键返回>>>\n");
    		getch();
    	}
    }
    
    int main(){
    	BBSTree T1 = NULL;
    	BBSTree T2 = NULL;
    	Start(T1,T2);
    	return 0;
    }
    
    展开全文
  • 广工数据结构课程设计(平衡二叉树演示),包含报告源代码
  • 平衡二叉树操作的演示 1. 需求分析 本程序是利用平衡二叉树实现动态查找表的基本功能创建表查找插入删除 具体功能 1 初始平衡二叉树为空树操作界面给出创建查找插入删除合并分 裂六种操作供选择每种操作均提示输入...
  • system("title 平衡二叉树操作演示"); Print(); scanf("%d",&s); while(s!=8){ switch(s) { case1: //显示 printf("\t>>-显示-); printf("T:\n"); ViewTree(T,5); printf("t:\n"); ViewTree(t,5); ...
  • 还可有附加功能,如:合并两棵平衡二叉树以及把一棵平衡二叉树分裂为两棵平衡二叉树,使得在一棵树中的所有关键字都小于或等于x,另一棵树中的任一关键字都大于x。本资源包括了可执行文件、源代码以及实验报告电子版
  • C语言编写的 数据结构 平衡二叉树 演示、含课程设计报告 多种输出平衡二叉树格式
  • 利用平衡二叉树实现一个动态查找表。 (1)实现动态查找表的三种基本功能:查找、插入和删除。 (2)初始时,平衡二叉树为空树,操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。在查找...
  • 实现的平衡二叉树的基本功能还有分裂和合并的功能
  • #include<stdio.h> #include<malloc.h> typedef int KeyType; //定义关键字类型 typedef struct node //记录类型 {KeyType... //平衡因子 struct node *lchild*rchild; //左右孩子指针 }BSTNode; void LeftProcess(BSTN
  • 1)平衡二叉树的旋转 avlTree left_left_Rotation(avlTree T) 初始条件:二叉树T存在。 操作结果:实现LL旋转。 avlTree right_right_Rotation(avlTree T) 初始条件:二叉树T存在。 操作结果:实现RR旋转。 ...

    可参考:https://blog.csdn.net/hnust_xiehonghao/article/details/7938869
    https://blog.csdn.net/u010552731/article/details/47393549
    https://github.com/zhaoxin111/AVLTree/blob/master/avltree.c
    二、概要设计
    1)平衡二叉树的旋转

    avlTree
    left_left_Rotation(avlTree T)

    初始条件:二叉树T存在。

    操作结果:实现LL旋转。

    avlTree
    right_right_Rotation(avlTree T)

    初始条件:二叉树T存在。

    操作结果:实现RR旋转。

    avlTree
    left_right_rotation(avlTree T)

    初始条件:二叉树T存在。

    操作结果:实现LR旋转。

    avlTree
    right_left_rotation(avlTree T)

    初始条件:二叉树存在。

    操作结果:实现RL旋转。

    (2)平衡二叉树的插入

    avlTree
    insert_Node(ElementType x, avlTree T)

    初始条件:二叉树T存在,需插入数据x。

    操作结果:插入数据并且旋转。

    (3)平衡二叉树的删除

    avlTree
    delete_Node(ElementType x, avlTree T)

    初始条件:二叉树T存在,需删除数据x

    操作结果:删除数据并且旋转。

    (4)平衡二叉树的查询

    int search(avlTree T, int data)

    初始条件:二叉树T存在,需查询数据x

    操作结果:输出查询成功与否的结果。

    (5)平衡二叉树先序遍历

    void
    pre_order_avltree(avlTree tree)

    初始条件:二叉树T存在。

    操作结果:先序遍历输出T。

    三、详细设计

    #include<stdio.h>

    #include<stdlib.h>

    typedef int ElementType;

    typedef struct Node {

    ElementType data;
    
    int height;//深度
    
    struct Node *left, *right;
    

    }avlNode, *avlTree;

    int get_Height(avlTree N) {

    if (!N)
    
        return 0;
    
    else
    
        return N->height;
    

    }

    int max_Height(int x, int y) {

    if (x > y)
    
        return x;
    
    else
    
        return y;
    

    }

    void menu(){

    printf("--------------1、插入数据--------------\n");
    
    printf("--------------2、查找数据--------------\n");
    
    printf("--------------3、删除数据--------------\n");
    
    printf("--------------4、结束程序--------------\n");
    

    }

    int search(avlTree T, int data) {

    if (T == NULL) {
    
        printf("不存在该数\n");
    
        return 0;
    
    }
    
    if (T->data == data) {
    
        printf("存在该数\n");
    
        return 0;
    
    }
    
    else if (data < T->data) {
    
        search(T->left, data);
    
    }
    
    else {
    
        search(T->right, data);
    
     }
    

    }

    avlTree left_left_Rotation(avlTree T) {

    avlTree k2 = T->left;
    
    T->left =k2->right;
    
    k2->right= T;
    
    T->height =max_Height(get_Height(T->left), get_Height(T->right)) + 1;
    
    k2->height= max_Height(get_Height(k2->left), get_Height(k2->right) + 1);
    
    return k2;
    

    }

    avlTree right_right_Rotation(avlTree T) {

    avlNode *k3 = T->right;
    
    T->right =k3->left;
    
    k3->left= T;
    
    T->height =max_Height(get_Height(T->left), get_Height(T->right)) + 1;
    
    k3->height= max_Height(get_Height(k3->left), get_Height(k3->right)) + 1;
    
    return k3;
    

    }

    avlTree left_right_rotation(avlTree T) {

    T->left = right_right_Rotation(T->left);
    
    T = left_left_Rotation(T);
    
    return T;
    

    }

    avlTree right_left_rotation(avlTree T) {

    T->right = left_left_Rotation(T->right);
    
    T = left_right_rotation(T);
    
    return T;
    

    }

    avlTree insert_Node(ElementType x, avlTree T) {

    if (T==NULL) {
    
        T = (avlTree)malloc(sizeof(avlNode));
    
        T->left = NULL;
    
        T->right = NULL;
    
        T->height = 0;
    
        T->data = x;
    
    }
    
    else if (x < T->data) {
    
        T->left = insert_Node(x, T->left);
    
        if (get_Height(T->left) -get_Height(T->right) == 2) {
    
             if (x < (T->left)->data){
    
                 T = left_left_Rotation(T);
    
             }
    
             else
    
                 T = left_right_rotation(T);
    
        }
    
    }
    
    else if (x > T->data) {
    
        T->right =insert_Node(x, T->right);
    
        if (get_Height(T->right) -get_Height(T->left) == 2)
    
        {
    
             if (x > T->right->data)  {
    
                 T =right_right_Rotation(T);
    
             }
    
             else  {
    
                 T =right_left_rotation(T);
    
             }
    
        }
    
    }
    
    else {
    
        printf("不允许插入相同值结点\n");
    
    }
    
    T->height =max_Height(get_Height(T->left), get_Height(T->right)) + 1;
    
    return T;
    

    }

    avlTree delete_Node(ElementType x, avlTree T) {

    if (!T) {
    
        printf("ERROR\n");
    
        return NULL;
    
    }
    
    if (x < T->data)
    
        T->left =delete_Node(x, T->left);
    
    else if (x > T->data)
    
        T->right =delete_Node(x, T->right);
    
    else {
    
        if (T->left&&T->right) {
    
             avlTree temp = T->right;
    
             while (temp->left != NULL) {
    
                 temp= temp->left;
    
             }
    
             T->data =temp->data;
    
             T->right =delete_Node(temp->data, T->right);
    
             if (get_Height(T->left) -get_Height(T->right) == 2) {
    
                 if ((T->left->right!= NULL) &&get_Height(T->left->right)> get_Height(T->left->left))
    
                     left_left_Rotation(T);
    
                 else
    
                     left_left_Rotation(T);
    
             }
    
        }
    
        else {
    
             avlTree temp = T;
    
             if (!T->left)
    
                 T = T->right;
    
             else if (!T->right)
    
                 T = T->left;
    
             free(temp);
    
        }
    
    }
    
    if (T) {
    
        T->height =max_Height(get_Height(T->left), get_Height(T->right));
    
    }
    
    return T;
    

    }

    void pre_order_avltree(avlTree tree){//先序遍历

    if (tree){
    
        printf("%d ", tree->data);
    
        pre_order_avltree(tree->left);
    
        pre_order_avltree(tree->right);
    
    }
    

    }

    int main()
    {

    avlTree root=NULL;
    
    int num, n;
    
    menu();
    
    while (1) {
    
        printf("输入所选选项:");
    
        scanf_s("%d", &num);
    
        switch (num) {
    
        case 1:
    
             printf("请输入要插入的数据:");
    
             scanf_s("%d", &n);
    
             root=insert_Node(n,root);
    
             printf("先序遍历:");
    
             pre_order_avltree(root);
    
             printf("\n");
    
             menu();
    
             break;
    
        case 2:
    
             printf("请输入要查询的数据:");
    
             scanf_s("%d", &n);
    
             search(root,n);
    
             menu();
    
             break;
    
        case 3:
    
             printf("请输入要删除的数据:");
    
             scanf_s("%d", &n);
    
             root=delete_Node(n,root);
    
             printf("先序遍历:");
    
             pre_order_avltree(root);
    
             printf("\n");
    
             menu();
    
             break;
    
        case 4:
    
             return 0;
    
        }
    
    }
    
    return 0;
    

    }

    展开全文
  • 平衡二叉树

    2019-11-28 21:24:36
    平衡二叉树是外国的两个大爷发明的。一开始发明的是二叉查找树。后来觉得不给力演化成了平衡二叉树。那什么是二叉查找树呢?我们给出一张图来看看: 看到这张图我们就会发现如下的特征。从每个节点出发,左边的...

    一、概念

    平衡二叉树是外国的两个大爷发明的。一开始发明的是二叉查找树。后来觉得不给力演化成了平衡二叉树。那什么是二叉查找树呢?我们给出一张图来看看:

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    看到这张图我们就会发现如下的特征。从每个节点出发,左边的节点一定小于右边的。但是你会发现这可以高低不平,看起来很不美观。于是慢慢的演化成了平衡二叉树。(当然不是因为美观演化的)。也就是说平衡二叉树的前提就是一颗二叉查找树

    平衡二叉树定义(AVL):

    (1)它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1,

    (2)它的左子树和右子树都是一颗平衡二叉树。

    也就是说以上两条规则,只要破坏了一个就不是平衡二叉树了。比如说下面这张图。

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    上面这张图就是破坏了二叉查找树这一条规则。当然了还有一条规则。也就是他的高度只差不能超过1

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    现在相信我们已经明白了什么是平衡二叉树。下面我们就来看看平衡二叉树的增删改查操作是怎么样的。

    二、平衡二叉树的插入操作

    我们先从最简单的入手,一步一步来。

    1、右旋

    首先我们插入几个数字,50,45,44。通过动画我们来演示一遍

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    (1)插入50根节点不会出现任何操作

    (2)插入45,往左边插入即可

    (3)插入44,破坏了平衡,于是右旋。

    2、左旋

    我们插入几个数字,50,60,70。通过动画我们来演示一遍

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    (1)插入50根节点不会出现旋转

    (2)插入60,往右边插入即可

    (3)插入70,破坏了平衡,于是左旋。

    3、先右旋再左旋

    我们依次插入50,60,55.通过动画我们演示一遍

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    (1)插入55,根节点,不会出现旋转

    (2)插入60,往右边插入

    (3)插入55,破坏了平衡,于是先把55和60右旋,然后整体左旋。

    4、先左旋后右旋

    我们依次插入50,40,45.通过动画我们演示一遍。

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    (1)插入55,根节点,不会出现旋转

    (2)插入40,往左边插入

    (3)插入45,破坏了平衡,于是先把45和40左旋,然后整体右旋。

    现在我们基本上已经把插入的几种情况罗列出来了。现在我们画一张图,来一个总结。

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    上图对于每一种情况,从上往下看就好了。对于平衡二叉树的删除操作,其实也是同样的道理,找到相应的元素之后,对其进行删除,删除之后如果破坏了平衡,只需要按照上面的这几种情况进行调整即可。下面我们来分析一下平衡二叉树的查找操作。

    三、平衡二叉树的查找

    平衡二叉树的查找很简单,只需要按照二叉查找树的顺序执行就好。我们使用一张动画演示一下:

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    现在平衡二叉树的操作相信你已经能够理解。下面我们就来关注最后一个问题,那就是如何手写一颗平衡二叉树呢?

    四、手写一颗平衡二叉树

    平衡二叉树的代码操作,难点在于旋转。只要把旋转弄清楚基本上整个树就能完成了,根据上面旋转的特点我们从零开始定义一颗。

    第一步:定义节点

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    第二步:插入数据

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    第三步:左旋和右旋的调整

    1、右旋

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    2、左旋

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    第四步:计算平衡和深度

    1、计算平衡

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    2、计算深度

    面试官让我手写一个平衡二叉树,我当时就笑了

     

    看起来代码有些多,其实梳理一下就不多了。

    (1)首先定义一个节点,里面有get和set方法,构造函数等等做准备工作

    (2)直接写业务流程,比如说这里的insert操作,里面涉及到的旋转操作先用方法代替

    (3)对主业务流程的操作,缺哪一个方法,写哪一个方法即可

    展开全文
  • 头文件出现错误需要大面积改动吗 头文件改动复杂吗 好
  • 数据结构实验--平衡二叉树操作的演示

    千次阅读 多人点赞 2018-03-25 18:10:32
    一、题目描述利用平衡二叉树实现一个动态查找表,实现动态查找表的三种基本功能:查找、插入和删除。二、需求分析1.建立平衡二叉树并进行创建、查找、插入、删除等功能。2.设计一个实现平衡二叉树的程序,可进行...

    一、题目描述

    利用平衡二叉树实现一个动态查找表,实现动态查找表的三种基本功能:查找、插入和删除。

    二、需求分析

    1.建立平衡二叉树并进行创建、查找、插入、删除等功能。

    2.设计一个实现平衡二叉树的程序,可进行创建、查找、插入、删除等操作,实现动态的输入数据,实时的输出该树结构。

    3.测试数据:自选数据

    三、概要设计

    1.抽象数据类型定义:

    typedef struct BSTNode {

    int data;    

            int bf;                         //节点的平衡因子

             structBSTNode *lchild,*rchild;    //左右孩子指针

    }BSTNode,*BSTree;

     

    voidCreatBST(BSTree &T);        //创建平衡二叉树

    voidR_Rotate(BSTree &p);         //对以*p为根的二叉排序树作左旋处理

    voidL_Rotate(BSTree &p);         //对以*p为根的二叉排序树作左旋处理

    voidLeftBalance(BSTree &T);      //对以指针T所指结点为根的二叉树作左平衡旋转处理

    voidRightBalance(BSTree &T);    //对以指针T所指结点为根的二叉树作右平衡旋转处理

    boolInsertAVL(BSTree &T,int e,bool &taller);          //插入结点e

    boolSearchBST(BSTree &T,int key);                 //查找元素key是否在树T中

    void LeftBalance_div(BSTree &p,int&shorter);        //删除结点时左平衡旋转处理

    void RightBalance_div(BSTree &p,int&shorter);       //删除结点时右平衡旋转处理

    void Delete(BSTreeq,BSTree  &r,int &shorter);       //删除结点

    int DeleteAVL(BSTree &p,int x,int&shorter);          //平衡二叉树的删除操作

    void PrintBST(BSTree T,int m);                     //按树状打印输出二叉树的元素

     

    2.主程序的流程

     

    请输入操作的选项编号(1-5)

     

    1---创建平衡二叉树

    2---查找

    3---插入

    4---删除

    5---结束

     

    3.各模块之间的层次调用

    四、详细设计

    1.以平衡二叉树的插入和平衡化为例:

    bool InsertAVL(BSTree &T,int e,bool&taller)

    {

    //若存在平衡的二叉排序树T中不存在和e有相同关键字的节点,则插入一个数据元素为e

    //的新结点,并返回1,否者返回0。若因插入而使二叉排序树失去平衡,则作平衡旋转理,

    //布尔变量taller反映T长高与否。

        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("已存在相同关键字的结点\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;

                }//switch(T->bf)

            }//if

            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;

                }//switch(T->bf)

            }//else

       }//else

       return 1;

    }//InsertAVL

    2.说明:执行完输入函数后,会在键盘缓冲区中保存回车键,后面再对字符型量

    赋值时,会将缓冲区当成数据存入变量中,所以要在某些输入语句后面加getchar

    函数。

    五、调试分析

    1. 遇到的问题

    (1)对平衡二叉树的删除的算法设计程序存在很大问题。删除节点后需要对新的排序树平衡化,改变节点的信息,使之形成一棵新的平衡二叉树。

    (2)主函数中的实参和子函数中的实参相等,造成调用该子函数时,虽然没有错误,但其功能不能正确的实现。改变该变量后程序成功实现各种功能。

    (3)一些逻辑逻辑运算符书写不正确,造成实现的功能不正确或程序死循环。

    六、用户使用说明

    1.了解程序清单上给出的功能,并根据提示依次进行操作。

    2.创建二叉树,输入的数据元素为整数,当输入-123时,停止创建。并显示平衡二叉树的中序凹入树形图。

    3.查找(输入你要查找的元素)。

    4.插入(输入要插入的数据元素,并输出)

    5.删除(删除指定的元素,并输出)

    6.结束

    说明:其中每一个功能实现后都会提示是否继续:选择y继续,否则,终止。

     

    七、总结

    经过这次课程设计实验,我体会到只有保持耐心,坚持到底才有可能做好事情。这次课程设计加强了我动手解决问题的能力,巩固和加深了对数据结构的理解,提高了综合运用课程知识的能力,培养了独立思考、深入研究、分析问题和解决问题的能力。

        同时,我也明白了将理论知识与实际相结合的重要性,只有理论知识远远不够,因为在实际设计中还是会遇到不少问题,这次实验使我发现了自己很多知识漏洞,这对我今后的学习来说是一次非常宝贵的体验。

    收获:

    1)对平衡二叉树的构造、插入和删除的算法思想有了更清楚的认识,能够对平衡二叉树进行创建、调平、插入、删除等操作,实现动态的输入数据,实时的输出该树结构.

    2)对多个程序的调用

    八、附录

    源代码:

    #include<stdio.h>
    #include<stdlib.h>
    
    #define LH +1
    #define EH 0
    #define RH -1
    #define NULL 0
    
    typedef struct BSTNode {
    	int data;
    	int bf;
    	struct BSTNode *lchild,*rchild;
    }BSTNode,*BSTree;
    
    void CreatBST(BSTree &T);
    void R_Rotate (BSTree &p);
    void L_Rotate(BSTree &p);
    void LeftBalance(BSTree &T);
    void RightBalance(BSTree &T);
    bool InsertAVL(BSTree &T,int e,bool &taller);
    bool SearchBST(BSTree &T,int key);
    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);
    void PrintBST(BSTree T,int depth);
    
    void main()
    {
    	BSTree T;
    	int sear,cmd,depth;
    	char ch;
    	int shorter=0;
        bool taller=false;
    	T=(BSTree)malloc(sizeof(BSTNode));
    	T=NULL;
    	printf("****************平衡二叉树的操作菜单****************\n");
    	printf("                    1--创建\n");
    	printf("                    2--查找\n");
        printf("                    3--插入\n");
       	printf("                    4--删除\n");
        printf("                    5--退出\n");
    	printf("****************************************************\n");
    	do
    	{
            printf("\n请选择操作的编号:");
    		scanf("%d",&cmd);
    		getchar();
    		switch(cmd)
    		{
    		case 1:
    			CreatBST(T);break;
    		case 2:
    			printf("请输入您要查找的关键字:");
    				scanf("%d",&sear);getchar();
    			if(SearchBST(T,sear)) printf("关键字%d存在,查找成功!\n",sear);
    			else printf("查找失败!\n");
    			break;
    		case 3:
    			printf("请输入您要插入的关键字:");
    				scanf("%d",&sear);getchar;
    			InsertAVL(T,sear,taller);depth=0;
    			PrintBST(T,depth);
    			break;
    		case 4:
    			depth=0;
    			printf("请输入你要删除的关键字: ");
    			scanf("%d",&sear); getchar();
    			DeleteAVL(T,sear,shorter);
    			PrintBST(T,depth); 
    			break;
    		case 5:
    			printf("结束!\n");
    			break;
    		default:
    			printf("输入错误!\n");
    		}
    		if(cmd==5)
    			break;
    		printf("\n继续吗? y/n: ");
    		scanf("%s",&ch);
    		getchar();
    		printf("\n");
    	}while(ch=='y');
    	printf("\n");
    }
    
    void CreatBST(BSTree &T)
    {
    	int depth;
    	int e;
        bool taller=false;
    	T = NULL;
    	printf("\n请输入关键字(以-123结束建立平衡二叉树):");
    	scanf("%d",&e);
    	getchar();
    	while(e != -123)
    	{
    		InsertAVL(T,e,taller);
    		printf("\n请输入关键字(以-123结束建立平衡二叉树):");
    		scanf("%d",&e);
    		getchar();
    		taller=false;
    	}
    	depth=0;
    	printf("\n****************************************************\n");
    	printf("                 您创建的二叉树为\n");
    	if(T)
    		PrintBST(T,depth);
    	else
    		printf("这是一棵空树!\n");
    }
    
    void R_Rotate (BSTree &p)    //对以*p为根的二叉排序树作右旋处理
    {
    	BSTree lc;
    	lc=p->lchild;
    	p->lchild=lc->rchild;
    	lc->rchild=p;
    	p=lc;
    }
    
    void L_Rotate(BSTree &p)   //对以*p为根的二叉排序树作左旋处理
    {
    	BSTree rc;
    	rc=p->rchild;
    	p->rchild=rc->lchild;
    	rc->lchild=p;
    	p=rc;
    }
    
    void LeftBalance(BSTree &T)    //对以指针T所指结点为根的二叉树作左平衡旋转处理
    {
    	BSTree lc,rd;
    	lc=T->lchild;
    	switch(lc->bf)
    	{
    	case LH:
    		T->bf=lc->bf=EH;
    		R_Rotate(T);
    		break;
    	case RH:
    		rd=lc->rchild;
    		switch(rd->bf)
    		{
    		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);
    		R_Rotate(T);
    	}
    }
    
    void RightBalance(BSTree &T)     //对以指针T所指结点为根的二叉树作右平衡旋转处理
    {
    	BSTree rc,ld;
    	rc=T->rchild;
    	switch(rc->bf)
    	{
    	case RH:
    		T->bf=rc->bf=EH;
    		L_Rotate(T);
    		break;
    	case LH:
    		ld=rc->lchild;
    		switch(ld->bf)
    		{
    		case RH:T->bf=LH;rc->bf=EH;break;
    		case EH:T->bf=rc->bf=EH;break;
    		case LH:T->bf=EH;rc->bf=RH;break;
    		}
    		ld->bf=EH;
    		R_Rotate(T->rchild);
    		L_Rotate(T);
    	}
    }
    
    bool InsertAVL(BSTree &T,int e,bool &taller)  //插入结点e
    {
    	if(!T)
    	{
    		T=(BSTree)malloc(sizeof(BSTNode));
    		T->data=e;
    		T->lchild=T->rchild=NULL;
    		T->bf=EH;
    		taller=true;
    	}
    	else{
    		if(e==T->data)
    		{
    			taller=false;
    			printf("已存在相同关键字的结点!\n");
    			return 0;
    		}
    		if(e<T->data)
    		{
    			if(!InsertAVL(T->lchild,e,taller))
    				return 0;
    			if(taller)
    				switch(T->bf)
    			{
    				case LH:
    					LeftBalance(T);taller=false;break;
    				case EH:
    					T->bf=LH;taller=true;break;
    				case RH:
    					T->bf=EH;taller=false;break;
    			}
    		}
    		else{
    			if(!InsertAVL(T->rchild,e,taller))
    				return 0;
    			if(taller)
    				switch(T->bf)
    			{
    				case LH:
    					T->bf=EH;taller=false;break;
    				case EH:
    					T->bf=RH;taller=true;break;
    				case RH:
    					RightBalance(T);taller=false;break;
    			}
    		}
    	}
    }
    
    bool SearchBST(BSTree &T,int key)   //查找元素key是否在树T中
    {
    	if(!T)
    		return false;
    	else if(key==T->data)
    		return true;
    	else if(key<T->data)
    		return SearchBST(T->lchild,key);
    	else
    		return SearchBST(T->rchild,key);
    }
    
    void LeftBalance_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->rchild;
    		if(p1->bf==0)
    		{
    			L_Rotate(p);
    			p1->bf=1; p->bf=-1; shorter=0;
            }
    		else if(p1->bf==-1)
            {
    			L_Rotate(p);
                p1->bf=p->bf=0; shorter=1;
            }
    		else 
            {
    			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("不存在要删除的关键字!\n"); return 0;}
        else if(x<p->data)
        { 
    		k=DeleteAVL(p->lchild,x,shorter);
            if(shorter==1)
    			LeftBalance_div(p,shorter);
    		return k;
    	}
    	else if(x>p->data)
        {
    		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;
    	}
    }
    
    void PrintBST(BSTree T,int depth)
    {
    	int i;
    		if(T->rchild)
    			PrintBST(T->rchild,depth+1);
    		for(i=1;i<=depth;i++)
    			printf("     ");
    		printf("%d\n",T->data);
    		if(T->lchild)
    			PrintBST(T->lchild,depth+1);
    }
    
    

    展开全文
  •   我们知道在二叉查找树中,如果插入元素的顺序接近有序,那么二叉查找树将退化...如何使得二叉查找树无论在什么样情况下都能使它的形态最大限度地接近满二叉树以保证它的查找效率呢? 前苏联科学家G.M. Adels...
  • 平衡二叉树操作

    2013-06-19 15:56:16
    演示程序中,初始,平衡二叉树是空树,操作界面给出查找、插入和删除三种操作供选择。每种操作均要提示输入关键字。每次插入或删除一个结点后 ,自动更新平衡二叉树的显示。
  • 数据结构课程设计-平衡二叉树的操作!本人以前做的就是这个,非常不错的,不过就只有代码哦!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 4,977
精华内容 1,990
关键字:

平衡二叉树的演示