今晚整那个ubuntu,什么也没弄成,唉,把算法先保留一下吧, 插入函数还没理解透彻呢
#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define NULL 0
typedef int Status;
typedef int ElemType;
typedef int KeyType;
typedef struct BSTNode{
ElemType data;
int bf; //结点平衡因子
BSTNode *lchild, *rchild; //左右孩子指针
}BSTNode, *BSTree;
Status InitBSTree(BSTree &BT) //初始化
{//操作结果:构造一个空的动态查找表BT
BT=NULL;
return OK;
}//InitBSTree
Status DestroyBSTree(BSTree &BT) //销毁
{//初始条件:动态表已经存在。操作结果:销毁动态查找表BT
if(BT) //非空树
{
if(BT->lchild) //有左孩子
DestroyBSTree(BT->lchild); //递归法销毁左孩子子树
if(BT->rchild) //有右孩子
DestroyBSTree(BT->rchild); //递归法消去右孩子子树
free(BT); //释放根结点
BT=NULL;
}//if
return OK;
}//DestroyBSTree
BSTree SearchBSTree(BSTree T, KeyType key) //查找
{//在根指针T所指平衡二叉树中递归地查找某关键字等于key的数据元素
//若查找成功,则返回指向该数据元素结点的指针,否则返回空指针。
if(!T)
{
if(key == T->data)
return T; //查找结束;
else if(key < T->data)
return SearchBSTree(T->lchild, key); //在左子树中查找
else if(key > T->data)
return SearchBSTree(T->rchild, key); //在右子树中查找
}//if
}//SearchBSTree
Status R_Rotate(BSTree &p) //右旋
{//对以*p为根的二叉树作右旋处理,处理之后p指向新的树根结点,
//即指向处理前的左子树的根结点(p的左孩子结点)
BSTree lc;
lc=p->lchild; //lc指向左子树的根结点
p->lchild = lc->rchild; //lc的右子树挂接为p的左子树
lc->rchild =p;
p=lc; //p指向新的根结点
return OK;
}//R_Rotate
Status L_Rotate(BSTree &p) //左旋
{
BSTree rc;
rc=p->rchild;
p->rchild = rc->lchild;
rc->lchild=p;
p=rc;
return OK;
}//L_Rotate
#define LH +1 //左高
#define EH 0 //等高
#define RH -1 //右高
Status LeftBalance(BSTree &T) //左平衡旋转处理
{//对以指针T所指结点为根的二叉树作左平衡处理,
//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;
}//switch
rd->bf=EH;
L_Rotate(T->lchild);//对*T的左子树做左旋平衡处理
R_Rotate(T); //对*T做右旋处理
}//switch
return OK;
}//LeftBalance
Status RightBalance(BSTree &T) //右平衡旋转处理
{//对以T所指向的结点为根二叉树做右平衡处理,
//T指向新的根结点
BSTree rc, rd;
rc=T->rchild; //rc指向T的右子树根结点
switch(rc->bf)
{//检查*T的右子树的平衡度,并作相应平衡处理
case RH: //新结点插入在右子树右子树上,单向左旋
T->bf=rc->bf=EH;
L_Rotate(T);
break;
case LH: //新结点插入在右子树的左子树上,双选处理
rd=rc->lchild;//rd指向右子树的座子树根
switch(rd->bf)
{//修改*T及其右孩子的平衡因子
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;
}//switch
rd->bf=EH;
R_Rotate(T->rchild);//右子树右旋
L_Rotate(T); //对*T作左旋平衡处理
}//switch
return OK;
}//RightBalance
Status InsertElem(BSTree &T, ElemType e, Status &taller)
{//若不存在e则插入,返回1;否则返回0;若插入后失衡,则作相应平衡处理
//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(e == T->data)
{//存在相同结点,则不插入
taller=FALSE;
return FALSE;
}//if
if(e < T->data)
{//应继续在T的左子树中搜索
if(!InsertElem(T->lchild, e, taller))//未插入
return FALSE;
if(taller) //已插入,且左子树长高
{
switch(T->bf)//检查*T的平衡度
{
case LH://原本左高,需左平衡处理
LeftBalance(T);
taller=FALSE;
break;
case EH: //原本等高,左增高则树增高
T->bf=LH;
taller=TRUE;
break;
case RH: //原本右高,则左右等高
taller=FALSE;
}//switch
}//if
else
{//应在T的右子树中搜索
if(!InsertElem(T->rchild, e, taller))//未插入
return FALSE;
if(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;
}
}
}
}
}
return OK;
}
分享到:
相关推荐
数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 数据结构、算法相关的资源 ...
通俗易懂,由艾孜尔江·艾尔斯兰亲自实验并撰著而成,均为底层开发,可供研究和学习使用,平时工作中亦可实践,是初学者深入学习数据结构与算法的法宝,基于C++语言实现,涉及到C语言的内容较多,内含指导教程和详细...
为了研究更好的三角网构建的方法,对不规则三角网构建算法进行了研究,提出了一种基于平衡二叉树的Delaunay三角网生成算法,采用分割合并的思想,提高了搜索效率,将离散点集进行划分,通过对各个所分小块子网的合并...
本文本是广东工业大学数据结构课设平衡二叉树的演示的报告,最后的等级是优秀。文本里面对于选做提高的部分内容都采用了两种方法实现。文档里面有些过程的演示由于涉及到个人信息我删除了,你们可以下载下来后可以...
提出了一种基于平衡二叉树的Delaunay三角网生成算法。采用分割合并的思想,将离散点集进行划分,通过对各个所分小块子网的合并,完成三角网的构建。同时,分析了该算法涉及的相邻子网公切线查找、凸壳生成,分层等关键...
5.7 在二叉树中计算平衡因子 5.8 寻找最大连续子序列 5.9 增强归纳假设 5.10 动态规划:背包问题 5.11 常见的错误 5.12 小结 第6章 序列和集合的算法 6.1 引言 6.2 二叉搜索的几种形式 6.2.1 纯二叉搜索 ...
本课程涉及的数据结构与算法有,栈,队列,单向链表,双向循环链表,树,二叉树,搜索二叉树,平衡搜索二叉树,冒泡,选择,直插,希尔,,归并等,课程还涉及深度优先算法与广度优先算法等等。
3.2.1 本章所涉及的结构体定义 56 3.2.2 顺序栈 57 3.2.3 链栈 59 3.2.4 栈的应用 60 3.2.5 顺序队 64 3.2.6 链队 66 3.3 抽象数据类型 69 ▲真题仿造 71 真题仿造答案与讲解 71 习题 真题精选 74 习题答案 真题精选...
涉及如何构建平衡二叉树,是C语言源代码,最流行的算法
数据结构是计算机科学中的一门重要课程,它主要研究数据的组织、存储和管理方式。合理的数据结构选择对于算法的实现和程序的性能至关重要。...树形结构如二叉树、平衡树、堆等;图形结构则涉及图、网络等复杂数据结构。
主要涉及音视频和图像算法。 欢迎关注头条号火车上遇见 简单数据结构和算法( ) referencegeeksforgeeks.org网站编写 大批 链表 堆 队列 二叉树 二进制搜索树 堆 散列 图形 矩阵 杂项 先进的数据结构 ...
4.1.4 平衡二叉树 4.1.5 算法细节 4.1.6 成本分析 4.2 多对多广播和归约 4.2.1 线性阵列和环 4.2.2 格网 4.2.3 超立方体 4.2.4 成本分析 4.3 全归约与前缀和操作 4.4 散发和收集 4.5 多对多私自通信 ...
15.1.3 满二叉树、完全二叉树和平衡二叉树 421 15.1.4 二叉树的最大和最小高度 422 15.2 ADT二叉树 425 15.2.1 二叉树的遍历 425 15.2.2 二叉树的操作 428 15.2.3 ADT二叉树的模板接口 430 15.3 ADT二叉查找...
Java服务器端开发面试题篇3 数据结构,线性列表,二叉树,完全二叉平衡树,B+树,图的表示。 树的先序,中序,后序,层序遍历。能手写代码,递归和循环实现。 栈的使用 排序 常用的排序算法, 选择,冒泡,快排,堆...
答: 左右子树都是平衡二叉树 且左右子树的深度差值的绝对值不大于1。 17、堆栈溢出一般是由什么原因导致的? 答: 没有回收垃圾资源。 18、什么是预编译?何时需要预编译? 答: (1)总是使用不经常改动的大型代码...