文档章节

平衡二叉排序树,建树,删除c语言实现

FL_NC
 FL_NC
发布于 2016/08/17 14:16
字数 1887
阅读 16
收藏 0
点赞 0
评论 0

日常打代码,日常复习,博主的文字都很少

#include <stdio.h>
#include <stdlib.h>
#define LH 1 //左高
#define RH -1 //右高
#define EH  0 //等高
typedef struct TNode{
  int data;//数据
  int number;//计数器
  int bf;//平衡因子,左子树的深度减去右子树的深度
  struct TNode *lchild;//左子树
  struct TNode *rchild;//右子树
}TNode,*BTree;
//初始化一颗空二叉树
void InitBTree(BTree *T){
   (*T)=NULL;
}
//创建二叉平衡排序树
 int InsertVAL(BTree *T,int key,int *taller){
     if(*T==NULL){//生成新的结点
       *T=(BTree)malloc(sizeof(TNode));
       (*T)->data=key;
       (*T)->number=1;
       (*T)->bf=EH;
       (*T)->lchild=(*T)->rchild=NULL;
        *taller=1;
      printf("%d插入成功\n",(*T)->data);
     }else  if((*T)->data==key){
       (*T)->number=(*T)->number+1;
       printf("%d已存在计数器加1\n",key);
       *taller=0;
       return 0 ;
     }else if(key<(*T)->data){//在左子树遍历
       if(!InsertVAL(&(*T)->lchild,key,&*taller)) return 0;
       if(*taller){//有新的结点插入左子树
        switch((*T)->bf){//检查平衡度
        case LH:LeftBalance(&(*T));*taller=0; break; //原本左子树比右子树高,需做平衡出来
        case EH: (*T)->bf=LH; *taller=1;break;       //原本左右子树等高,现因左因子增高而使树等高
        case RH: (*T)->bf=EH; *taller=0;break;       //原本右子树比左子树高,现在一样高
        }
       }
     }else {
      if(!InsertVAL(&(*T)->rchild,key,&*taller)) return 0;
      if(*taller){
        switch((*T)->bf){
        case LH: (*T)->bf=EH; *taller=0; break;
        case EH: (*T)->bf=RH; *taller=1; break;
        case RH:RightBalance(&(*T));*taller=0;break;
        }
      }
     }
   return 1;
 }
