实验报告平衡二叉树

实验四平衡二叉树演示1•问题定义及需求分析课题目的和任务问题描述：利用平衡二叉树设计动态查找表。

\/ 实验要求：\设计平衡二叉树的动态演示的模拟程序。

1）采用平衡二叉树存储结构。

2）完成平衡二叉树的创建、查找、插入和删除的演示操作。

3）可以考虑两棵平衡二叉树的合并。

数据形式输入数据形式：通过键盘输入数据输入值的范围：树中元素的值为float型，范围为至+38;树的名称为char类型数据，可以输入字母，数字和符号，但是长度必须在20位以内；对菜单进行操作时，输入数据长度必须在200以内，且有效的输入数据为0至7,其中0为退出程序，1至7为对应菜单的操作选项。

输出数据形式：输出到显示器。

程序功能\ 创建平衡二叉树存储结构，通过平衡因子，使二叉排序树达到平衡，提供平衡二叉树的创建、查找和删除，树中元素的查找、插入和删除等基本功能，可以实现创建多棵平衡二叉树，并且能够进行两棵树的合并。

通过平衡二叉树，能够使树时刻保持平衡，从而提高在树中遍历数据的速度，具有重要意义。

测试数据10 1 0 1 0 log n 0 log nO 2n［青输入你想要访冋的树名：t2t2树现在的形狀为(’〔)'里为平衛因子，7代表空儿3(-1)1(0) 7(0)咔+ 4(0 10(0)请按任意犍继续・・・.请输入你祖要访问的树名’12t2树现在的形状为('()'里为平術因子■ *代表空h 3M)1(0) 4(7* * * io to)***□!：****\z衡树"<<endl; 2. 在树中查找元素"<<endl;3. 在树中插入元素"<<endl;4. 在树中删除元素"<<endl;5. 输出二叉平衡树结构示意图"<<e ndl;6. 合并两个二叉平衡树"<<e ndl;7. 删除二叉平衡树"<<endl<<endl;0退出程序)："；建二叉平break;}}switch(a){case '1':{system("cls");cout<<"请输入需要创建的平衡树个数:";int j,k;cin> >k;for(j=0;j<k;j++){cout<<"请输入第"<<j+1<<"棵平衡树的树名(小于20个字符)："; char name[NAME_LENGTH]; /cin»n ame;cout<<"请输入元素个数:"<<endl;int m,n;cin>>n; \ /cout<<"请依次输入元素:"<<endl;Type e;AVL t=NULL;for(m=0;m <n ;m++){cin >>;int taller=O;<<e ndl;}else{cout<<"该树中不存在这个数！"<<e ndl;}system("pause");system("cls");break;}case 3:{system("cls");cout<<"请输入你想要访问的树名："<<e ndl;char n ame[NAME_LENGTH];cin»n ame;Li nk s;if(!SearchL(l, name,s)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}cout<<"请输入插入元素个数"<<e ndl;int m,n;cin»n;cout<<"请依次输入插入元素"<<e ndl;Type e;for(m=0;m <n ;m++){cin >>;int taller=O;〃增高标识，1为增高，0为不增高In sertTree(s->t,e,taller);}\ cout<<"插入成功！"<<endl;system("pause");system("cls");break;}case '4':{system("cls");cout<<"请输入你想要访问的树名："<<e ndl;char n ame[NAME_LENGTH];cin»n ame; \ /Li nk s;if(!SearchL(l, name,s)){'*'代表空）:cout<<"未找到该名字的平衡树！ "<<e ndl; system("pause"); system("cls"); break;}cout<<"请输入删除元素个数 "<<e ndl; int m,n; cin»n;cout<<"请依次输入需要删除的元素 "<<e ndl; Type e;for(m=0;m <n ;m++){cin >>;int shorter=0;〃降低表示，1为降低，0为不降低 DeleteTree(s->t,e,shorter); }cout<<"删除成功！ "<<e ndl; system("pause"); system("cls"); break; }case '5':{system("cls");cout<<"请输入你想要访问的树名： "<<e ndl; char n ame[NAME_LENGTH]; cin»n ame; Li nk s;if(!SearchL(l, name,s)){cout<<"未找到该名字的平衡树！ "<<e ndl; system("pause"); system("cls"); break;\ }if(s->t!=NULL){cout<<s->tree_name<<"树现在的形状为('()'里为平衡因子, "<<e ndl;Prin tTreeStructure(s->t); cout<<e ndl; }system("pause"); system("cls"); break; }case '6':{system("cls");"<<e ndl;（会将后者合并到前者）: cout<<"请分别输入你想要合并的两个树的名字char n ame1[NAME_LENGTH]; cin»n amel;Li nk s1;if(!SearchL(l, name1,s1)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}char n ame2[NAME_LENGTH];cin»n ame2;Li nk s2;if(!SearchL(l, name2,s2)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}else{MergeTree(s1->t,s2->t);〃将t2 合并到t1 上DeleteL(s2);〃删除链表结点12 cout<<"合并树成功！"<<e ndl;system("pause"); system("cls");break;}}case '7':{system("cls");cout<<"请输入你想要删除的树的名字："<<e ndl;\ char name[NAME_LENGTH];cin»n ame;Li nk s;if(!SearchL(l, name,s)){cout<<"未找到该名字的平衡树！"<<e ndl;system("pause");system("cls");break;}else{ \ /DestroyTree(s->t);DeleteL(s);cout<<"删除树成功！"<<e ndl;system("pause");system("cls");break;}}}}}/**/#i nclude""void LeftBalance(AVL& t){〃左部平衡化处理AVL l,lr;l=t->lchild;switch(l->bf){//检查T的左子树平衡度，并作相应的平衡处理case，做单右旋处理t->bf=l->bf=EH;R_Rotate(t);break;case , insertAVL 用不着t->bf=LH;l->bf=RH;R_Rotate(t);break;case，做双旋处理lr=l->rchild;switch(lr->bf){case LH:t->bf=RH;l->bf=EH;break;case EH:t->bf=l->bf=EH;break;case RH:t->bf=EH;l->bf=LH;break;}lr->bf=EH; \ /L_Rotate(t->lchild);R_Rotate(t);}}void RightBalance(AVL& t){〃右部平衡化处理AVL r,rl;r=t->rchild;switch(r->bf){case，要做单左旋处理t->bf=r->bf=EH;L_Rotate(t);break;case , insertAVL 用不着t->bf=RH;r->bf=LH;L_Rotate(t);break;case，要做双旋处理rl=r->lchild;switch(rl->bf){case LH:t->bf=EH;r->bf=RH;break;case EH:t->bf=r->bf=EH;break;case RH:t->bf=LH;r->bf=EH;break;}rl->bf=EH;R_Rotate(t->rchild);L_Rotate(t); \}}/**/#i nclude""int InsertTree(AVL& t,Type e,int& taller){// 二叉平衡树的结点插入if(!t){t=(AVL)malloc(sizeof(AVLTree)); 、、t->=;t->lchild=t->rchild=NULL;0,结束t->bf=EH;taller=1;}else{if==t->{〃找到重复元素时，不插入，返回 0taller=0;return 0;}if<t->{〃应在T 的左子树中搜寻if(!l nsertTree(t->lchild,e,taller))return 0;// 找到重复元素，依次返回if(taller){〃插入左子树，且左子树变高switch(t->bf){case ，需要做左平衡处理LeftBala nce(t);taller=0;break;case ，现因左子树增高而树增高t->bf=LH;taller=1;break;case ，现在左右子树等高t->bf=EH;taller=0;break;"/switch}//if}//ifelse{//应在T 的右子树中搜寻if(!InsertTree(t->rchild,e,taller))returin 0; if(taller){//插入右子树，且右子树长高 switch(t->bf){case ，现在左右子树等高t->bf=EH;taller=0;break;case ，现在右子树变高t->bf=RH;taller=1;break;case ，现在需做右平衡处理RightBala nce(t);taller=0;break;}//switch即查找q}//if}//else}//elsereturn 1;}/**/#i nclude""int DeleteTree(AVL& t,Type e,int& shorter){〃 平衡二叉树的结点删除if(t==NULL){〃不存在该元素return 0;//删除失败}else if==t->{//找到元素结点 \AVL q=NULL;if(t->lchild==NULL){// 左子树为空q=t;t=t->rchild;delete q;shorter=1;}else if(t->rchild==NULL){// 右子树为空q=t;t=t->lchild;delete q;shorter=1;}else{//左右子树都存在q=t->lchild;\ while(q->rchild){//找到要删除结点t 的左孩子的最右孩子 qq=q->rchild;}t->=q->;//把q 的值给tDeleteTree(t->lchild,q->data,shorter);// 在左子树中递归删除前驱结点。

