平衡二叉树操作的演示
#include
#include
typedef int KeyType; //定义关键字类型
typedef struct node //记录类型
{KeyType key; //关键字项
int bf; //平衡因子
struct node *lchild,*rchild; //左右孩子指针
}BSTNode;
void LeftProcess(BSTNode *&p,int &taller)
{//对以指针p所指结点为根的二叉树作左平衡旋转处理，本算法结束时，
//指针p指向新的根结点
BSTNode *p1,*p2;
if(p->bf==0) //原本左右子树等高，现因左子树增高而使树增高{p->bf=1;
taller=1;
}
else if(p->bf==-1) //原本右子树比左子树高，现左右子树等高
{p->bf=0;
taller=0;
}
else //原本左子树比右子树高，须作左子树的平衡处理
{p1=p->lchild; //p指向*p的左子树根节点
if(p1->bf==1) //新结点插入在*p的左孩子的左子树上，要做LL 调整
{p->lchild=p1->rchild;
p1->rchild=p;
p->bf=p1->bf=0;
p=p1;
}
else if(p1->bf==-1) //新结点插入在*p的左孩子的右子树上，要做LR调整
{p2=p1->rchild;
p1->rchild=p2->lchild;
p2->lchild=p1;
p->lchild=p2->rchild;
p2->rchild=p;
if(p2->bf==0) //新结点插入在*p2处作为叶子结点的情况p->bf=p1->bf=0;
else if(p2->bf==1) //新结点插在*p2的左子树上的情况
{p1->bf=0;
p->bf=-1;
}
else //新结点插在*p2的右子树上的情况
{p1->bf=1;
p->bf=0;
}
p=p2;
p->bf=0; //仍将p指向新的根结点，并置其bf值为0
}
taller=0;
}
}
void RightProcess(BSTNode *&p,int &taller)
{//对以指针p所指结点为根的二叉树作右平衡旋转处理，本算法结束时，
//指针p指向新的根结点
BSTNode *p1,*p2;
if(p->bf==0) //原本左右子树等高，现因右子树增高而使树增高{p->bf=-1;
taller=1;
}
else if(p->bf==1) //原本左子树比右子树高，现左右子树等高
{p->bf=0;
taller=0;
}
else //原本右子树比左子树高，须作右子树的平衡处理
{p1=p->rchild; //p指向*p的右子树根结点
if(p1->bf==-1) //新结点插入在*p的右孩子的左子树上，要做RR 调整
{p->rchild=p1->lchild;
p1->lchild=p;
p->bf=p1->bf=0;
p=p1;
}
else if(p1->bf==1) //新结点插入在*p的右孩子的左子树上，要做RL 调整
{p2=p1->lchild;
p1->lchild=p2->rchild;
p2->rchild=p1;
p->rchild=p2->lchild;
p2->lchild=p;
if(p2->bf==0) //新结点插在*p2处作为叶子结点的情况p->bf=p1->bf=0;
else if(p2->bf==-1) //新结点插在*p2的右子树上的情况
{p1->bf=0;
p->bf=1;
}
else //新结点插在*p2的左子树上的情况
{p1->bf=-1;
p->bf=0;
}
p=p2;
p->bf=0; //仍将p指向新的结点，并置其bf值为0
}
taller=0;
}
}
int InsertA VL(BSTNode*&b,KeyType e,int &taller)
{//若在平衡二叉排序树b中不存在和e有相同关键字的结点，则插入一个数据元素为e的新结点，
//并返回1，否则返回0。若因插入而使二叉排序树失去平衡，则作平衡旋转处理，布尔变量taller
//反映b长高与否
if(b==NULL) //原树为空，插入新结点，树长高，置taller为1 {b=(BSTNode*)malloc(sizeof(BSTNode));
b->key=e;
b->lchild=b->rchild=NULL;
b->bf=0;
taller=1;
}
else
{if(e==b->key) //树中已存在和e有相同关键字的结点则不插入{taller=0;
return 0;
}
if(e
{if((InsertA VL(b->lchild,e,taller))==0) //未插入
return 0;
if(taller==1) //已插入到*b的左子树中且左子树长高LeftProcess(b,taller);
}
else //继续在*b的右子树中进行搜索
{if((InsertA VL(b->rchild,e,taller))==0) //未插入
return 0;
if(taller==1) //已插入到*b的右子树中且右子树长高RightProcess(b,taller);
}
}
return 1;
}
void DispBSTree(BSTNode *b)
{//以括号表示法输出A VL
if(b!=NULL)
{printf("%d",b->key);
if(b->lchild!=NULL||b->rchild!=NULL)
{printf("(");
DispBSTree(b->lchild);
if(b->rchild!=NULL)printf(",");
DispBSTree(b->rchild);
printf(")");
}
}
}
void LeftProcess1(BSTNode*&p,int&taller) //在删除结点时进行左处理{BSTNode *p1,*p2;
if(p->bf==1)
{p->bf=0;
taller=1;
}
else if(p->bf==0)
{p->bf=-1;
taller=0;
}
else
{p1=p->rchild;
if(p1->bf==0) //须作RR调整
{p->rchild=p1->lchild;
p1->lchild=p;
p->bf=1;
p1->bf=-1;
p=p1;
taller=0;
}
else if(p1->bf==-1) //须作RR调整
{p->rchild=p1->lchild;
p1->lchild=p;
p1->bf=p->bf=0;
p=p1;
taller=1;
}
else //须作RL调整
{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)
{p1->bf=1;
p->bf=0;
}
else
{p1->bf=0;
p->bf=-1;
}
p2->bf=0;
p=p2;
taller=1;
}
}
}
void RightProcess1(BSTNode*&p,int&taller) //在删除结点是进行右处理{BSTNode *p1,*p2;
if(p->bf==-1)
{p->bf=0;
taller=1;
}
else if(p->bf==0)
{p->bf=1;
taller=0;
}
else
{p1=p->lchild;
if(p1->bf==0) //须作LL调整
{p->lchild=p1->rchild;
p1->rchild=p;
p->bf=-1;
p1->bf=1;
p=p1;
taller=0;
}
else if(p1->bf==1) //须作LL调整
{p->lchild=p1->rchild;
p1->rchild=p;
p1->bf=p->bf=0;
p=p1;
taller=1;
}
else //须作LR调整{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)
{p1->bf=-1;
p->bf=0;
}
else
{p1->bf=0;
p->bf=1;
}
p2->bf=0;
p=p2;
taller=1;
}
}
}
void Delete(BSTNode*q,BSTNode*&r,int &taller)
{//由DeleteA VL调用，用于处理被删结点左右子树均不空的情况if(r->rchild==NULL)
{q->key=r->key;
q=r;
r=r->lchild;
free(q);
taller=1;
}
else
{Delete(q,r->rchild,taller);
if(taller==1)
RightProcess1(r,taller);
}
}
int DeleteA VL(BSTNode *&p,KeyType x,int &taller)
{//在A VL树中删除关键字为x的结点
int k;
BSTNode *q;
if(p==NULL)
return 0;
else if(x
{k=DeleteA VL(p->lchild,x,taller);
if(taller==1)
LeftProcess1(p,taller);
return k;
}
else if(x>p->key)
{k=DeleteA VL(p->rchild,x,taller);
if(taller==1)
RightProcess1(p,taller);
return k;
}
else //找到了关键字为x的结点，由p指向它{q=p;
if(p->rchild==NULL) //被删结点右子树为空
{p=p->lchild;
free(q);
taller=1;
}
else if(p->lchild==NULL) //被删结点左子树为空
{p=p->rchild;
free(q);
taller=1;
}
else //被删结点左右子树均不为空
{Delete(q,q->lchild,taller);
if(taller==1)
LeftProcess1(q,taller);
p=q;
}
return 1;
}
}
void main()
{BSTNode *b=NULL;
int i,j,k;
KeyType a[]={4,9,0,1,8,6,3,5,2,7},n=10; printf("创建一棵A VL树:\n");
for(i=0;i {printf("第%d步，插入%d元素:",i+1,a[i]); InsertA VL(b,a[i],j); DispBSTree(b); printf("\n"); } printf("A VL:"); DispBSTree(b); printf("\n"); printf("删除结点:\n"); k=8; printf("删除结点%d:",k); DeleteA VL(b,k,j); printf("A VL:"); DispBSTree(b); printf("\n"); k=2; printf("删除结点%d:",k); DeleteA VL(b,k,j); printf("A VL:"); DispBSTree(b); printf("\n\n"); } 平衡二叉树操作的演示 1.需求分析 本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。具体功能： （1）初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更 新平衡二叉树的显示。 （2）平衡二叉树的显示采用凹入表现形式。 （3）合并两棵平衡二叉树。 （4）把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。 如下图： 2．概要设计 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。 具体步骤： （1）每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点； （2）若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； （3）判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；（4）如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；（5）计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。 流程图 3.详细设计 二叉树类型定义： typedef int Status; typedef int ElemType; typedef struct BSTNode{ 二叉排序树变成平衡二叉树 对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。 平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1 一棵好的平衡二叉树的特征： （1）保证有n个结点的树的高度为O(logn) （2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1) 一、平衡二叉树的构造 在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树 1.调整方法 （1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点 （2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。 2.调整方式 （1）LL型 LL型：插入位置为左子树的左结点，进行向右旋转(LL表示的是在做子树的左结点进行插入) 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。 （2）RR型 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学号： 班级： 指导老师： 报告日期： 1.需求分析 1．建立平衡二叉树并进行创建、查找、插入、删除等功能。 2．设计一个实现平衡二叉树的程序，可进行创建、查找、插入、删除等操作，实现动态的输入数据，实时的输出该树结构。 3．测试数据：自选数据 2.概要设计 1.抽象数据类型定义： typedef struct BSTNode { int data; int bf; //节点的平衡因子 struct BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; void CreatBST(BSTree &T); //创建平衡二叉树 void R_Rotate(BSTree &p); //对以*p为根的二叉排序树作左旋处理 void L_Rotate(BSTree &p); //对以*p为根的二叉排序树作左旋处理 void LeftBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理bool InsertAVL(BSTree &T,int e,bool &taller); //插入结点e bool SearchBST(BSTree &T,int key); //查找元素key是否在树T中 void LeftBalance_div(BSTree &p,int &shorter); //删除结点时左平衡旋转处理 void RightBalance_div(BSTree &p,int &shorter); //删除结点时右平衡旋转处理 void Delete(BSTree q,BSTree &r,int &shorter); //删除结点 int DeleteA VL(BSTree &p,int x,int &shorter); //平衡二叉树的删除操作 void PrintBST(BSTree T,int m); //按树状打印输出二叉树的元素 2.主程序的流程 3.各模块之间的层次调用 二叉树的各种算法.txt男人的承诺就像80岁老太太的牙齿，很少有真的。你嗜烟成性的时候，只有三种人会高兴，医生你的仇人和卖香烟的。 /*用函数实现如下二叉排序树算法： （1）插入新结点 （2）前序、中序、后序遍历二叉树 （3）中序遍历的非递归算法 （4）层次遍历二叉树 （5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6）交换各结点的左右子树 （7）求二叉树的深度 （8）叶子结点数 Input 第一行：准备建树的结点个数n 第二行：输入n个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字 Output 第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列 第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 第十行：插入新结点后的二叉树的层次遍历序列 第十一行~第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列 第十四行~第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列 第十七行：二叉树的深度 第十八行：叶子结点数 */ #include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int KeyType; #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 #define MAXQSIZE 100 typedef int ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) { if(!T){p=f;return FALSE;} else if(key==T->data){p=T;return TRUE;} else if(key 实验6 实验目的： 1、掌握二叉树的所有算法 2、熟悉计算机英语和术语 实验步骤： 1、二叉树算法的模拟 2、完型填空 3、翻译 具体要求： 一、设计一个完整的程序，实现二叉树的各种算法 要求：/*用函数实现如下二叉排序树算法： （1）插入新结点 （2）前序、中序、后序遍历二叉树 （3）中序遍历的非递归算法 （4）层次遍历二叉树 （5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6）交换各结点的左右子树 （7）求二叉树的深度 （8）叶子结点数 输入： 第一行：准备建树的结点个数n 第二行：输入n个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字 输出： 第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列第九行：插入新结点后的二叉树的中序遍历序列(非递归算法) 代码： #include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int KeyType; #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 #define MAXQSIZE 100 typedef int ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;//左右孩子指针 } BiTNode,*BiTree; Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) { if(!T){p=f;return FALSE;} else if(key==T->data){p=T;return TRUE;} else if(key 平衡二叉树（AVL）查找、插入和删除 小组成员： 陈静101070009 陈丹璐101070006 陈娇101070008 目录 平衡二叉树（AVL） (1) 查找、插入和删除 (1) 问题描述 (2) 设计说明 (3) （一）ADT (3) （二）算法思想 (5) （三）数据结构 (12) （四）程序结构与流程 (13) 运行平台及开发工具 (15) I/O格式 (15) 算法复杂度分析 (18) 源代码 (18) 小结 (37) 问题描述 利用平衡二叉树实现一个动态查找表。 （1）实现动态查找表的三种基本功能：查找、插入和删除。 （2）初始时，平衡二叉树为空树，操作界面给出创建、查找、插入和删除和退出五种操作供选择。每种操作均要提示输入关键字。创建时，根据提示输入数据，以-1为输入数据的结束标志，若输入数据重复，则给出已存在相同关键字的提示，并不将其插入到二叉树中。在查找时，如果查找的关键字不存在，则显示不存在查找的关键字，若存在则显示存在要查找的关键字。插入时首先检验原二叉树中是否已存在相同第3 页共38 页- 3 -的关键字，若没有则进行插入并输出二叉树，若有则给出已有相同关键字的提醒。删除时首先检验原二叉树中是否存在要删除的关键字，若有则进行删除后并输出二叉树，若没有则给出不存在要删除的关键字的提醒。 （3）平衡二叉树的显示采用中序遍历的方法输出，还可以根据输出数据是否有序验证对平衡二叉树的操作是否正确。 设计说明 （一）ADT ADT BalancedBinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： void R_Rotate(BSTree &p); 初始条件：二叉树存在，且关键字插入到以*p为根的二叉树的左子树的左孩子上； 操作结果：对以*p为根的二叉排序树作右旋处理 数据结构实习报告 题目：平衡二叉树的操作演示 班级：信息管理与信息系统11-1 ：佳 学号：3 完成日期：2013.06.25 一、需求分析 1. 初始，平衡二叉树为空树，操作界面给出两棵平衡二叉树的显示、查找、插入、删除、销毁、合并两棵树，几种选择。其中查找、插入和删除操作均要提示用户输入关键字。每次插入或删除一个节点后都会更新平衡二叉树的显示。 2. 平衡二叉树的显示采用凹入表形式。 3.每次操作完毕后都会给出相应的操作结果，并进入下一次操作，知道用户选择退出 二、概要设计 1.平衡二叉树的抽象数据类型定义： ADT BalancedBinaryTree{ 数据对象D：D是具有相同特性的数据元素的集合。各个数据元素均含有类型相同，可唯一标志的数据元素的关键字。 数据关系R：数据元素同属一个集合。 基本操作P： InitAVL(BSTree& T) 操作结果：构造一个空的平衡二叉树T DestroyAVL(BSTree& T) 初始条件：平衡二叉树T存在 操作结果：销毁平衡二叉树T SearchAVL(BSTree T,int key) 初始条件：平衡二叉树T存在，key为和关键字相同类型的给定值 操作结果：若T中存在关键字和key相等的数据元素，则返回指向该元素的 指针，否则为空 InsertAVL(BSTree& T,int key,Status& taller) 初始条件：平衡二叉树T存在，key和关键字的类型相同 操作结果：若T中存在关键字等于key的数据元素则返回，若不存在则插入 一个关键字为key的元素 DeleteAVL(BSTree& T,int &key,Status& lower) 初始条件：平衡二叉树T存在，key和关键字的类型相同 操作结果：若T中存在关键字和key相同的数据元素则删除它}ADT BalancedBinaryTree 实验报告 课程名称：数据结构实验课程 实验四、串的基本操作练习 一、实验目的 1. 掌握二叉树的存储实现 2. 掌握二叉树的遍历思想 3. 掌握二叉树的常见算法的程序实现 二、实验环境 VC++6.0 三、实验内容 1.输入字符序列，建立二叉树的二叉链表结构。（可以采用先序序列） 2.实现二叉树的先序、中序、后序的递归遍历算法。 3.实现二叉树的先序、中序、后序的非递归遍历算法。 4.求二叉树的高度。 5.求二叉树的结点个数。 6.求二叉树的叶子结点的个数。 四、实验要求： 分别编写实现上述算法的子函数，并编写一个主函数，在主函数中设计一个简单的菜单，分别调用上述子函数。 五、实验步骤和结果 1.打开vc，新建文本，命名二叉树算法，编写代码。 2.编写代码： #include BiTNode *base; BiTNode *top; int stacksize; } SqStack;//栈类型 void InitStack(SqStack *S)//创建二叉树 { S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode)); S->top=S->base; S->stacksize=STACK_INIT_SIZE; } void Push(SqStack *S,BiTNode e)//进栈 { if(S->top - S->base >= S->stacksize)//如果栈空间不足 { S->base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(B iTNode)); S->top=S->base+S->stacksize; S->stacksize+=STACKINCREMENT; } *(S->top)=e; S->top++; } BiTNode Pop(SqStack *S)//出栈 { S->top --; return *S->top; } int StackEmpty(SqStack *S)//判断栈是否非空 { if(S->top == S->base ) return 1; else return 0; } /*---------------------------------------------递归部分-------------------------------------------*/ 平衡二叉树构造方法 平衡二叉树 对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为O(logn)，但是它们的最差运行时间都是O(n),原因在于对树的形状没有限制。 平衡二叉树又称为AVL树，它或者是一棵空树，或者是有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左右子树的深度之差的绝对值不超过1。二叉树的的平衡因子BF为：该结点的左子树的深度减去它的右子树的深度，则平衡二叉树的所有结点的平衡因子为只可能是：-1、0和1 一棵好的平衡二叉树的特征： （1）保证有n个结点的树的高度为O(logn) （2）容易维护，也就是说，在做数据项的插入或删除操作时，为平衡树所做的一些辅助操作时间开销为O(1) 一、平衡二叉树的构造 在一棵二叉查找树中插入结点后，调整其为平衡二叉树。若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树 1.调整方法 （1）插入点位置必须满足二叉查找树的性质，即任意一棵子树的左结点都小于根结点，右结点大于根结点 （2）找出插入结点后不平衡的最小二叉树进行调整，如果是整个树不平衡，才进行整个树的调整。 2.调整方式 （1）LL型 LL型：插入位置为左子树的左结点，进行向右旋转 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1变为2，成为不平衡的最小二叉树根结点。此时A结点顺时针右旋转，旋转过程中遵循“旋转优先”的规则，A结点替换D结点成为B结点的右子树，D结点成为A结点的左孩子。 （2）RR型 RR型：插入位置为右子树的右孩子，进行向左旋转 由于在A的右子树C的右子树插入了结点F，A的平衡因子由-1变为-2，成为不平衡的最小二叉树根结点。此时，A结点逆时针左旋转，遵循“旋转优先”的规则，A结点替换D结点成为C的左子树，D结点成为A的右子树。 （3）LR型 LR型：插入位置为左子树的右孩子，要进行两次旋转，先左旋转，再右旋转；第一次最小不平衡子树的根结点先不动，调整插入结点所在的子树，第二次再调整最小不平衡子树。 由于在A的左子树B的右子树上插入了结点F，A的平衡因子由1变为了2，成为不平衡的最小二叉树根结点。第一次旋转A结点不动，先将B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。 （4）RL型 RL型：插入位置为右子树的左孩子，进行两次调整，先右旋转再左旋转；处理情况与LR 类似。 数据结构程序报告(平衡二叉树的操作) 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学号： 班级： 指导老师： 报告日期： 1.需求分析 1．建立平衡二叉树并进行创建、查找、插入、删除等功能。 2．设计一个实现平衡二叉树的程序，可进行创建、查找、插入、删除等操作，实现动态的输入数据，实时的输出该树结构。 3．测试数据：自选数据 2.概要设计 1.抽象数据类型定义： typedef struct BSTNode { int data; int bf; //节点的平衡因子 struct BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; void CreatBST(BSTree &T); //创建平衡二叉树 void R_Rotate(BSTree &p); //对以*p 为根的二叉排序树作左旋处理 void L_Rotate(BSTree &p); //对以*p 为根的二叉排序树作左旋处理 void LeftBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作左平衡旋转处理void RightBalance(BSTree &T); //对以指针Ｔ所指结点为根的二叉树作右平衡旋转处理bool InsertA VL(BSTree &T,int e,bool &taller); //插入结点e bool SearchBST(BSTree &T,int key); //查找元素key是否在树T中 void LeftBalance_div(BSTree &p,int &shorter); void RightBalance_div(BSTree &p,int &shorter); 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期2014-12-18 一.实验目的和要求 1、掌握二叉树的链式存储结构。 2、掌握在二叉链表上的二叉树操作的实现原理与方法。 3、进一步掌握递归算法的设计方法。 二.实验内容 1、按照下面二叉树二叉链表的存储表示，编写头文件binary_tree.h，实现二叉链表的定义与基本操作实现函数；编写主函数文件test4_1.cpp，验证头文件中各个操作。 二叉树二叉链表存储表示如下： struct BTreeNode { ElemType data; // 结点值域 BTreeNode *lchild , *rchild ; // 定义左右孩子指针 } ; 基本操作如下： ①void InitBTree( BTreeNode *&BT ); //初始化二叉树BT ②void CreateBTree( BTreeNode *&BT, char *a ); //根据字符串a所给出的广义表表示的二叉树建立二叉链表存储结构 ③int EmptyBTree( BTreeNode *BT); //检查二叉树BT是否为空，空返回1，否则返回0 ④int DepthBTree( BTreeNode *BT); //求二叉树BT的深度并返回该值 ⑤int FindBTree( BTreeNode *BT, ElemType x); //查找二叉树BT中值为x的结点，若查找成功返回1，否则返回0 ⑥void PreOrder( BTreeNode *BT); //先序遍历二叉树BT ⑦void InOrder( BTreeNode *BT); //中序遍历二叉树BT ⑧void PostOrder( BTreeNode *BT); //后序遍历二叉树BT 实现平衡二叉排序树的各种算法代码一 /* 《实现平衡二叉排序树的各种算法》 一、分析题目要求 用函数实现如下平衡二叉排序树算法,: （1）插入新结点 （2）前序、中序、后序遍历二叉树（递归） （3）前序、中序、后序遍历的非递归算法 （4）层次遍历二叉树 （5）在二叉树中查找给定关键字(函数返回值为成功1,失败0) （6）交换各结点的左右子树 （7）求二叉树的深度 （8）叶子结点数 （9）删除某结点 为了完成以上的各项操作，首先应该用函数建一棵平衡二叉排序树，输入形式是首先输入要建的二叉树的结点数，然后依次输入各个结点的值。在实现插入新结点的函数时，需要一个向一棵二叉树插入新结点的函数。可用递归算法写出平衡二叉树的前序，中序，后序遍历的函数。在写平衡二叉树的前，中，后序遍历的非递归算法时要用到栈结构的知识，运用栈结构来存储平衡二叉树结点的指针。在层次遍历二叉树时需要用到队列结构，运用队列结构的先进先出来存储二叉树的结点指针。在遍历二叉树的结点时需要一个访问结点数据的函数。二叉树是一棵排序树，所以二叉树的查找可以运用其有序的性质，查找的方式和建树的方式相似。交换二叉树各结点的左右子树时，可以用先序遍历递归的方式从根结点向下递归，每次访问结点时就需将各结点的左右孩子的指针调换，并对该结点的平衡因子作相应的处理。示二叉树的深度时，可用递归的方式访问结点的左右子树，并记录下左右子树的深度，最后返回左右子树中较深的深度的值即可。可以用一次遍历的方式遍历二叉树，记录每一个经过的结点，若结点存在且左右孩子都为空，则该结点为叶子结点。删除二叉树的某个结点时，首先要写一个函数，用递归查找的方式找到相应的结点，该函数还要有调整二叉树平衡的作用，因为若删除结点使得二叉树深度减少而不平衡，需要调整二叉树的平衡，若该结点不存在则返回ERROR,，若存在该结点，则应该再写一个函数来删除该结点，在删除之前还要判断该结点是只有左子树还是只有右子树还是左右子树都有的情况：若只有左或是只有右子树，则只需删除该结点，并回溯调整二叉树的平衡；若该结点的左右子树都有，则应该用另一个函数递归找到该结点的直接“后继”，并从该“后继”开始回溯调整二叉树的平衡。 */ #include<stdio.h> #include<stdlib.h> #include<malloc.h> #define OK 1 #define ERROR 0 二叉树： 左子树都小于根节点，右子树都大于根节点。可以动态维护这棵树（因为是树结构，可以有限步完成插入），所以是动态查找算法。时间复杂度为O(logn)在46.5%的情况下，需要把二叉树平衡化成“平衡二叉树”。 平衡二叉树：定义：平衡二叉树或为空树,或为如下性质的二叉排序树: （1）左右子树深度之差的绝对值不超过1; （2）左右子树仍然为平衡二叉树. 平衡因子：平衡因子bf=左子树深度－右子树深度, 每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。增加一个元素后，平衡二叉树有可能变成不平衡了，所以需要旋转平衡调整。 平衡二叉树算法思想： 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况：（可以断定插入一个节点一定是在叶子节点上） （1）LL型平衡旋转法 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B 的右子树的根结点。而原来B的右子树则变成A的左子树。 （2）RR型平衡旋转法 由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C 的左子树的根结点。而原来C的左子树则变成A的右子树。 二叉树的各种算法.txt 男人的承诺就像80 岁老太太的牙齿，很少有真的。你嗜烟成性的时候，只有三种人会高兴，医生你的仇人和卖香烟的。 /* 用函数实现如下二叉排序树算法： （ 1 ）插入新结点 （ 2 ）前序、中序、后序遍历二叉树 （3）中序遍历的非递归算法 （4）层次遍历二叉树 （5）在二叉树中查找给定关键字（函数返回值为成功1, 失败0） （6）交换各结点的左右子树 （7）求二叉树的深度 （8）叶子结点数 Input 第一行：准备建树的结点个数n 第二行：输入n 个整数，用空格分隔 第三行：输入待查找的关键字 第四行：输入待查找的关键字 第五行：输入待插入的关键字 Output 第一行：二叉树的先序遍历序列 第二行：二叉树的中序遍历序列 第三行：二叉树的后序遍历序列 第四行：查找结果 第五行：查找结果 第六行~第八行：插入新结点后的二叉树的先、中、序遍历序列第九行：插入新结点后的二叉树的中序遍历序列（非递归算法）第十行：插入新结点后的二叉树的层次遍历序列 第十一行~第十三行：第一次交换各结点的左右子树后的先、中、后序遍历序列第十四行~第十六行：第二次交换各结点的左右子树后的先、中、后序遍历序列第十七行：二叉树的深度 第十八行：叶子结点数 */ #include "stdio.h" #include "malloc.h" #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 typedef int Status; typedef int KeyType; #define STACK_INIT_SIZE 100 // 存储空间初始分配量 #define STACKINCREMENT 10 // 存储空间分配增量 #define MAXQSIZE 100 typedef int ElemType; typedef struct BiTNode{ ElemType data; struct BiTNode *lchild,*rchild;// 左右孩子指针 } BiTNode,*BiTree; Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p) { if(!T){p=f;return FALSE;} else if(key==T->data){p=T;return TRUE;} else if(key 课程设计报告 课程名称数据结构课程设计 题目平衡二叉树操作 指导教师 设计起止日 2010-5-16 学院计算机学院 专业软件工程 学生姓名 班级/学号------------ 成绩_________________ 一．需求分析 1、建立平衡二叉树并进行创建、增加、删除、调平等操作。 2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。 3、测试数据：自选数据 二．概要设计 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下： ⑴每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点； ⑵若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； ⑶判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整； ⑷如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突； ⑸计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。 三．详细设计 树的内部变量 typedef struct BTNode { 题目: 基于层次遍历的二叉树算法设计 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写 等具体要求） 1、系统应具备的功能： （1）建立二叉树 （2）按层次遍历二叉树 2、数据结构设计； 3、主要算法设计； 4、编程及上机实现； 5、撰写课程设计报告，包括： （1）设计题目； （2）摘要和关键字； （3）正文，包括引言、需求分析、数据结构设计、算法设计、程序实现及测试、不足之处、设计体会； （4）结束语； （5）参考文献。 时间安排：2007年7月2日－7日（第18周） 7月2日查阅资料 7月3日系统设计，数据结构设计，算法设计 7月4日-5日编程并上机调试 7月6日撰写报告 7月7日验收程序，提交设计报告书。 指导教师签名： 2007年7月2日 系主任（或责任教师）签名： 2007年7月2日 基于层次遍历的二叉树算法设计 摘要：本程序设计实现二叉树的层次遍历，该程序主要部分包括：创建二叉树，按层次遍历二叉树。. 关键字：二叉树，队列，二叉链表，数据结构 . 0.引言： 树型结构是一类重要的非线性数据结构，其中一树和二叉树最重要。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构够可以用树来形象表示。树在计算机领域中也得到了广泛应用，如在编译程序中，可以用树来表示源程序的语法结构。二叉树是一种非线性数据结构，对它进行操作时总需要对每个数据逐一进行操作，这样就存在一个操作顺序问题，由此提出了二叉树的遍历操作问题，所谓遍历二叉树就是按某种顺序访问二叉树中某个结点一次且仅一次的过程，这里的访问可以是输出.比较.更新.查看元素内容等各种操作。 1.需求分析： 1.1行输入数据构造二叉树。 1.2用队列存储二叉树结点。 1.3算法实现层次遍历。 1.4实现过程: A：初始，系统开始运行后，要先构造二叉树，先输入根结点数据信息。 B：根据提示信息输入其左子树，若没有左子树则输入“-1”。 C：根据提示信息输入其右子树，若没有右子树则输入“-1”。 D：在二叉树构造完成之后程序会自动按层次遍历二叉树，并且输出相应结点 数据信息。 E：在完成上述过程之后按任意键结束程序。 2.数据结构设计： 2.1树的链式存储 typedef struct Bitnode /*树的链式存储*/ 平衡二叉树调整算法 在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为A，并已知A的左孩子平衡因子为0，右孩子平衡因子为1，则应该做（C）型调整以使其平衡 A LL B LR C RL D RR 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。 失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于 1 的结点作为根的子树。假设用 A 表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。 （1）LL型平衡旋转法 由于在 A 的左孩子 B 的左子树上插入结点 F ，使 A 的平衡因子由 1 增至2 而失去平衡。故需进行一次顺时针旋转操作。即将 A 的左孩子 B 向右上旋转代替 A 作为根结点， A 向右下旋转成为 B 的右子树的根结点。而原来B 的右子树则变成 A 的左子树。 （2）RR型平衡旋转法 由于在 A 的右孩子 C 的右子树上插入结点 F ，使 A 的平衡因子由-1 减至-2 而失去平衡。故需进行一次逆时针旋转操作。即将 A 的右孩子 C 向 左上旋转代替 A 作为根结点， A 向左下旋转成为 C 的左子树的根结点。而原来C 的左子树则变成 A 的右子树。 （3）LR型平衡旋转法 由于在 A 的左孩子 B 的右子数上插入结点 F ，使 A 的平衡因子由 1 增至2 而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A 结点的左孩子B 的右子树的根结点 D 向左上旋转提升到 B 结点的位置，然后再把该D 结点向右上旋转提升到 A 结点的位置。即先使之成为LL型，再按LL型处理。 如图中所示，即先将圆圈部分先调整为平衡树，然后将其以根结点接到 A 的左子树上，此时成为LL 型，再按LL 型处理成平衡型。 （4）RL型平衡旋转法 由于在 A 的右孩子 C 的左子树上插入结点 F ，使 A 的平衡因子由-1 减至-2 而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A 结点的右孩子C 的左子树的根结点D 向右上旋转提升到C 结点的位置，然后再把该D 结点向左上旋转提升到 A 结点的位置。即先使之成为RR型， 二叉树应用——二叉树基本算法的实现 【功能要求】 实现Create方法，要求键盘输入二叉树结点序列，创建一棵二叉树（提示：前序递归） 实现SwapTree方法，以根结点为参数，交换每个结点的左子树和右子树（提示：前序递归） 增加InorderTree方法，采用非递归方法实现二叉树的中序遍历 你可以选择： 对BinaryTree模板进行功能扩充； 自己定义并实现二叉树类 要求键盘输入二叉树结点序列 结点序列可以是前序，也可以是层次 空结点以#表示 【代码实现】 // 二叉树01.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include bool Root (T&x)const; void MakeTree(const T&element,BinaryTree数据结构平衡二叉树的操作演示
平衡二叉树的生成过程
数据结构程序报告(平衡二叉树的操作)
二叉树的各种算法
设计一个完整的程序,实现二叉树的各种算法
平衡二叉树(AVL)的查找、插入和删除
平衡二叉树操作演示
二叉树排序算法
平衡二叉树 构造方法(绝妙)
数据结构程序报告(平衡二叉树的操作)
实验10 二叉树的基本操作
实现平衡二叉排序树的各种算法代码 一
平衡二叉树
二叉树的各种算法
数据结构课程设计-_平衡二叉树操作
基于层次遍历的二叉树算法设计
平衡二叉树调整算法
二叉树应用之二叉树基本算法的实现