平衡二叉树操作演示.doc
平衡二叉树操作的演示
#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;
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 的左子树上的情况
p->bf=0;
将
}
p=p2;
p->bf=0;
p 指向新的结点，并置其
}
taller=0;
bf 值为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)
{// 以括号表示法输出AVL
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;
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;
}
{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)
{// 由 DeleteAVL 调用，用于处理被删结点左右子树均不空的情况
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 DeleteAVL(BSTNode *&p,KeyType x,int &taller)
{// 在 AVL 树中删除关键字为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(" 创建一棵 AVL 树:\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); DeleteAVL(b,k,j); printf("A VL:"); DispBSTree(b); printf("\n"); k=2; printf(" 删除结点 %d:",k); DeleteAVL(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．熟悉二叉树结点的结构和对二叉树的基本操作。 2．掌握对二叉树每一种操作的具体实现。 3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。 4.会用二叉树解决简单的实际问题。 二、实验内容 设计程序实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。 1 按先序次序建立一个二叉树， 2按（A:先序 B:中序 C:后序）遍历输出二叉树的所有结点 以上比做，以下选做 3求二叉树中所有结点数 4求二叉树的深度 三、实验步骤 ㈠、数据结构与核心算法的设计描述 /* 定义DataType为char类型 */ typedef char DataType; /* 二叉树的结点类型 */ typedef struct BitNode { DataType data; struct BitNode *lchild,*rchild; }*BitTree; 相关函数声明： 1、/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT) { BT=(BitTree)malloc(sizeof(BitNode)); BT->data=NULL; cout<<"二叉树初始化成功!"< 二叉树的各种算法.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 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学号： 班级： 指导老师： 报告日期： 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.各模块之间的层次调用 数据结构实习报告 题目：平衡二叉树的操作演示 班级：信息管理与信息系统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; } /*---------------------------------------------递归部分-------------------------------------------*/ 平衡二叉树（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为根的二叉排序树作右旋处理 二叉树遍历算法的实现 题目：编制二叉树遍历算法的实现的程序 一．需求分析 1.本演示程序中，二叉树的数据元素定义为非负的整型（unsigned int）数据，输 入-1表示该处没有节点 2.本演示程序输入二叉树数据均是按先序顺序依次输入 3.演示程序以用户和计算机对话方式执行，即在计算机终端上显示“提示信息” 之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据和运 算结果显示在其后 4.本实验一共包括三个主要程序，分别是：1）二叉树前序，中序，后序遍历递归 算法实现2）二叉树前序中序遍历非递归算法实现3)二叉树层次遍历算法实现 5.本程序执行命令包括：1）构建二叉树2）二叉树前序递归遍历3）二叉树中序 递归遍历4）二叉树后序递归遍历5）二叉树前序非递归遍历6）二叉树中序非 递归遍历7）二叉树层次遍历 6.测试数据 （1）7 8 -1 9 10 -1 -1 -1 6 11 -1 -1 12 13 -1 -1 14 -1 -1 （2）1 -1 -1 （3）7 8 -1 -1 9 -1 -1 二．概要设计 1.为实现二叉树的遍历算法，我们首先给出如下抽象数据类型 1）二叉树的抽象数据类型 ADT BiTree{ 数据对象D:D是具有相同特性的数据元素的集合 数据关系R： 若D=Φ，则R=Φ，称BiTree是空二叉树； 若D≠Φ，则R={H}，H是如下二元关系： (1)在D中存在唯一的成为根的数据元素root，它在关系H下无前驱； (2)若D-{H}≠Φ，则存在D-{root}={D1,D r}，且D1∩D r=Φ (3)若D1≠Φ，则D1中存在唯一的元素x1， 浙江大学城市学院实验报告 课程名称数据结构基础 实验项目名称实验十二叉树的基本操作 学生姓名专业班级学号 实验成绩指导老师（签名）日期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的右子树。 数据结构程序报告(平衡二叉树的操作) 计算机科学学院数据结构课程设计报告 平衡二叉树操作 学生姓名： 学号： 班级： 指导老师： 报告日期： 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); 《数据结构与数据库》 实验报告 实验题目 二叉树的基本操作及运算 一、需要分析 问题描述： 实现二叉树（包括二叉排序树）的建立，并实现先序、中序、后序和按层次遍历，计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目，以及二叉树常用运算。 问题分析： 二叉树树型结构是一类重要的非线性数据结构，对它的熟练掌握是学习数据结构的基本要求。由于二叉树的定义本身就是一种递归定义，所以二叉树的一些基本操作也可采用递归调用的方法。处理本问题，我觉得应该： 1、建立二叉树； 2、通过递归方法来遍历（先序、中序和后序）二叉树； 3、通过队列应用来实现对二叉树的层次遍历； 4、借用递归方法对二叉树进行一些基本操作，如：求叶子数、树的深度宽度等； 5、运用广义表对二叉树进行广义表形式的打印。 算法规定： 输入形式：为了方便操作，规定二叉树的元素类型都为字符型，允许各种字符类型的输入，没有元素的结点以空格输入表示，并且本实验是以先序顺序输入的。 输出形式：通过先序、中序和后序遍历的方法对树的各字符型元素进行遍历打印，再以广义表形式进行打印。对二叉树的一些运算结果以整型输出。 程序功能：实现对二叉树的先序、中序和后序遍历，层次遍历。计算叶子结点数、树的深度、树的宽度，求树的非空子孙结点个数、度为2的结点数目、度为2的结点数目。对二叉树的某个元素进行查找，对二叉树的某个结点进行删除。 测试数据：输入一：ABC□□DE□G□□F□□□（以□表示空格）,查找5,删除E 预测结果：先序遍历ABCDEGF 中序遍历CBEGDFA 后序遍历CGEFDBA 层次遍历ABCDEFG 广义表打印A（B（C,D（E（,G）,F））） 叶子数3 深度5 宽度2 非空子孙数6 度为2的数目2 度为1的数目2 查找5，成功，查找的元素为E 删除E后，以广义表形式打印A（B（C,D（,F））） 输入二：ABD□□EH□□□CF□G□□□（以□表示空格）,查找10,删除B 预测结果：先序遍历ABDEHCFG 中序遍历DBHEAGFC 后序遍历DHEBGFCA 层次遍历ABCDEFHG 广义表打印A（B(D,E(H)),C(F(,G))） 叶子数3 深度4 宽度3 非空子孙数7 度为2的数目2 度为1的数目3 查找10，失败。 二叉树的各种算法.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 [1996] 设t 为一棵二叉树的根结点地址指针，试设计一个非递归算法完成把二叉树中每个结点的左右孩子位置交换。 int swithLRChild(BiTree *t) { BiTree *stack[100] = {0}; int stack_length = 0; if (NULL == t){ return 0; } stack[stack_length++] = t; while (stack_length > 0){ //pop stack BiTree *node = stack[stack_length - 1]; stack_length -= 1; BiTree *temp = node ->lchild; node->lchild = node ->rchild; node->rchild = temp; if (NULL != node ->rchild){ stack[stack_length++] = node ->rchild;} if (NULL != node ->lchild){ stack[stack_length++] = node ->lchild; } } return 1; } [1998]一棵高度为K 且有n个结点的二叉排序树，同时又是一棵完全二叉树存于向量t 中，试设计删除树中序号为i 且具有左右孩子的一个结点，而不使存储量增加保证仍为二叉排序树(不一定是完全二叉树)的算法。 //存数据的位置是从 1 的索引开始的，避免需要访问索引为0 的空间，避免需要频繁的索引 转换 void delNodeInSortedBiTree(int *sorted_bitree, int *last_index,int i) { //因为题目中描述具有左右孩子，所以直接从左孩子的最右边叶子节点开始//分两种情况，左孩子没有右孩子，那么左孩子之后的节点都移动一个位子//左孩子存在右孩子，则从右孩子的左孩子一直走，到叶子节点停止，因为是叶子节点//就不需要移动元素了 int del_node_index = 2*i; if (2*del_node_index + 1 >= *last_index) 题目: 基于层次遍历的二叉树算法设计 初始条件： 理论：学习了《数据结构》课程，掌握了基本的数据结构和常用的算法； 实践：计算机技术系实验室提供计算机及软件开发环境。 要求完成的主要任务:（包括课程设计工作量及其技术要求，以及说明书撰写 等具体要求） 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 /*树的链式存储*/数据结构平衡二叉树的操作演示
平衡二叉树的生成过程
实验三 二叉树的基本操作实现及其应用
二叉树的各种算法
设计一个完整的程序,实现二叉树的各种算法
数据结构程序报告(平衡二叉树的操作)
平衡二叉树操作演示
二叉树排序算法
平衡二叉树(AVL)的查找、插入和删除
二叉树遍历算法的实现
实验10 二叉树的基本操作
实现平衡二叉排序树的各种算法代码 一
平衡二叉树
数据结构程序报告(平衡二叉树的操作)
数据结构实验三——二叉树基本操作及运算实验报告
二叉树的各种算法
东北大学计算机初试历年二叉树算法题目及解答
基于层次遍历的二叉树算法设计