实验报告：二叉树第一篇：实验报告：二叉树实验报告二叉树一实验目的1、进一步掌握指针变量，动态变量的含义；2、掌握二叉树的结构特性以及各种存储结构的特点及适用范围。

3、掌握用指针类型描述、访问和处理二叉树的运算。

4、熟悉各种存储结构的特征以及如何应用树结构解决具体问题。

二实验原理树形结构是一种应用十分广泛和重要的非线性数据结构，是一种以分支关系定义的层次结构。

在这种结构中，每个数据元素至多只有一个前驱，但可以有多个后继；数据元素之间的关系是一对多的层次关系。

树形结构主要用于描述客观世界中具有层次结构的数据关系，它在客观世界中大量存在。

遍历二叉树的实质是将非线性结构转为线性结构。

三使用仪器，材料计算机 2 Wndows xp 3 VC6.0四实验步骤【问题描述】建立一个二叉树，请分别按前序，中序和后序遍历该二叉树。

【基本要求】从键盘接受输入（按前序顺序），以二叉链表作为存储结构，建立二叉树（以前序来建立），并采用递归算法对其进行前序，中序和后序遍历，将结果输出。

【实现提示】按前序次序输入二叉树中结点的值（一个整数），0表示空树，叶子结点的特征是其左右孩子指针为空。

五实验过程原始记录基本数据结构描述； 2 函数间的调用关系；用类C语言描述各个子函数的算法；附录：源程序。

六试验结果分析将实验结果分析、实验中遇到的问题和解决问题的方法以及关于本实验项目的心得体会，写在实验报告上。

第二篇：数据结构-二叉树的遍历实验报告实验报告课程名：数据结构（C语言版）实验名：二叉树的遍历姓名：班级：学号：时间：2014.11.03一实验目的与要求1.掌握二叉树的存储方法2.掌握二叉树的三种遍历方法3.实现二叉树的三种遍历方法中的一种二实验内容• 接受用户输入一株二叉树• 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序三实验结果与分析//*********************************************************** //头文件#include #include //*********************************************************** //宏定义#define OK 1 #define ERROR 0 #define OVERFLOW 0//*********************************************************** typedef struct BiTNode { //二叉树二叉链表存储结构char data;struct BiTNode *lChild,*rChild;}BiTNode,*BiTree;//******************************** *************************** int CreateBiTree(BiTree &T){ //按先序次序输入二叉中树结点的值，空格表示空树//构造二叉链表表示的二叉树T char ch;fflush(stdin);scanf(“%c”,&ch);if(ch==' ')T=NULL;else{ if(!(T=(BiTNode *)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;Creat eBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrd erTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderT raverse(T->rChild);} }//*********************************************************** void PostOrderTraverse(BiTree T){ //采用二叉链表存储结构，后序遍历二叉树的递归算法if(T){ PostOrderTraverse(T->lChild);PostOrderTraverse(T->rChild) ;printf(“%c”,T->data);} }//*********************************************************** void main(){ //主函数分别实现建立并输出先、中、后序遍历二叉树printf(“please input your tree follow the PreOrder:n”);BiTNode *Tree;CreateBiTree(Tree);printf(“n先序遍历二叉树:”);PreOrderTraverse(Tree);printf(“n中序遍历二叉树:”);InOrderTraverse(Tree);printf(“n后序遍历二叉树:”);PostOrderTraverse(Tree);}图1:二叉树的遍历运行结果第三篇：数据结构二叉树操作验证实验报告班级：计算机11-2 学号：40 姓名：朱报龙成绩：_________实验七二叉树操作验证一、实验目的⑴ 掌握二叉树的逻辑结构；⑵ 掌握二叉树的二叉链表存储结构；⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。

