二叉平衡树的程序分析
/* Note:Your choice is C IDE *///平衡二叉树。#include"stdio.h"
#include"stdlib.h"
typedef struct Node
{
int key;
struct Node*pLeft;
struct Node*pRight;
int bf;
}
Node;
void RightRotate(Node**pNode)//右旋函数。
{
Node*pAxis=(*pNode)->pLeft;
(*pNode)->pLeft=pAxis->pRight;
pAxis->pRight=*pNode;
*pNode=pAxis;
}
void LeftRotate(Node**pNode)//左旋函数。
{
Node*pAxis=(*pNode)->pRight;
(*pNode)->pRight=pAxis->pLeft;
pAxis->pLeft=*pNode;
*pNode=pAxis;
}
void LL_LR_Balance(Node**pNode)//LL型或LR函数。{
Node*pLeft=(*pNode)->pLeft;
Node*pRight;
switch(pLeft->bf)
{
case 1:
(*pNode)->bf=pLeft->bf=0;
RightRotate(pNode);
break;
case-1:
pRight=pLeft->pRight;
switch(pRight->bf)
{
case 0:(*pNode)->bf=pLeft->bf=0;break;
case 1:pRight->bf=pLeft->bf=0;(*pNode)->bf=-1;break;
case-1:(*pNode)->bf=pRight->bf=0;pLeft->bf=1;break;
}
LeftRotate(&(*pNode)->pLeft);
RightRotate(pNode);
break;
}
}
void RR_RL_Balance(Node**pNode) //RR型或RL函数。
{
Node*pRight=(*pNode)->pRight;
Node*pLeft;
switch(pRight->bf)
{
case-1:
(*pNode)->bf=pRight->bf=0;
LeftRotate(pNode);
break;
case 1:
pLeft=pRight->pLeft;
switch(pLeft->bf)
{
case 0:(*pNode)->bf=pRight->bf=0;break;
case 1:(*pNode)->bf=pLeft->bf=0;pRight->bf=-1;break;
case-1:pRight->bf=pLeft->bf=0;(*pNode)->bf=1;break;
}
RightRotate(&(*pNode)->pRight);
LeftRotate(pNode);
break;
}
}
int InsertBST(Node**pRoot,int key,int*chain) Insert（）函数。{
if((*pRoot)==NULL)
{
*pRoot=(Node*)malloc(sizeof(Node));
(*pRoot)->bf=0;
(*pRoot)->pLeft=(*pRoot)->pRight=NULL;
(*pRoot)->key=key;
*chain=1;
}
else
{
if(key==(*pRoot)->key)
{*chain=0;return 0;}
if(key<(*pRoot)->key)
{
if(!InsertBST(&(*pRoot)->pLeft,key,chain))return 0;
if(*chain)
{
switch((*pRoot)->bf)
{
case 0:(*pRoot)->bf=1;*chain=1;break;
case 1:LL_LR_Balance(pRoot);*chain=0;break;
case-1:(*pRoot)->bf=0; *chain=0;break;
}
}
}
else
{if(!InsertBST(&(*pRoot)->pRight,key,chain))return 0;
if(*chain)
{
switch((*pRoot)->bf)
{
case 0:(*pRoot)->bf=-1;*chain=1;break;
case 1:(*pRoot)->bf=0;*chain=0;break;
case-1:RR_RL_Balance(pRoot);*chain=0;break;
}
}
}
}
return 1;
}
void PintTree(Node *bt,int n)//屏幕显示二叉树!
{
int i;
if(bt==NULL)return ;
PintTree(bt->pLeft,n+1);
for(i=0;i printf(" "); if(n>=1)printf(" ---"); printf("%d\n",bt->key); PintTree(bt->pRight,n+1); } void main() { Node*pRoot=NULL;int a=0,*chain=&a,n=0; InsertBST(&pRoot,3,chain); InsertBST(&pRoot,8,chain); InsertBST(&pRoot,16,chain); InsertBST(&pRoot,7,chain); InsertBST(&pRoot,2,chain); InsertBST(&pRoot,5,chain); PintTree(pRoot, n); } RR型或RL函数与LL型或LR函数的程序分析： 已经知道是LL型的树。设n、x、y表示数的高度，x=n-1，y=n-1； B的左子树的高度为n,包括C。 A上的2表示平衡因子A—>bf。B上的1也是B—>bf。右旋后结果： 由图可知A的平衡因子变为0，B的平衡因子也变为0。 至于子树的位置都不变。 下面是LR型（先左旋，后右旋） 分三种情况。 C—>bf=0；（C—>bf为平衡因子。） 设C的左子树的高度x=n，由于C的平衡因子为0，则右子树的高度y=n，同理已知了B的右子树的高度为n+1，B的平衡因子为-1，则可知B的左子树的高度为n.。其余的推论类似。 第一步左旋： 第二步右旋： 由于C原来为0，不用修改。当C bf=1时。 第一步： 第二步： 当C—>bf=-1时。 第一步： 第二步： 下面的是RR型的二叉平衡树。（只需左旋一次。） 左旋后的结果： 左旋之后，如图，得到A、B点的平衡因子信息。如上修改。下面是RL型的证明： 也分三种情况： C—>bf=0， 第一步右旋： 第二步（左旋）： 当C—>bf=1， 第一步： 第二步： 当C—>bf=-1时。 第一步： 第二步： 对Insert（）函数的分析： Insert（）函数的插入算法的内容： 如果插入一个叶子结点，对于双亲结点来说，高度是增加的。未插入时，parent—>bf=0。左边插入后，parent—>bf+1=1.高度增加chan=1。 右边插入后，parent—>bf-1=-1.高度增加,chan=1。（如果某结点的子树高度增加，则该结点的高度的改变量可能为1、0、-1，要做出判断。）而在递归退回到双亲结点的双亲结点时， 当这个祖先结点的子树高度增加，该结点的平衡因子grandparent→bf可能为1、 0、-1。 <一>.如果双亲结点是祖先的左孩子。 若grandparent→bf=-1，则grandparent→bf=0；高度没有增加，chan=0； 若grandparent→bf=0，则grandparent→bf=1；高度增加，chan=1； 若grandparent→bf=1，则grandparent→bf=2；调用LL型或LR函数，高度没有增加，chan=0； <二>.如果双亲结点是祖先的右孩子。 若grandparent→bf=-1，则grandparent→bf=-2；调用RR型或RL函数，高度没有增加，chan=0； 若grandparent→bf=0，则grandparent→bf=-1；高度增加，chan=1； 若grandparent→bf=1，则grandparent→bf=0；高度没有增加，chan=0； 从上可知parent结点与grandparent结点是可以用递归统一的(看图中的红字与蓝字部分)。插入算法最多修改二层，从叶结点算起的三代结点。 树和二叉树 以下问题要求统一在一个大程序里解决。 10、按先序遍历的扩展序列建立二叉树的存储结构 11、二叉树先序、中序、后序遍历的递归算法 12、二叉树中序遍历的非递归算法 13、二叉树层次遍历的非递归算法 14、求二叉树的深度(后序遍历) 15、建立树的存储结构 16、求树的深度 17、 源程序代码： // tree.cpp : Defines the entry point for the console application. // #include "stdafx.h" #include "stdio.h" #include "stdlib.h" #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -1 typedef char TElemType; // 元素数据类型 typedef int Status; /* 二叉链表储存结构*/ typedef struct BiTNode { TElemType data; struct BiTNode *lchild, *rchild; }BiTNode, *BiTree; bool CreateBiTree(BiTree &T) { //先序序列建立二叉树 char ch; scanf("%c",&ch); if (ch=='*') T = NULL; else { if (!(T = (BiTNode *)malloc(sizeof(BiTNode)))) return ERROR; T->data = ch; CreateBiTree(T->lchild); CreateBiTree(T->rchild); } return OK; } Status PrintElement(TElemType e) { // 访问函数 printf("%c", e); return OK; } Status PreOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { //先序遍历二叉树的递归算法 if (T) { if (Visit(T->data)) if (PreOrderTraverse(T->lchild, Visit)) if (PreOrderTraverse(T->rchild, Visit)) return OK; return ERROR; }else return OK; } Status InOrderTraverse(BiTree T, Status(*Visit)(TElemType)) { //中序遍历二叉树的递归算法 if (T) { if (InOrderTraverse(T->lchild, Visit)) if (Visit(T->data)) if (InOrderTraverse(T->rchild, Visit)) return OK; return ERROR; }else return OK; 平衡二叉树操作的演示 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.各模块之间的层次调用 实验三二叉树的基本运算 一、实验目的 1、使学生熟练掌握二叉树的逻辑结构和存储结构。 2、熟练掌握二叉树的各种遍历算法。 二、实验内容 题目一：二叉树的基本操作实现（必做题） [问题描述] 建立一棵二叉树，试编程实现二叉树的如下基本操作： 1. 按先序序列构造一棵二叉链表表示的二叉树T； 2. 对这棵二叉树进行遍历：先序、中序、后序以及层次遍历，分别输出结点的遍历序列； 3. 求二叉树的深度/结点数目/叶结点数目；(选做) 4. 将二叉树每个结点的左右子树交换位置。（选做） [基本要求] 从键盘接受输入（先序），以二叉链表作为存储结构，建立二叉树（以先序来建立）， [测试数据] 如输入：ABCффDEфGффFффф（其中ф表示空格字符） 则输出结果为 先序：ABCDEGF 中序：CBEGDFA 后序：CGEFDBA 层序：ABCDEFG [选作内容] 采用非递归算法实现二叉树遍历。 三、算法设计 1、主要思想：根据二叉树的图形结构创建出二叉树的数据结构，然后 用指针对树进行操作，重点掌握二叉树的结构和性质。 2、本程序包含四个模块： （1）结构体定义 （2）创建二叉树 （3）对树的几个操作 （4）主函数 四、调试分析 这是一个比较简单程序，调试过程中并没有出现什么问题，思路比较清晰 五、实验结果 六、总结 此次上机实验对二叉树进行了以一次实际操作，让我对二叉树有了更深的了解，对二叉树的特性有了更熟悉的认知，让我知 道了二叉树的重要性和便利性，这对以后的编程有更好的帮助。 七、源程序 #include 包含二叉树的顺序存储，插入，删除结点，以及设置root结点，和前序、中序、后序、按层次遍历的完成代码。 #include int BTreeAddNode(CBTree *bt,CBTree *node,int n) { if(bt==NULL) { cout<<"no parent!"< return 0; } else bt->right=node; break; default: cout<<"it's wrong!"< 平衡二叉树（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为根的二叉排序树作右旋处理 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 学院：化学与材料科学学院 专业班级：09级材料科学与工程系PB0920603 姓名：李维谷 学号：PB09206285 邮箱：liwg@https://www.wendangku.net/doc/554478911.html, 指导教师：贾伯琪 实验时间：2010年10月17日 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 数据结构实习报告 题目：平衡二叉树的操作演示 班级：信息管理与信息系统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 本程序由SOGOF完成 该完整程序主要是递归函数的使用及模板的使用，完成了对二叉树基本的链表操作，主要有二叉树的建立，前序、中序、后序遍历，求树的高度，每层结点数（包含树的最大宽度），左右结点对换，二叉树的内存释放，求解树的叶子数。 #include 平衡二叉树构造方法 平衡二叉树 对于二叉查找树，尽管查找、插入及删除操作的平均运行时间为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 类似。 C语言课程设计_二叉树演示源程序 /********tree2.c二叉树演示********/ #include void Preorder(Tree *t);/*前序遍历*/ void Midorder(Tree *t);/*中序遍历*/ void Posorder(Tree *t);/*后序遍历*/ void DrawNode(Tree *t,int color);/*遍历时显示每个结点的过程*/ void ClrScr();/*清空树的区域*/ void main() { Tree *root; randomize(); root=CreatTree();/*创建树*/ Init(); DrawTree(root);/*每次遍历前显示白色的树*/ sleep(1); s.x=100;s.y=300;s.num=1;/*每次遍历前设置显示遍历顺序显示的x,y坐标*/ Preorder(root);/*前序遍历*/ getch(); ClrScr(); DrawTree(root); sleep(1); s.x=100; s.y=350; s.num=1; Midorder(root);/*中序遍历*/ getch(); ClrScr(); DrawTree(root); sleep(1); s.x=100; s.y=400; s.num=1; 数据结构程序报告(平衡二叉树的操作) 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学号： 班级： 指导老师： 报告日期： 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); 实现平衡二叉排序树的各种算法代码一 /* 《实现平衡二叉排序树的各种算法》 一、分析题目要求 用函数实现如下平衡二叉排序树算法,: （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的右子树。 【综设实验题目】 实现学生健康情况管理的几个操作功能（新建、插入、删除、从文件读取、写入文件和查询、屏幕输出等功能）。健康表中学生的信息有学号、姓名、出生日期、性别、身体状况等。 实验内容 1．利用二叉树来实现 2．系统的菜单功能项如下： 1------新建学生健康表 2------向学生健康表插入学生信息 3------在健康表删除学生信息 4------从文件中读取健康表信息 5------向文件写入学生健康表信息 6------在健康表中查询学生信息（按学生学号来进行查找） 7------在屏幕中输出全部学生信息 8-----退出 【中文摘要】这次实验主要用二叉树来实现简单的学生健康管理系统，为了方便查找，进一步使用排序二叉树来实现。系统的功能包括：向学生健康表插入学生信息，在健康表删除学生信息，从文件中读取健康表信息，向文件写入学生健康表信息，在健康表中查询学生信息（按学生学号来进行查找），在屏幕中输出全部学生信息等。健康表中学生的信息有学号、姓名、出生日期、性别、身体状况等。 【关键词】排序二叉树学生健康管理系统学生信息 【前言】 本次实验是为了进一步熟悉和掌握VC环境下的编译、调试和执行的方法及步骤，熟悉二叉树存储的实现方式及其应用。 【实验设计】 以排序二叉树为储存机制，可以方便的实现插入或删除学生信息。每个学生的信息储存在一个结构体Sstudent中，并且这个结构体带有输出学生信息的函数ouput()。然后以这个结构体作为二叉树节点的数据类型，这样就实现了学生信息的储存。在创建二叉树对象时将已存储在文件中的学生信息写入二叉树，在析构函数里实现将学生信息写入文件。 【实验实现】 软件平台：VC++ 6.0 硬件平台：32位机器 主要功能模块分析： 课程设计报告 课程名称数据结构课程设计 题目平衡二叉树操作 指导教师 设计起止日 2010-5-16 学院计算机学院 专业软件工程 学生姓名 班级/学号------------ 成绩_________________ 一．需求分析 1、建立平衡二叉树并进行创建、增加、删除、调平等操作。 2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。 3、测试数据：自选数据 二．概要设计 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下： ⑴每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点； ⑵若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； ⑶判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整； ⑷如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突； ⑸计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。 三．详细设计 树的内部变量 typedef struct BTNode { 实验四 二叉树的建立和应用 1、实验目的 （1）熟练掌握树的基本概念、二叉树的基本操作及在链式存储结构上的实现； （2）重点掌握二叉树的生成、遍历及求深度等算法； （3）掌握运用递归方式描述算法及编写递归C 程序的方法，提高算法分析和程序设计能力。 2、实验内容 按照已知二叉树，从键盘读入节点字符，建立二叉树（ABD#G###CE##FH###） ；分别采用先序、中序、后序遍历该二叉树，分别输出遍历结果。 3、实验步骤 （1）仔细分析实验内容，给出其算法和流程图； （2）用C 语言实现该算法； （3）给出测试数据，并分析其结果； （4）在实验报告册上写出实验过程。 4、测试数据 先序序列： ABDGCEFHjfkdkfakf 中序序列： DGBAECHF 后序序列： GDBEHFCA 5、结构定义 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; 6、实验报告要求 实验报告要求书写整齐，步骤完整，实验报告格式如下： 1、［实验目的］ 2、［实验设备］ 3、［实验步骤］ 4、［实验内容］ 5、［实验结果(结论)］ G H B C D E F A 程序如下： #include "stdio.h" #include "string.h" typedef char TElemType ; typedef struct BiNode { TElemType data; struct BiNode * lchild ,* rchild; }BiNode ,*BiTree; BiTree CreateBiTree(BiTree bt) { char ch; B iTree h=NULL; c h=getchar(); i f(ch=='#') bt=NULL; e lse { if((bt=(BiNode *)malloc(sizeof(BiNode)))==NULL) exit(-2); bt->data=ch; bt->lchild=CreateBiTree(h); bt->rchild=CreateBiTree(h); } r eturn(bt); } void PreOrderTraverse(BiTree bt) 平衡二叉树调整算法 在平衡二叉树中插入一个结点后造成不平衡，设最低的不平衡结点为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型， 攀枝花学院本科学生课程设计任务书题目二叉排序树与平衡二叉树的实现 1、课程设计的目的 1)使学生进一步理解和掌握课堂上所学各种基本抽象数据类型的逻辑结构、存储结构和操 作实现算法，以及它们在程序中的使用方法。 2)使学生掌握软件设计的基本内容和设计方法，并培养学生进行规范化软件设计的能力。 3）使学生掌握使用各种计算机资料和有关参考资料，提高学生进行程序设计的基本能力。 2、课程设计的内容和要求（包括原始数据、技术要求、工作要求等） 1) (1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T； (2)对二叉排序树T作中序遍历，输出结果； (3)计算二叉排序树T查找成功的平均查找长度,输出结果； (4)输入元素x,查找二叉排序树T,若存在含x的结点,则删该结点,并作中序遍历(执行 操作2)；否则输出信息“无x”； (5)用数列L，生成平衡的二叉排序树BT:当插入新元素之后，发现当前的二叉排序树BT 不是平衡的二叉排序树，则立即将它转换成新的平衡的二叉排序树BT； (6)计算平衡的二叉排序树BT的平均查找长度，输出结果。 3、主要参考文献 ［1］刘大有等，《数据结构》（C语言版），高等教育出版社 ［2］严蔚敏等，《数据结构》（C语言版），清华大学出版社 ［3］William Ford，William Topp，《Data Structure with C++》清华大学出版社 ［4］苏仕华等，数据结构课程设计，机械工业出版社 4、课程设计工作进度计划 第1天完成方案设计与程序框图 第2、3天编写程序代码 第4天程序调试分析和结果 第5天课程设计报告和总结 指导教师（签字）日期年月日 教研室意见： 年月日学生（签字）： 接受任务时间：年月日注：任务书由指导教师填写。求树和二叉树的深度题目及源程序代码
数据结构平衡二叉树的操作演示
平衡二叉树的生成过程
数据结构程序报告(平衡二叉树的操作)
实验三二叉树的基本操作
完整二叉树实例程序
平衡二叉树(AVL)的查找、插入和删除
《二叉树基本操作实验报告》
平衡二叉树操作演示
二叉树基本操作经典实例
平衡二叉树 构造方法(绝妙)
C语言课程设计_二叉树演示源程序
数据结构程序报告(平衡二叉树的操作)
实现平衡二叉排序树的各种算法代码 一
平衡二叉树
用二叉树来实现学生健康情况管理系统
数据结构课程设计-_平衡二叉树操作
数据结构课程实验(树和二叉树的建立和应用)
平衡二叉树调整算法
二叉排序树与平衡二叉树的实现课程设计