//画图理解
//LL型转uy
//右旋顺时针
//R_Rotate
void R_Rotate(BTree *p){
    BTree T2;
    T2=(*p)->lchild;
    (*p)->lchild=T2->rchild;
    T2->rchild=(*p);
    *p=T2;//p指向新的跟结点
}
//RR型旋转
//左旋逆时针
//L_Rotate
 void L_Rotate(BTree *p){
     BTree T2;
     T2=(*p)->rchild;
     (*p)->rchild=T2->lchild;
     T2->lchild=(*p);
     *p=T2;//p指向新的跟结点
}
//左平衡旋转包括LL型和LR型
void LeftBalance(BTree *T){
   BTree LT,RT;
   LT=(*T)->lchild;
  switch(LT->bf){
     case LH: //插在左子树的左孩子
        (*T)->bf=LT->bf=EH;
        //LL型调整
        R_Rotate(T);
        break;
    case EH:                //删除时需要,插入不需要
            (*T)->bf = 1;
            LT->bf = -1;
            R_Rotate(&(*T));
            break;
     case RH://插在左子树的右孩子
     RT=LT->rchild;
     switch(RT->bf){
     //先调整平衡因子在做旋转
     //为容易理解,约定左高或右高其中右子树或左子树为空,另一边的子树只有一个结点
     case LH:(*T)->bf=RH;LT->bf=EH; break;//左高,则RT的右子树为空,两次旋转后,T的左子树为空,因为T的左子树挂的是RT的右子数。
                                             //LT的右子树挂上RT的左子树,LT的平衡因子为0

     case EH:(*T)->bf=LT->bf=EH; break;//等高,RT的左右子树等高或都为空,则两次旋转后LT,T都等高
     case RH:(*T)->bf=EH;LT->bf=LH; break;
     }//switch((*RT)->bf)
     RT->bf=EH;//两次旋转后RT成为新的跟结点
      L_Rotate(&(*T)->lchild);
      R_Rotate(T);
  }
}
//右平衡旋转,包括RR型和RL型
void RightBalance(BTree *T){
  BTree RT,LT;
  RT=(*T)->rchild;
  switch(RT->bf){
  case RH:
    (*T)->bf=RT->bf=EH;
     L_Rotate(T);
    break;
    case EH:            //删除时需要,插入不需要,画图理解
            (*T)->bf = -1;//旋转后,RT的左子树挂在T的右子树,所以右高
            RT->bf = 1;//旋转后RT为此时的根节点,相当于T,原来的T成为RT的左子树,所以左高
            L_Rotate(&(*T));
            break;
    case LH:
   LT=RT->lchild;
    switch(LT->bf)
    {
    case LH:(*T)->bf=EH;RT->bf=RH;break;
    case EH:(*T)->bf=EH;RT->bf=EH;break;
    case RH:(*T)->bf=LH;RT->bf=EH;break;
   }
    LT->bf=EH;
    R_Rotate(&(*T)->rchild);
    L_Rotate(T);
    }
}
void  getData( BTree T){
if(T!=NULL){
    getData(T->lchild);
   int i;
   for(i=0;i<T->number;i++){
     printf("%d    ",T->data);
   }
    getData(T->rchild);
}

}
void  getData1( BTree T){
if(T!=NULL){
    printf("%d    ",T->data);
    getData1(T->lchild);
   int i;
    for(i=0;i<T->number;i++){

   }
    getData1(T->rchild);
}

}
void  getData2( BTree T){
if(T!=NULL){

    getData2(T->lchild);
   int i;
    for(i=0;i<T->number;i++){

   }
    getData2(T->rchild);
    printf("%d    ",T->data);
}

}
//删除结点
int DeleteNOde(BTree *T,int data,int *taller){
    if((*T)==NULL||((*T)->data==data&&(*T)->number>1)){
            //存在多个相同的数,number-1
        (*T)->number=(*T)->number-1;
        return 0;
    }else if((*T)->data==data){
      if((*T)->lchild==NULL){//包括左子树为空和左右子树都为空
        BTree  p=(*T);
        (*T)=(*T)->rchild;
        *taller=1;
        printf("%d删除成功!\n",data);
        free(p);
      }else if((*T)->rchild==NULL){//左子树不为空,右子树为空
          BTree p=(*T);
          (*T)=(*T)->lchild;
          *taller=1;
          free(p);
      }else{//左右都不为空
        BTree p=(*T)->lchild;
       //找到T右子树最大数p->data,并赋值给T
        while(p->rchild!=NULL){
            p=p->rchild;
        }
        (*T)->data=p->data;
        //此时删除data,变成删除p->data
        DeleteNOde(&(*T)->lchild,p->data,&*taller);
      }
      //在左子树删除结点
    } else if(data<(*T)->data){
        //如果没有删除成功,则不调整
       if(!DeleteNOde(&(*T)->lchild,data,&*taller)){
        return 0;
       }
       if(*taller){
        switch((*T)->bf){
        case LH: (*T)->bf=EH,*taller=1; break;//原本左高,左子树删除一个结点,树的高度发生变化,此时等高
        case EH: (*T)->bf=RH,*taller=0; break;//原本等高,左子树删除一结点,此时右高
        case RH:
            if((*T)->rchild->bf == 0)
					{                //T->rchild平衡因子等高,
						*taller = 0;//T进行一次旋转即平衡,此时树的高度不变,taller=0
					}
					else
					{
						*taller = 1;//(1)T的平衡因子和T->rchild的平衡因子相等,做一次旋转即平衡,此时
                                    //树变矮,taller=1
					}               //(2)T的平衡因子和T->rchild的平衡因子符号相反,需做两旋转平衡
					                //此时树变矮,taller=1
            RightBalance(&(*T)); break;
        }
       }/*
          总结:设p为回溯至根节点的路径上的某一结点,观察p的平衡因子。
          1.如果p的当前平衡因子等高,则根据其左子树或右子树是否减短,将p的当前平衡因子做相应的改变,变量shorter设置为false
          2.如果p的当前平衡因子不等高,且p的较高的子树被减短,将p的当前平衡因子改成等高,变量shorter设置true
          3.如果p的当前平衡因子不等高,且p的较短的子树被减短,假设q指向p的较高的子树的跟结点
            a.如果q的平衡因子等高,则需要在p处进行一次单旋转,shorter设置为false
            b.如果q的平衡因子等于p的平衡因子,则需要在p处进行一次单旋转,shorter设置为true
            c.假设p和q的平衡因子符号相反,则需要在p处进行一次双旋转(即在q出进行一次单旋转,再在p进行一次单旋转)。调整平衡因子,将shorter设置为true
       */


    }else{
         if(!DeleteNOde(&(*T)->rchild,data,&*taller))
    {
      return 0;
    }
    if(*taller)
    {
      switch((*T)->bf)
      {
        case 1:
            if((*T)->lchild->bf == 0)
					{
						*taller = 0;
					}
					else
					{
						*taller= 1;
					}
         LeftBalance(&(*T));break;
        case 0:
          (*T)->bf = 1;
         *taller= 0;
          break;
        case -1:
        (*T)->bf = 0;
         *taller = 1;
          break;
      }
    }
    }
 return 1;
}
//求树的深度
void Depth(BTree *T,int level,int *haval){
   if((*T)!=NULL){
     if(level>*haval) *haval=level;
      Depth(&(*T)->lchild,level+1,&*haval);
      Depth(&(*T)->rchild,level+1,&*haval);
   }
}
int Depth1(BTree T)
{
	if (T==NULL)
		return 0;
	else
	{
		int ld = Depth1(T->lchild);
		int rd = Depth1(T->rchild);
		return 1 + (ld >rd ? ld : rd);
	}
}
 int isBalance(BTree T)
{
	if (T==NULL)
		return 1;
	int dis = Depth1(T->lchild) - Depth1(T->rchild);
	if (dis>1 || dis<-1 )
		return 0;
	else
		return isBalance(T->lchild) && isBalance(T->rchild);
}
int main()
{   BTree T;//=NULL;
    InitBTree(&T);
    int a[]={1,45,92,78,32,46,12,11,11,1,1,11,1,12,23,24,25,26,27,28,29,37,42};
    int i;
    int n=sizeof(a)/sizeof (int);
    //测试函数
    int taller;
      int isb;
    for(i=0;i<n;i++){
    InsertVAL(&T,a[i],&taller);
    //验证是否为平衡二叉树,返回1是,0否
     isb=isBalance(T);
     printf("isb=%d\n",isb);
    }

  isb=isBalance(T);
  printf("isb=%d\n",isb);
     //中序遍历
     getData(T);
      printf("\n");
    int haval=0;
    //求树的深度
   Depth(&T,1,&haval);

     printf("\n");
    printf("haval=%d\n",haval);
    printf("\n");
    int b;

    for(i=0;i<n;i++){
    //删除结点
     DeleteNOde(&T,a[i],&b);
     isb=isBalance(T);
     printf("isb=%d\n",isb);
     int haval1=0;
     Depth(&T,1,&haval1);
     printf("\n");
    printf("haval1=%d\n",haval1);
    printf("\n");
    getData(T);
    printf("\n");
    }
    InsertVAL(&T,1,&taller);
   InsertVAL(&T,1,&taller);
    getData(T);
    printf("\n");

    printf("Hello world!\n");
    return 0;
}