数据结构实验报告实验名称：平衡二叉树1.实验目的和内容根据平衡二叉树的抽象数据类型的定义，使用二叉链表实现一个平衡二叉树。

二叉树的基本功能：1、平衡二叉树的建立2、平衡二叉树的查找3、平衡二叉树的插入4、平衡二叉树的删除5、平衡二叉树的销毁6、其他：自定义操作编写测试main()函数测试平衡二叉树的正确性。

2. 程序分析2.1 存储结构struct node{int key; //值int height; //这个结点的父节点在这枝最长路径上的结点个数node *left; //左孩子指针node *right; //右孩子指针node(int k){ key = k; left = right = 0; height = 1; } //构造函数};2.2 程序流程2.3 关键算法分析（由于函数过多，在此只挑选部分重要函数）算法1：void AVL_Tree::left_rotate(node *&x)[1] 算法功能：对 R-R型进行调整[2] 算法基本思想：将结点右孩子进行逆时针旋转[3] 算法空间、时间复杂度分析：都为0（1）[4] 代码逻辑node *y = x->right; y为x的右孩子x->right = y->left; 将y的左孩子赋给x的右孩子 y->left = x; x变为y的左孩子fixheight(x); 修正x，y的height值fixheight(y);x = y; 使x的父节点指向y 算法2：void A VL_Tree::right_rotate(node *&x)[1] 算法功能：对L-L型进行调整[2] 算法基本思想：将左孩子进行顺时针旋转[3] 算法空间、时间复杂度分析：都为0（1）[4] 代码逻辑node *y = x->left; //y为x的左孩子 x->left = y->right; y的右孩子赋给x的左孩子y->right = x; x变为y的右孩子fixheight(x); 修正x和y的height值fixheight(y);x = y; 使x的父节点指向y算法3：node*& A VL_Tree::balance(node *&p)[1] 算法功能：对给定结点进行平衡操作[2] 算法基本思想：通过平衡因子判断属于哪种情况，再依照情况进行平衡[3] 算法空间、时间复杂度分析：没有递归和循环，都为O（1）[4] 代码逻辑fixheight(p); //修正P的height值if (bfactor(p) == 2) 平衡因子为2，为L-？型if (bfactor(p->left) < 0) P的左孩子平衡因子<0时，为L-R型，执行left_rotate(p->left); 相关平衡操作，若>0，为L-L型。

⼆叉树总结（四）平衡⼆叉树平衡⼆叉树概念AVL树是根据它的发明者G.M. Adelson-Velsky和E.M. Landis命名的。

它是最先发明的⾃平衡⼆叉查找树，也被称为⾼度平衡树。

相⽐于"⼆叉查找树"，它的特点是：AVL树中任何节点的两个⼦树的⾼度最⼤差别为1。

AVL树的查找、插⼊和删除在平均和最坏情况下都是O(logn)。

如果在AVL树中插⼊或删除节点后，使得⾼度之差⼤于1。

此时，AVL树的平衡状态就被破坏，它就不再是⼀棵⼆叉树；为了让它重新维持在⼀个平衡状态，就需要对其进⾏旋转处理。

平衡⼆叉树结构：typedef int Type;typedef struct AVLTreeNode{Type key;int height; //当前节点的⾼度struct AVLTreeNode *left; // 左孩⼦struct AVLTreeNode *right; // 右孩⼦}Node, *AVLTree;平衡⼆叉树修复⽅法当插⼊⼀个元素使平衡⼆叉树不平衡时，可能出现以下的四种情况：1. LL：称为"左左"。

插⼊或删除⼀个节点后，根节点的左⼦树的左⼦树还有⾮空⼦节点，导致"根的左⼦树的⾼度"⽐"根的右⼦树的⾼度"⼤2，导致AVL树失去了平衡。

例如，在上⾯LL情况中，由于"根节点(8)的左⼦树(4)的左⼦树(2)还有⾮空⼦节点"，⽽"根节点(8)的右⼦树(12)没有⼦节点"；导致"根节点(8)的左⼦树(4)⾼度"⽐"根节点(8)的右⼦树(12)"⾼2。

1. LR：称为"左右"。

插⼊或删除⼀个节点后，根节点的左⼦树的右⼦树还有⾮空⼦节点，导致"根的左⼦树的⾼度"⽐"根的右⼦树的⾼度"⼤2，导致AVL树失去了平衡。

数学与计算机科学学院数据结构程序设计报告平衡二叉树学生姓名:学号:班级:指导老师:报告日期:1.题目与要求1). 问题的提出编写已个平衡二叉树，主要是对插入一个元素导致树不平衡的情况进行平衡化处理以及相关的处理。

2）设计的知识点队列的插入，删除，二叉树的建立于销毁，平衡树的平衡化，以及C语言中基础应用于结构等。

3）功能要求(1).通过不断插入的方式创建一棵平衡二叉树，包括输入结点的关键字和相关信息。

(2)按要求输出创建的平衡二叉树结点，包括顺序（中序）输出和按层次输出。

(3)插入新增的结点，若结点不存在则插入平衡二叉树，并进行相关调整。

(4)销毁二叉树。

(5)退出菜单界面如下：2.功能设计算法设计选择创建平衡二叉树后，利用循环不断插入结点，并进行调整，当输入节点为0时停止进入菜单界面。

在平横二叉树排序树BSTree上插入一个新的数据元素ｅ的递归算法可如下描述：（１）若BSTree为空树，则插入一个数据元素为e的新结点作为BSTree的根结点，树的深度增1；（２）若e的关键字和BSTree的根节点的关键字相等，则不进行插入；（３）若e的关键字小于BSTree的根结点的关键字，而且在其左子树中不存在和e形同的关键字的结点，则将e插入在其左子树上，并且当插入之后的左子树的深度加1时，分别就下列不同情况处理之：a.BSTree的跟结点的平衡因子为-1（右子树的深度大于左子树的深度）：则将跟结点的平衡因子更改为0，BBST的深度不变；b.BBST的根结点的平衡因子为0（左，右子树的深度相等）：则将根结点的平衡因子更改为1，BBST的深度增1；c.BBST的根结点的平衡因子为1（左子树的深度大于右子树的深度）：若BBST的左子树根结点的平衡因子为1，则需进行向左旋平衡处理，并且在右旋之后，将根节点和其右子树根节点的平衡因子更改为0，树的深度不变；若BBST的左子树根结点的平衡因子为-1，则需进行向左，向右的双向旋转平衡处理，并且在旋转处理之后，修改根结点和其左右子树的平衡因子，数的深度不变；（４）若e的关键字大于BBST的根结点的关键字，而且在BBST的右子树中不存在和e有相同的关键字的的节点，则将e插入在BBST的右子树上，并且当插入之后的右子树深度增加（+1）时，分别就不同情况处理之。

实验报告课程名称数据结构实验学院计算机学院专业班级计科9班学号学生姓名指导教师苏庆2015年 7 月6 日1.题目:平衡二叉树ADT BBSTree{数据对象：D＝{ ai | ai∈ElemSet, i=1,2,...,n, n≥0 }数据关系：R1＝{ <ai-1, ai>|ai-1, ai∈D, i=2,...,n }基本操作：BBSTree MakeBBSTree( )操作结果：创建好一棵树返回：将创建好的树返回Status InsertAVL(BBSTree &T, RcdType e, Status &taller)初始条件：树T已存在，e存在，taller为真操作结果：将e插入到T中返回：成功TRUE，失败FALSEStatus DeleteAVL(BBSTree &t, RcdType e, Status &shorter) 初始条件：树T已存在，e存在，shorter为真操作结果：将e从T中删除返回：成功TRUE，失败FALSEBBSTree SearchAVL(BBSTree T, RcdType e)初始条件：树T已存在，e存在操作结果：从T中找到e返回：以e为根节点的树void L_Rotate(BBSTree &p)初始条件：树p存在操作结果：对p左旋操作void R_Rotate(BBSTree &p)初始条件：树p存在操作结果：对p右旋操作void LeftBalance(BBSTree &T)初始条件：树T存在操作结果：对T左平衡操作void RightBalance(BBSTree &T)初始条件：树T存在操作结果：对T右平衡操作void ExchangeSubTree(BBSTree &T)初始条件：树T存在操作结果：对T所有左右孩子交换int BBSTreeDepth(BBSTree T)初始条件：树T已存在操作结果：求树T的深度返回：树的深度BBSTree Combine2Tree(BBSTree T1, BBSTree T2)初始条件：树T1和T2已存在操作结果：将T1和T2合并返回：合并后的树Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2,BBSTree &Tt3, int x)初始条件：树Tt1，Tt2，Tt3已存在，x存在操作结果：将Tt1分裂成Tt2和Tt3返回：以e为根节点的树Status PreOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归先序遍历输出返回：成功TRUE 失败FALSEStatus InOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归中序遍历输出返回：成功TRUE 失败FALSEStatus LastOrder_RecTraverse(BBSTree T)初始条件：树T已存在操作结果：对树T进行递归后序遍历输出返回：成功TRUE 失败FALSEvoid PreOrderTravese_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归先序遍历输出void InOrderTraverse_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归中序遍历输出void LastOrderTravese_I(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归后序遍历输出void LevelOrederTraverse_Print(BBSTree T)初始条件：树T已存在操作结果：对树T进行非递归层次遍历输出void BraNotationPrint(BBSTree T)初始条件：树T已存在操作结果：对树T用括号表示法输出}ADT BBSTree2.存储结构定义#include<stdio.h>#include<malloc.h>#define OVERFLOW -1#define OK 1#define ERROR 0#define TRUE 1#define FALSE 0#define LH +1 //左高#define EH 0 //等高#define RH -1 //右高typedef int RcdType;typedef int Status;/*平衡二叉树结构体*/typedef struct BBSTNode{RcdType data;int bf;BBSTNode *lchild, *rchild;}BBSTNode,*BBSTree;3.算法设计/*求平衡二叉树的深度*/int BBSTreeDepth(BBSTree T){int depthLeft, depthRight;if(NULL==T) return 0;else{depthLeft = BBSTreeDepth(T->lchild);depthRight = BBSTreeDepth(T->rchild);return 1+(depthLeft > depthRight ? depthLeft : depthRight);}}/*交换二叉树所有结点的左右子树*/void ExchangeSubTree(BBSTree &T){BBSTree temp;if(NULL!=T){ExchangeSubTree(T->lchild); //使用递归交换左子树ExchangeSubTree(T->rchild); //使用递归交换右子树if((T->lchild!=NULL)||(T->rchild!=NULL)){ //如果T的子树有一个不为空，则交换左右子树temp = T->lchild;T->lchild = T->rchild;T->rchild = temp;}}}/*左旋调整*/void L_Rotate(BBSTree &p){BBSTree rc = p->rchild;p->rchild = rc->lchild;rc->lchild = p;p = rc;}/*右旋调整*/void R_Rotate(BBSTree &p){BBSTree lc = p->lchild;p->lchild = lc->rchild;lc->rchild = p;p = lc;}/*左平衡处理操作*/void LeftBalance(BBSTree &T){BBSTree lc, rd;lc = T->lchild;switch(lc->bf){case LH:T->bf = lc->bf = EH; R_Rotate(T); break;case RH:rd = lc->rchild;switch(rd->bf){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; break;}rd->bf = EH;L_Rotate(T->lchild);R_Rotate(T);break;}}/*右平衡处理操作*/void RightBalance(BBSTree &T){BBSTree rd,lc;rd=T->rchild;switch(rd->bf){case RH:T->bf=rd->bf=EH; L_Rotate(T); break;case LH:lc=rd->lchild;switch(lc->bf){case RH:T->bf=LH;rd->bf=EH;break;case EH:T->bf=rd->bf=EH;break;case LH:T->bf=EH;rd->bf=RH;break;}lc->bf=EH;R_Rotate(T->rchild);L_Rotate(T);break;}}/*平衡二叉树的插入操作*/Status InsertAVL(BBSTree &T, RcdType e, Status &taller){ if(NULL==T){T = (BBSTree)malloc(sizeof(BBSTNode));T->data = e;T->bf = EH;T->lchild = NULL;T->rchild = NULL;}else if(e==T->data){ //书中已存在和e相等的结点taller = FALSE; return FALSE;}else if(e<T->data){if(FALSE==InsertA VL(T->lchild, e, taller)) return FALSE;if(TRUE==taller){switch(T->bf){case LH: LeftBalance(T); taller = FALSE; break;case EH: T->bf = LH; taller = TRUE; break;case RH: T->bf = EH; taller = FALSE; break;}}}else{if(FALSE==InsertA VL(T->rchild, e, taller)) return FALSE;if(TRUE==taller){switch(T->bf){case LH: T->bf = EH; taller = FALSE; break;case EH: T->bf = RH; taller = TRUE; break;case RH: RightBalance(T); taller = FALSE; break;}}}return TRUE;}/*平衡二叉树的删除操作*/Status DeleteA VL(BBSTree &t, RcdType e, Status &shorter){//当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=1 static int tag = 0;if(t == NULL){return FALSE; //如果不存在元素，返回失败}else if(e==t->data){BBSTNode *q = NULL;//如果该结点只有一个孩子，则将自子树取代该结点if(t->lchild == NULL){q = t;t = t->rchild;free(q);shorter = TRUE;}else if(t->rchild == NULL){q = t;t = t->lchild;free(q);shorter = TRUE;}//如果被删结点有两个孩子，则找到结点的前驱结点，//并将前驱结点的值赋给该结点，然后删除前驱结点else{q = t->lchild;while(q->rchild){q = q->rchild;}t->data = q->data;if(t->lchild->data==q->data){tag = 1;}DeleteA VL(t->lchild, q->data, shorter);if(tag==1){BBSTree r = t->rchild;if(NULL==r) t->bf = 0;else{switch(r->bf){case EH: t->bf=-1;break;default: RightBalance(t);break;}}}}}else if(e<t->data){ //左子树中继续查找if(!DeleteA VL(t->lchild, e, shorter)){return FALSE;}//删除完结点之后，调整结点的平衡因子if(shorter&&(tag==0)) {switch(t->bf){case LH:t->bf = EH;shorter = TRUE;break;case EH:t->bf = RH;shorter = FALSE;break;//如果本来就是右子树较高，删除之后就不平衡，需要做右平衡操作case RH:RightBalance(t); //右平衡处理if(t->rchild->bf == EH)shorter = FALSE;elseshorter = TRUE;break;}}}else if(e>t->data){ //右子树中继续查找if(!DeleteA VL(t->rchild, e, shorter)){return FALSE;}//删除完结点之后，调整结点的平衡因子if(shorter&&(tag==0)) {switch(t->bf){case LH:LeftBalance(t); //左平衡处理if(t->lchild->bf == EH)//注意这里，画图思考一下shorter = FALSE;elseshorter = TRUE;break;case EH:t->bf = LH;shorter = FALSE;break;case RH:t->bf = EH;shorter = TRUE;break;}}if(tag==1){int depthLeft = BBSTreeDepth(t->lchild);int depthRight = BBSTreeDepth(t->rchild);t->bf = depthLeft - depthRight;}}return TRUE;}/*平衡二叉树的查找操作*/BBSTree SearchA VL(BBSTree T, RcdType e){if(T==NULL) return NULL;if(e==T->data){return T;}else if(e>T->data){return SearchA VL(T->rchild, e);}else {return SearchA VL(T->lchild, e);}}/*获取输入存到数组a*/Array GetInputToArray(){Array head, p, q;char k;head = p = q = NULL;int m;if(k!='\n'){scanf("%d",&m);p = (ArrayNode*)malloc(sizeof(ArrayNode));head = p;p->data = m;k = getchar();}while(k!='\n'){scanf("%d",&m);q = (ArrayNode*)malloc(sizeof(ArrayNode));q->data = m;p->next = q;p = p->next;k = getchar();}if(p!=NULL){p->next = NULL;}return head; //返回存放数据的头指针}/*根据输入的字符串建一棵平衡二叉树*/BBSTree MakeBBSTree( ){int i=0;Status taller = TRUE;BBSTree T = NULL;Array a;a = GetInputToArray();while(a!=NULL){taller = TRUE;InsertA VL(T, a->data, taller);a = a->next;}return T;}/*递归先序遍历*/Status PreOrder_RecTraverse(BBSTree T){ if(NULL==T) return OK;printf("%d ",T->data);PreOrder_RecTraverse(T->lchild);PreOrder_RecTraverse(T->rchild);}/*递归中序遍历*/Status InOrder_RecTraverse(BBSTree T){ if(T->lchild)InOrder_RecTraverse(T->lchild);printf("%d ",T->data);if(T->rchild)InOrder_RecTraverse(T->rchild);}/*递归后序遍历*/Status LastOrder_RecTraverse(BBSTree T){ if(T->lchild)LastOrder_RecTraverse(T->lchild);if(T->rchild)LastOrder_RecTraverse(T->rchild);printf("%d ",T->data);}/*找到最左结点*/BBSTree GoFarLeft(BBSTree T, LStack &S){ if(NULL==T) return NULL;while(T->lchild!=NULL){Push_LS(S, T);T = T->lchild;}return T;}/*非递归中序遍历*/void InOrderTraverse_I(BBSTree T){LStack S;InitStack_LS(S);BBSTree p = NULL;p = GoFarLeft(T, S);while(p!=NULL){printf("%d ",p->data);if(p->rchild!=NULL){p = GoFarLeft(p->rchild, S);}else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S, p);else p = NULL;}}BBSTree VisitFarLeft(BBSTree T, LStack &S){if(NULL==T) return NULL; //如果T为空，则返回空printf("%d ",T->data); //先序，先读取结点数据while(T->lchild!=NULL){Push_LS(S, T); //入栈T = T->lchild; //遍历下一个左子树printf("%d ", T->data); //下一个结点的读取数据}return T;}/*非递归先序遍历*/void PreOrderTravese_I(BBSTree T){LStack S;InitStack_LS(S);BBSTree p;p = VisitFarLeft(T, S); //先将左边的数据先序读取while(p!=NULL){if(p->rchild!=NULL) //如果最左下结点的右子树不为空p = VisitFarLeft(p->rchild, S); //执行遍历该结点的左子树else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S,p); //如果S不为空栈，出栈else p = NULL; //如果为空栈，p赋予空}}/*非递归后序遍历*/void LastOrderTravese_I(BBSTree root){BBSTree p = root;BBSTree stack[30];int num=0;BBSTree have_visited = NULL;while(NULL!=p||num>0){while(NULL!=p){stack[num++]=p;p=p->lchild;}p=stack[num-1];if(NULL==p->rchild||have_visited==p->rchild){printf("%d ",p->data);num--;have_visited=p;p=NULL;}else{p=p->rchild;}}printf("\n");}/*非递归层次遍历输出一棵二叉树*/void LevelOrederTraverse_Print(BBSTree T){if(T==NULL){printf("The tree is empty!");}if(T!=NULL){LQueue Q;InitQueue_LQ(Q);BBSTree p = T;printf("%d ",p->data);EnQueue_LQ(Q,p);while(DeQueue_LQ(Q,p)){if(p->lchild!=NULL){printf("%d ", p->lchild->data);EnQueue_LQ(Q, p->lchild);}if(p->rchild!=NULL){printf("%d ", p->rchild->data);EnQueue_LQ(Q, p->rchild);}}}}/*括号表示法输出平衡二叉树*/void BraNotationPrint(BBSTree T){if(NULL==T){printf(" 空!");}else{if(T!=NULL){if(T!=NULL){printf("%i",T->data);if(T->lchild||T->rchild){printf("(");}}}if(T->lchild||T->rchild){if(T->lchild){BraNotationPrint(T->lchild);}else if(T->rchild){printf("#");}printf(",");if(T->rchild){BraNotationPrint(T->rchild);}else if(T->lchild){printf("#");}printf(")");}}}/*将一棵树转换为一个数组*/Array GetArrayFromTree(BBSTree T){Status firstTime = TRUE;Array head = NULL;ArrayNode *b = NULL;ArrayNode *q = NULL;if(T==NULL){printf("The tree is empty!");}if(T!=NULL){LQueue Q;InitQueue_LQ(Q);BBSTree p = T;q = (Array)malloc(sizeof(ArrayNode));q->data = p->data;if(firstTime==TRUE){head = q;firstTime = FALSE;b = q;}else{b->next = q;b = b->next;}EnQueue_LQ(Q,p);while(DeQueue_LQ(Q,p)){if(p->lchild!=NULL){q = (Array)malloc(sizeof(ArrayNode));q->data = p->lchild->data;b->next = q;b = b->next;EnQueue_LQ(Q, p->lchild);}if(p->rchild!=NULL){q = (Array)malloc(sizeof(ArrayNode));q->data = p->rchild->data;b->next = q;b = b->next;EnQueue_LQ(Q, p->rchild);}}if(b!=NULL){b->next = NULL;}}return head;}/*将两棵平衡二叉树合并成一颗平衡二叉树*/ BBSTree Combine2Tree(BBSTree T1, BBSTree T2){ Status taller = TRUE;Array a = NULL;a = GetArrayFromTree(T2);while(a!=NULL){taller = TRUE;InsertA VL(T1, a->data, taller);a = a->next;}return T1;}/*将一棵平衡二叉树分裂成两棵平衡二叉树*//*参数1：要进行分裂的树参数2：分裂出来的小于等于x的子树参数3：分裂出来的大于x的子树参数4：关键字x*/Status SplitBBSTree(BBSTree Tt1, BBSTree &Tt2, BBSTree &Tt3, int x){ Array a = NULL;Status taller;a = GetArrayFromTree(Tt1);if(Tt1==NULL) return FALSE;else{while(a!=NULL){if(a->data<=x){taller = TRUE;InsertA VL(Tt2, a->data, taller);a = a->next;}else {taller = TRUE;InsertA VL(Tt3, a->data, taller);a = a->next;}}}return TRUE;}4.测试(1)建树操作测试代码:测试数据：1 2 3 4 5 6测试结果：(2)插入操作测试代码：测试数据：1 2 3 4 5 6 插入8测试结果：测试数据：1 2 3 4 5 6 插入4测试结果：(3)删除操作测试代码：测试数据：1 2 3 4 5 6 删除6测试结果：测试数据：1 2 3 4 5 6 删除2测试结果：测试数据：1 2 3 4 5 6 删除4测试结果：(4)查找操作测试代码：测试数据：1 2 3 4 5 6 查找5测试结果：(5)输出测试代码：测试数据：1 2 3 4 5 6测试结果：5.思考与小结在完成平衡二叉树实验的过程中，所遇到的最大问题就是如何实现平衡二叉树删除结点的接口，因为课本没有涉及到这个知识点，所以自己只能通过阅读其他书籍和通过参考网上的资料来对这个过程有了进一步的理解。

数据结构实验报告二叉树数据结构实验报告：二叉树引言：数据结构是计算机科学中的重要基础，它为我们提供了存储和组织数据的方式。

二叉树作为一种常见的数据结构，广泛应用于各个领域。

本次实验旨在通过实践，深入理解二叉树的概念、性质和操作。

一、二叉树的定义与性质1.1 定义二叉树是一种特殊的树结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树可以为空树，也可以是由根节点和左右子树组成的非空树。

1.2 基本性质（1）每个节点最多有两个子节点；（2）左子树和右子树是有顺序的，不能颠倒；（3）二叉树的子树仍然是二叉树。

二、二叉树的遍历2.1 前序遍历前序遍历是指首先访问根节点，然后按照先左后右的顺序遍历左右子树。

在实际应用中，前序遍历常用于复制一颗二叉树或创建二叉树的副本。

2.2 中序遍历中序遍历是指按照先左后根再右的顺序遍历二叉树。

中序遍历的结果是一个有序序列，因此在二叉搜索树中特别有用。

2.3 后序遍历后序遍历是指按照先左后右再根的顺序遍历二叉树。

后序遍历常用于计算二叉树的表达式或释放二叉树的内存。

三、二叉树的实现与应用3.1 二叉树的存储结构二叉树的存储可以使用链式存储或顺序存储。

链式存储使用节点指针连接各个节点，而顺序存储则使用数组来表示二叉树。

3.2 二叉树的应用（1）二叉搜索树：二叉搜索树是一种特殊的二叉树，它的左子树上的节点都小于根节点，右子树上的节点都大于根节点。

二叉搜索树常用于实现查找、插入和删除等操作。

（2）堆：堆是一种特殊的二叉树，它满足堆序性质。

堆常用于实现优先队列，如操作系统中的进程调度。

（3）哈夫曼树：哈夫曼树是一种带权路径最短的二叉树，常用于数据压缩和编码。

四、实验结果与总结通过本次实验，我成功实现了二叉树的基本操作，包括创建二叉树、遍历二叉树和查找节点等。

在实践中，我进一步理解了二叉树的定义、性质和应用。

二叉树作为一种重要的数据结构，在计算机科学中有着广泛的应用，对于提高算法效率和解决实际问题具有重要意义。

数据结构设计性实验报告课程名称_____数据结构实验 _ 题目名称平衡二叉树学生学院__ 计算机学院______ 专业班级_学号____ ______学生姓名____ _ ___指导教师______ ____2015年6月14日目录一、设计任务、要求以及所用环境及工具 (4)实验设计任务 (4)实验要求 (4)编程环境 (4)抽象数据类型及接口简要描述 (5)抽象数据类型 (5)接口简要描述 (7)算法设计 (8)程序测试 (17)测试代码 (17)测试结果 (18)测试分析 (20)思考与小结 (21)一、设计任务、要求以及所用环境及工具实验设计任务以教材中讨论的各种抽象数据类型为对象，利用C语言的数据类型表示和实现其中某个注：如果基本操作数量较多，可选择实现其中一个基本操作子集。

实验要求实验要求如下：1．首先了解设计的任务，然后根据自己的基础和能力从中选择一题。

一般来说，选择题目应以在规定的时间内能完成，并能得到应有的锻炼为原则。

若学生对教材以外的相关题目较感兴趣，希望选作实验的题目时，应征得指导教师的认可，并写出明确的抽象数据类型定义及说明。

2. 实验前要作好充分准备，包括：理解实验要求，掌握辅助工具的使用，了解该抽象数据类型的定义及意义，以及其基本操作的算法并设计合理的存储结构。

3. 实验时严肃认真，要严格按照要求独立进行设计，不能随意更改。

注意观察并记录各种错误现象，纠正错误，使程序满足预定的要求，实验记录应作为实验报告的一部分。

4. 实验后要及时总结，写出实验报告，并附所打印的问题解答、程序清单，所输入的数据及相应的运行结果。

编程环境本次实验设计采用C++语言，在Microsoft Visual Studio2010 IDE下完成。

所创建的项目类型Win32控制台应用程序：抽象数据类型及接口简要描述本次数据结构实验设计我选择的是二叉平衡树（AVL），使用C++面向对象编程语言实现。

利用C++泛型编程技术完成AVL类AVLTree。

实习报告一、需求分析1、问题描述利用平衡二叉树实现一个动态查找表。

（1）实现动态查找表的三种基本功能：查找、插入和删除。

（2）初始时，平衡二叉树为空树，操作界面给出查找、插入和删除三种操作供选择。

每种操作均要提示输入关键字。

在查找时，如果查找的关键字不存在，则把其插入到平衡二叉树中。

每次插入或删除一个结点后，应更新平衡二叉树的显示。

（3）每次操作的关键字都要从文件中读取，并且关键字的集合限定为短整型数字{1，2，3······}，关键字出现的顺序没有限制，允许出现重复的关键字，并对其进行相应的提示。

（4）平衡二叉树的显示采用图形界面画出图形。

2、系统功能打开数据文件，用文件中的关键字来演示平衡二叉树操作的过程。

3、程序中执行的命令包括：（1）(L)oad from data file //在平衡的二叉树中插入关键字；（2）(A)ppend new record //在平衡的二叉树中查找关键字；（3）(U)pate special record //显示调整过的平衡二叉树；（4）(D)elete special record //删除平衡二叉树中的关键字；（5）(Q)uit //结束。

4、测试数据：平衡二叉树为：图 1 插入关键字10之前的平衡二叉树插入关键字：10；调整后：图 2 插入关键字10之后的平衡二叉树删除关键字：14；调整后：图 3 删除关键字14后的平衡二叉树查找关键字：11；输出：The data is here!图 3 查找关键字11后的平衡二叉树二、概要设计本次实验目的是为了实现动态查找表的三种基本功能：查找、插入和删除。

动态查找表可有不同的表示方法，在此次实验中主要是以平衡二叉树的结构来表示实现的，所以需要两个抽象数据类型：动态查找表和二叉树。

1、动态查找表的抽象数据类型定义为：ADT DynamicSearchTable{数据对象D ：D是具有相同特性的数据元素的集合。

实验5：树（二叉树）（采用二叉链表存储）一、实验项目名称二叉树及其应用二、实验目的熟悉二叉树的存储结构的特性以及二叉树的基本操作。

三、实验基本原理之前我们都是学习的线性结构，这次我们就开始学习非线性结构——树。

线性结构中结点间具有唯一前驱、唯一后继关系，而非线性结构中结点的前驱、后继的关系并不具有唯一性。

在树结构中，节点间关系是前驱唯一而后继不唯一，即结点之间是一对多的关系。

直观地看，树结构是具有分支关系的结构（其分叉、分层的特征类似于自然界中的树）。

四、主要仪器设备及耗材Window 11、Dev-C++5.11五、实验步骤1.导入库和预定义2.创建二叉树3.前序遍历4.中序遍历5.后序遍历6.总结点数7.叶子节点数8.树的深度9.树根到叶子的最长路径10.交换所有节点的左右子女11.顺序存储12.显示顺序存储13.测试函数和主函数对二叉树的每一个操作写测试函数，然后在主函数用while+switch-case的方式实现一个带菜单的简易测试程序，代码见“实验完整代码”。

实验完整代码：#include <bits/stdc++.h>using namespace std;#define MAX_TREE_SIZE 100typedef char ElemType;ElemType SqBiTree[MAX_TREE_SIZE];struct BiTNode{ElemType data;BiTNode *l,*r;}*T;void createBiTree(BiTNode *&T){ElemType e;e = getchar();if(e == '\n')return;else if(e == ' ')T = NULL;else{if(!(T = (BiTNode *)malloc(sizeof (BiTNode)))){cout << "内存分配错误!" << endl;exit(0);}T->data = e;createBiTree(T->l);createBiTree(T->r);}}void createBiTree2(BiTNode *T,int u) {if(T){SqBiTree[u] = T->data;createBiTree2(T->l,2 * u + 1);createBiTree2(T->r,2 * u + 2); }}void outputBiTree2(int n){int cnt = 0;for(int i = 0;cnt <= n;i++){cout << SqBiTree[i];if(SqBiTree[i] != ' ')cnt ++;}cout << endl;}void preOrderTraverse(BiTNode *T) {if(T){cout << T->data;preOrderTraverse(T->l);preOrderTraverse(T->r);}}void inOrderTraverse(BiTNode *T) {if(T){inOrderTraverse(T->l);cout << T->data;inOrderTraverse(T->r);}}void beOrderTraverse(BiTNode *T){if(T){beOrderTraverse(T->l);beOrderTraverse(T->r);cout << T->data;}}int sumOfVer(BiTNode *T){if(!T)return 0;return sumOfVer(T->l) + sumOfVer(T->r) + 1;}int sumOfLeaf(BiTNode *T){if(!T)return 0;if(T->l == NULL && T->r == NULL)return 1;return sumOfLeaf(T->l) + sumOfLeaf(T->r);}int depth(BiTNode *T){if(!T)return 0;return max(depth(T->l),depth(T->r)) + 1;}bool LongestPath(int dist,int dist2,vector<ElemType> &ne,BiTNode *T) {if(!T)return false;if(dist2 == dist)return true;if(LongestPath(dist,dist2 + 1,ne,T->l)){ne.push_back(T->l->data);return true;}else if(LongestPath(dist,dist2 + 1,ne,T->r)){ne.push_back(T->r->data);return true;}return false;}void swapVer(BiTNode *&T){if(T){swapVer(T->l);swapVer(T->r);BiTNode *tmp = T->l;T->l = T->r;T->r = tmp;}}//以下是测试程序void test1(){getchar();cout << "请以先序次序输入二叉树结点的值，空结点用空格表示:" << endl; createBiTree(T);cout << "二叉树创建成功!" << endl;}void test2(){cout << "二叉树的前序遍历为:" << endl;preOrderTraverse(T);cout << endl;}void test3(){cout << "二叉树的中序遍历为:" << endl;inOrderTraverse(T);cout << endl;}void test4(){cout << "二叉树的后序遍历为:" << endl;beOrderTraverse(T);cout << endl;}void test5(){cout << "二叉树的总结点数为：" << sumOfVer(T) << endl;}void test6(){cout << "二叉树的叶子结点数为：" << sumOfLeaf(T) << endl; }void test7(){cout << "二叉树的深度为：" << depth(T) << endl;}void test8(){int dist = depth(T);vector<ElemType> ne;cout << "树根到叶子的最长路径:" << endl;LongestPath(dist,1,ne,T);ne.push_back(T->data);reverse(ne.begin(),ne.end());cout << ne[0];for(int i = 1;i < ne.size();i++)cout << "->" << ne[i];cout << endl;}void test9(){swapVer(T);cout << "操作成功!" << endl;}void test10(){memset(SqBiTree,' ',sizeof SqBiTree);createBiTree2(T,0);cout << "操作成功!" << endl;}void test11(){int n = sumOfVer(T);outputBiTree2(n);}int main(){int op = 0;while(op != 12){cout << "-----------------menu--------------------" << endl;cout << "--------------1：创建二叉树--------------" << endl;cout << "--------------2：前序遍历----------------" << endl;cout << "--------------3：中序遍历----------------" << endl;cout << "--------------4：后序遍历----------------" << endl;cout << "--------------5：总结点数----------------" << endl;cout << "--------------6：叶子节点数--------------" << endl;cout << "--------------7：树的深度----------------" << endl;cout << "--------------8：树根到叶子的最长路径----" << endl;cout << "--------------9：交换所有节点左右子女----" << endl;cout << "--------------10：顺序存储---------------" << endl;cout << "--------------11：显示顺序存储-----------" << endl;cout << "--------------12：退出测试程序-----------" << endl;cout << "请输入指令编号:" << endl;if(!(cin >> op)){cin.clear();cin.ignore(INT_MAX,'\n');cout << "请输入整数!" << endl;continue;}switch(op){case 1:test1();break;case 2:test2();break;case 3:test3();break;case 4:test4();break;case 5:test5();break;case 6:test6();break;case 7:test7();break;case 8:test8();break;case 9:test9();break;case 10:test10();break;case 11:test11();break;case 12:cout << "测试结束!" << endl;break;default:cout << "请输入正确的指令编号!" << endl;}}return 0;}六、实验数据及处理结果测试用例：1.创建二叉树（二叉链表形式）2.前序遍历3.中序遍历4.后序遍历5.总结点数6.叶子结点数7.树的深度8.树根到叶子的最长路径9.交换所有左右子女10.顺序存储七、思考讨论题或体会或对改进实验的建议通过这次实验，我掌握了二叉树的顺序存储和链式存储，体会了二叉树的存储结构的特性，掌握了二叉树的树上相关操作。