,哈哈,文字都在程序里,程序都是可以直接运行

© 著作权归作者所有

共有 人打赏支持
FL_NC
粉丝 7
博文 7
码字总数 5117
作品 0
哈尔滨
程序员
二叉排序树(Binary Sort Tree)

1、定义 二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为:二叉排序树或者是空树,或者是满足如下性质的二叉树: ① 若它的左子树非空,则左子树上所有...

野渡书生 ⋅ 2016/04/28 ⋅ 0

小蚂蚁学习数据结构(32)——二叉排序树的概念

二叉排序树,定义: 1,若左子树非空,则左子树上所有节点的关键字均小于根节点关键字。 2,若右子树非空,则右子树上所有节点的关键字均大于根节点关键字。 3,左右子树本身又是一颗二叉树。...

嗜学如命的小蚂蚁 ⋅ 2016/02/07 ⋅ 0

二叉排序树的java实现

二叉排序树,又称为二叉查找树。它或者是一棵空树。或者具有以下性质 (1)若它的左子树不空,则左子树所有的结点的值均小于它的根结构的值。 (2)若它在右子树不空,则右子树上所有结点的值...

liuzhangheng ⋅ 2014/04/28 ⋅ 0

Java关于数据结构的实现:树

关于作者 郭孝星,程序员,吉他手,主要从事Android平台基础架构方面的工作,欢迎交流技术方面的问题,可以去我的Github提issue或者发邮件至guoxiaoxingse@163.com与我交流。 文章目录` 一 ...

郭孝星 ⋅ 2017/09/28 ⋅ 0

二叉树知识点回忆以及整理

二叉树 在计算机科学中,二叉树是每个节点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”,左子树和右子树同时也是二叉树。二叉树的子树有左右之分,并且次序不能任意颠倒。...

静默加载 ⋅ 2017/10/19 ⋅ 0

数据结构与算法——常用数据结构及其Java实现

前言 仿佛一下子,2017年就快过去一半了,研一马上就要成为过去式了,我打算抓住研一的尾巴,好好梳理一下数据结构与算法,毕竟这些基础知识是很重要的嘛。所以准备在这里搞一个系列的文章,...

MageekChiu ⋅ 2017/06/17 ⋅ 0

数据结构(二)——树结构模型及应用

基于树实现的数据结构,具有两个核心特征: 逻辑结构:数据元素之间具有层次关系; 数据运算:操作方法具有Log级的平均时间复杂度。 因此,树在文件系统、编译器、索引以及查找算法中有很广的...

yhthu ⋅ 2017/11/11 ⋅ 0

平衡二叉树(AVL)树

1、平衡二叉树定义 是一种二叉排序树(二叉查找树、二叉搜索树),其中每个节点的左子树和右子树的高度差不大于1。(左右子树也是平衡二叉树) 平衡因子BF = 二叉树节点的左子树深度减去右子...

笨拙的小Q ⋅ 2016/07/02 ⋅ 0

Java集合--TreeMap完全解析

4 TreeMap 上一篇,介绍了集合框架中的HashMap对象,主要讲述了HashMap的底层实现和基本操作。本篇,让我们继续来学习Map集合,今天的主角是TreeMap。 相比于HashMap来说,TreeMap理解起来更...

贾博岩 ⋅ 2017/09/10 ⋅ 0

平衡二叉树学习

二叉树:每个节点最多有2个子树,分为左右子树,且次序不能颠倒。树的第i层最多有2^(i-1)个节点。 2. 二叉排序数(BST):又称二叉查找树。性质如下: 若左子树不为空,那么左子树上所有节点...

yizhangxyz ⋅ 2016/07/06 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

linux 安装docker

通过以下命令下载安装docker wget -qO- https://get.docker.com | sh 执行以上命令后输出以下内容说明安装成功,注意红框中的内容,docker安装成功后默认只有root能使用,红框中给出的提示是...

haoyuehong ⋅ 23分钟前 ⋅ 0

482. License Key Formatting - LeetCode

Question 482. License Key Formatting Solution 思路:字符串转化为char数组,从后遍历,如果是大写字母就转化为小写字母,如果是-就忽略,如果遍历了k个字符(排除-)就追加一个-。 Java实现...

yysue ⋅ 41分钟前 ⋅ 0

聊聊spring cloud gateway的LoadBalancerClientFilter

序 本文主要研究一下spring cloud gateway的LoadBalancerClientFilter GatewayLoadBalancerClientAutoConfiguration spring-cloud-gateway-core-2.0.0.RELEASE-sources.jar!/org/springfram......

go4it ⋅ 今天 ⋅ 0

详解:Nginx反代实现Kibana登录认证功能

Kibana 5.5 版后,已不支持认证功能,也就是说,直接打开页面就能管理,想想都不安全,不过官方提供了 X-Pack 认证,但有时间限制。毕竟X-Pack是商业版。 下面我将操作如何使用Nginx反向代理...

问题终结者 ⋅ 今天 ⋅ 0

002、nginx配置虚拟主机

一、nginx配置虚拟主机可分为三种方式,分别为: 1、基于域名的虚拟主机,通过域名来区分虚拟主机——应用:外部网站 2、基于端口的虚拟主机,通过端口来区分虚拟主机——应用:公司内部网站...

北岩 ⋅ 今天 ⋅ 0

shell脚本之死循环写法

最近在学习写shell脚本,在练习if while等流程控制时,突然它们的死循环写法是怎么样的?经过百度与亲测记录如下: for死循环 #! /bin/bashfor ((;;));do date sleep 1d...

hensemlee ⋅ 今天 ⋅ 0

苹果的ARKit2.0有多可怕,看了就知道

序言 ARKit主要由三部分组成: 跟踪(Tracking) 跟踪是ARKit的核心组件之一,其提供了设备在物理世界中的位置与方向信息,并对物体进行跟踪,如人脸。 2.场景理解(Scene Understanding) 场...

_小迷糊 ⋅ 今天 ⋅ 0

5.1 vim介绍 5.2 vim移动光标 5.3 ,5.4vim一般模式下移动光标,复制粘贴

vim命令 vim是vi的一个升级版;vim可以显示文字的颜色 安装vim这一个包vim-enhanced 如果不知道安装包,可以使用 命令下面命令来查看vim命令是那个包安装的。 [root@linux-128 ~]# yum prov...

Linux_老吴 ⋅ 今天 ⋅ 0

vim一般模式

vim 是什么 vim是什么 ? 在之前接触Linux,编辑网卡配置文件的时候我们用过了vi ,vim简单说就是vi的升级版,它跟vi一样是Linux系统中的一个文本编辑工具。 如果系统中没有vim ,需要安装一...

李超小牛子 ⋅ 今天 ⋅ 0

docker实战

构建企业级Docker虚拟化平台实战 重点剖析虚拟化和云计算概念; 分析Docker虚拟化的概念和原理; 从0开始实战Docker虚拟化平台; 基于Docker构建Nginx WEB服务器和CentOS虚拟机; 基于开源监...

寰宇01 ⋅ 今天 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部