第一篇：数据结构作业——二叉树
数据结构实验报告二
题目：
用先序递归过程监理二叉树（存储结构：二叉链表）
输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入abc**d**e**时，得到的二叉树为：
并用如下实力测试：
算法思路：
显然，建立一个二叉链表存储的二叉树，如果不考虑效率要求，考虑到程序的简介性，递归建立和递归遍历是一种很好的办法。
利用C++的类模板的方法实现建立，遍历，输出等二叉树操作。首先利用构造函数实现先序遍历建立二叉树，然后调用类模板中已经声明好的四种遍历函数，将遍历结果输出，检验建立好的二叉树是否为要求的二叉树。
初始化：利用构造函数建立二叉树。采用先序递归的调用方法，构造函数主体如下：
template
template
root = new BiNode
//生成一个结点 root->data=aa;
root->lchild = Creat();
//递归建立左子树
root->rchild = Creat();
//递归建立右子树
} return root;} 构造这样的函数，可以在输入时，按先序遍历顺序每次输入一个节点的数据，可以实现任意二叉树的构造。
为了检验构造的二叉树是否为预先设想的二叉树，需要遍历二叉树并进行输出。考虑到单一的输出并不能确定唯一的二叉树，因此对遍历二叉树的四种常用发方法，即先序遍历，中序遍历，后续遍历，层次遍历分别实现，通过遍历结果检验构造的二叉树是否为预先设计好的二叉树。
先序遍历：采用递归的方法建立。template
xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树
} 中序遍历：递归方法建立： template
if(root==NULL)return;
//如果节点为空，则返回空 else{ zhongxu(root->lchild);
//中序递归遍历root的左子树 cout<
//访问根结点
zhongxu(root->rchild);
//中序递归遍历root的右子树
}
} 后序遍历：递归方法建立： template
if(root==NULL)
return;
//如果节点为空，返回空 else{ houxu(root->lchild);
//后序递归遍历root的左子树 houxu(root->rchild);
//后序递归遍历root的右子树 cout<
//访问根节点
} } 层序遍历：采用非递归方法。利用队列的方法层序遍历二叉树。建立一个队列，在访问一个节点的时候，把它的左孩子和右孩子入队，并且将这个节点出队。当队列为空时，就完成了对二叉树的层序遍历。
template
Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear)
{
q = Q[front++];//只要队列不为空，则节点依次出队 cout<
if(q->lchild!= NULL)
Q[rear++] = q->lchild;
if(q->rchild!= NULL)
Q[rear++] = q->rchild;// 同时，该节点的双子入队
} } } 函数主体部分：声明一个类中的对象，调用构造函数，建立二叉树，并输出四种遍历结果，检验输出结果。
int main(){
BiTree
BiNode
cout<<“前序遍历序列为 ”< 程序结构： 主函数建立一个类模板定义构造函数，析构函数，以及成员函数声明类中的一个对象调用构造函数，构造一颗二叉树层序遍历二叉树后序遍历二叉树中序遍历二叉树前序遍历二叉树获取该二叉树的根节点将结果输出，人工检验 源代码： #include template { T data; BiNode template { public: BiTree(); //构造函数，初始化一棵二叉树 ~BiTree(void); //析构函数，释放二叉链表中各结点的存储空间 BiNode //获得指向根结点的指针 void xianxu(BiNode //前序遍历二叉树 void zhongxu(BiNode //中序遍历二叉树 void houxu(BiNode //后序遍历二叉树 void cengxu(BiNode //层序遍历二叉树 private: BiNode BiNode void Release(BiNode };template template if(aa==“*”)root = NULL; else{ root = new BiNode //生成一个结点 root->data=aa; root->lchild = Creat(); //递归建立左子树 root->rchild = Creat(); //递归建立右子树 } return root;} template template template else{ cout< xianxu(root->lchild);//先序遍历树的左子树 xianxu(root->rchild);//先序遍历树的右子树 } } template if(root==NULL)return; //如果节点为空，则返回空 else{ zhongxu(root->lchild); //中序递归遍历root的左子树 cout< //访问根结点 zhongxu(root->rchild); //中序递归遍历root的右子树 } } template if(root==NULL) return; //如果节点为空，返回空 else{ houxu(root->lchild); //后序递归遍历root的左子树 houxu(root->rchild); //后序递归遍历root的右子树 cout< //访问根节点 } } template const int MaxSize = 100;int front = 0;int rear = 0;//利用队列的方法对树进行层序遍历 BiNode BiNode else{ Q[rear++] = root;// 若节点不为空，则该节点入队 while(front!= rear) { q = Q[front++];//只要队列不为空，则节点依次出队 cout< if(q->lchild!= NULL) Q[rear++] = q->lchild; if(q->rchild!= NULL) Q[rear++] = q->rchild;// 同时，该节点的双子入队 } } } template if(root!= NULL){ Release(root->lchild); //释放左子树 Release(root->rchild); //释放右子树 delete root; } } int main(){ BiTree BiNode cout<<“前序遍历序列为 ”< cout<<“层序遍历序列为”< 通过对结果的分析，发现输出结果与建立二叉树时的输入完全符合，说明程序的运行结果是正确的。 心得体会： 1)函数递归的方法可以在相当程度上使程序简洁，避免代码的冗长复杂。2)构造函数如果带参数，在声明对象的时候应该将实参指出来。但是本题中构造函数位递归调用，初始的根节点的数据值由键盘输入，因此无法在声明对象时引入实参。所以最后选择了无参但是引用了this指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。 3)编程时，要不停得检验自己的输入与输出，必要的时候需要人工进行计算，以保证程序的运行按照预先的设想。 班级：计算机11-2 学号：40 姓名：朱报龙 成绩：_________ 实验七 二叉树操作验证 一、实验目的 ⑴ 掌握二叉树的逻辑结构； ⑵ 掌握二叉树的二叉链表存储结构； ⑶ 掌握基于二叉链表存储的二叉树的遍历操作的实现。 二、实验内容 ⑴ 建立一棵含有n个结点的二叉树，采用二叉链表存储； ⑵ 前序（或中序、后序）遍历该二叉树。 三、设计与编码 #include void inorder(void visit(BTreeNode void postorder(void visit(BTreeNode static void fun(BTreeNode data;}//访问结点 protected: BTreeNode //***********************建树******************************* template template //***********************遍历******************************* template {cout <<“递归先序遍历二叉树：”;s.preorder(s.fun);cout < 答：经常忘记对头结点的定义，以至于程序出错，经定义头结点，使程序正常运行。 b)程序运行的结果如何？ 四、实验小结 多练习，多上机，耐心调试程序，找出错误，多总结。 实验报告 课程名：数据结构（C语言版）实验名：二叉树的遍历 姓名： 班级： 学号： 时间：2014.11.03 一 实验目的与要求 1.掌握二叉树的存储方法 2.掌握二叉树的三种遍历方法 3.实现二叉树的三种遍历方法中的一种 二 实验内容 • 接受用户输入一株二叉树 • 输出这株二叉树的前根, 中根, 后根遍历中任意一种的顺序 三 实验结果与分析 //*********************************************************** //头文件 #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;CreateBiTree(T->lChild);CreateBiTree(T->rChild);} return(OK);} //********************************************************* void PreOrderTraverse(BiTree T){ //采用二叉链表存储结构，先序遍历二叉树的递归算法 if(T){ printf(“%c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);} } /***********************************************************/ void InOrderTraverse(BiTree T){ //采用二叉链表存储结构，中序遍历二叉树的递归算法 if(T){ InOrderTraverse(T->lChild);printf(“%c”,T->data);InOrderTraverse(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:二叉树的遍历运行结果 课 程 设 计 报 告 一． 需求分析 1、建立平衡二叉树并进行创建、增加、删除、调平等操作。 2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。 3、测试数据：自选数据 二． 概要设计 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下： ⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点； ⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； ⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整； ⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突； ⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。 三． 详细设计 树的内部变量 — 1 — typedef struct BTNode { int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子 }BTNode,*BTree;调平二叉树(左右调平方式大体雷同，之具体写出其中一种调平方式)if(插入元素与当前根元素相等){ printf(“已存在相同关键字的结点n”);} if(插入元素小于当前根元素)){ if(插入新结点不成功) return 0;if(插入成功) switch(查看根的平衡因子) { case +1: 进行左平衡处理; { 检查*T的左子树的平衡度，并作相应平衡处理 { case +1: 令根及其左孩子的平衡因子为0; 做右平衡处理; { BTree lc; lc指向的结点左子树根结点; rc的右子树挂接为结点的左子树; lc的右孩子为原结点; 原结点指向新的结点lc; } break; case-1: rd指向*T的左孩子的右子树根 switch(查看右孩子平衡因子) { case +1: 根的平衡因子为-1; 根左孩子的平衡因子为0; break; case 0: 令根和根左孩子的平衡因子为0;— 2 — } } } } break;根平衡因子为0;根左孩子平衡因子为1;break; case-1: 根右孩子的平衡因子为0;对*T的左子树作左旋平衡处理;对*T作右旋平衡处理;break;令根的平衡因子为+1;break;令根的平衡因子为-1;break;case 0: case-1: 四．调试分析 在进行对插入新结点并调平时由于利用的是普通的插入方法进行LL、LR、RL、RR型的转换，使得在调试时经常没有更改内部变量的值，导致编译出错。 对于在空树情况下删除结点的考虑，是在后期的调试检验过程中发现的。在没有更改代码前，如果按此操作，程序就会崩溃。原因就是在删除函数中虽然考虑到了空树的情况，但是在输出树的函数中没有加入空树的考虑而只是在创建树函数中加入了if…else…的判断。经过反复的检查，发现可以直接在输出函数中加入判断而不必再其他位置判断，并且调试成功。 五．使用说明和测试结果 测试数据： 创建二叉树 增加二叉树 直接创建平衡二叉树 — 4 —平衡二叉树加入新节点并调平 删除结点 六．心得体会 了解了建立树的方法； 学会了利用二分法建立树结构。、； 学习到了二叉树的调平方法； 学会了向一个已知树插入或删除结点的方法。 — 6 — 课 程 设 计 报 告 课程名称 数据结构课程设计 题 目平衡二叉树操作 指导教师 设计起止日 2010-5-16 学 院 计算机学院 专 业 软件工程 学生姓名 班级/学号------------成 绩 _________________ 一． 需求分析 1、建立平衡二叉树并进行创建、增加、删除、调平等操作。 2、设计一个实现平衡二叉树的程序，可进行创建、增加、删除、调平等操作，实现动态的输入数据，实时的输出该树结构。 3、测试数据：自选数据 二． 概要设计 平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是，则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。具体步骤如下： ⑴ 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值均不超过1，则平衡二叉树没有失去平衡，继续插入结点； ⑵ 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点； ⑶ 判断新插入的结点与最小不平衡子树的根结点的关系，确定是哪种类型的调整； ⑷ 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突； ⑸ 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后的平衡二叉树中是否存在平衡因子大于1的结点。 三． 详细设计 树的内部变量 typedef struct BTNode { — 2 — int data;int bf;//平衡因子 struct BTNode *lchild,*rchild;//左、右孩子 }BTNode,*BTree;调平二叉树(左右调平方式大体雷同，之具体写出其中一种调平方式)if(插入元素与当前根元素相等){ printf(“已存在相同关键字的结点n”);} if(插入元素小于当前根元素)){ if(插入新结点不成功) return 0;if(插入成功) switch(查看根的平衡因子) { case +1: 进行左平衡处理; { 检查*T的左子树的平衡度，并作相应平衡处理 { case +1: 令根及其左孩子的平衡因子为0; 做右平衡处理; { BTree lc; lc指向的结点左子树根结点; rc的右子树挂接为结点的左子树; lc的右孩子为原结点; 原结点指向新的结点lc; } break; case-1: rd指向*T的左孩子的右子树根 switch(查看右孩子平衡因子) { case +1: 根的平衡因子为-1; 根左孩子的平衡因子为0; break; case 0: 令根和根左孩子的平衡因子为0; break; case-1: } } } } 根平衡因子为0;根左孩子平衡因子为1;break; 根右孩子的平衡因子为0;对*T的左子树作左旋平衡处理;对*T作右旋平衡处理;break;令根的平衡因子为+1;break;令根的平衡因子为-1;break;case 0: case-1: 四．调试分析 在进行对插入新结点并调平时由于利用的是普通的插入方法进行LL、LR、RL、RR型的转换，使得在调试时经常没有更改内部变量的值，导致编译出错。 对于在空树情况下删除结点的考虑，是在后期的调试检验过程中发现的。在没有更改代码前，如果按此操作，程序就会崩溃。原因就是在删除函数中虽然考虑到了空树的情况，但是在输出树的函数中没有加入空树的考虑而只是在创建树函数中加入了if…else…的判断。经过反复的检查，发现可以直接在输出函数中加入判断而不必再其他位置判断，并且调试成功。 五．使用说明和测试结果 测试数据： 创建二叉树 — 4 — 增加二叉树 直接创建平衡二叉树 平衡二叉树加入新节点并调平 删除结点 — 6 — 六．心得体会 了解了建立树的方法； 学会了利用二分法建立树结构。、； 学习到了二叉树的调平方法； 学会了向一个已知树插入或删除结点的方法。七．附录 源代码 #include “stdafx.h” #include }BTNode,*BTree; /*需要的函数声明*/ void Right_Balance(BTree &p);void Left_Balance(BTree &p);void Left_Root_Balance(BTree &T);void Right_Root_Balance(BTree &T);bool InsertAVL(BTree &T,int i,bool &taller);void PrintBT(BTree T,int m);void CreatBT(BTree &T);void Left_Root_Balance_det(BTree &p,int &shorter);void Right_Root_Balance_det(BTree &p,int &shorter);void Delete(BTree q,BTree &r,int &shorter);int DeleteAVL(BTree &p,int x,int &shorter);void Adj_balance(BTree &T);bool SetAVL(BTree &T,int i,bool &taller);bool Insert_Balance_AVL(BTree &T,int i,bool &taller);/*主函数*/ void main(){ int input,search,m;bool taller=false;int shorter=0;BTree T;T=(BTree)malloc(sizeof(BTNode));T=NULL;while(1){ printf(“n请选择需要的二叉树操作n”);printf(“1.创建二叉树2.增加新结点3.直接创建平衡二叉树4.在平衡二叉树上增加新结点并调平衡5.scanf(”%d“,&input);getchar();switch(input){ case 1: CreatBT(T);break;printf(”请输入你要增加的关键字“);scanf(”%d“,&search);getchar();InsertAVL(T,search,taller);m = 0;PrintBT(T,m);break;Adj_balance(T);删除0.退出n”);case 2: case 3: — 8 — break; case 4: printf(“请输入你要增加的关键字”); scanf(“%d”,&search); getchar(); SetAVL(T,search,taller); m = 0; PrintBT(T,m); break; case 5: printf(“请输入你要删除的关键字”); scanf(“%d”,&search); getchar(); DeleteAVL(T,search,shorter); m=0; PrintBT(T,m); break; case 0: break; default: printf(“输入错误，请重新选择。”); break; } if(input == 0) break; printf(“按任意键继续.”); getchar();} } /*对以*p为根的二叉排序树作右旋处理*/ void Right_Balance(BTree &p){ BTree lc;lc = p->lchild;//lc指向的*p左子树根结点 p->lchild = lc->rchild;//rc的右子树挂接为*p的左子树 lc->rchild = p;p = lc;//p指向新的结点 } /*对以*p为根的二叉排序树作左旋处理*/ void Left_Balance(BTree &p){ BTree rc;rc = p->rchild;//指向的*p右子树根结点 p->rchild = rc->lchild;//rc左子树挂接到*p的右子树 rc->lchild = p;p = rc;//p指向新的结点 — 9 — } /*对以指针T所指结点为根的二叉树作左平衡旋转处理*/ void Left_Root_Balance(BTree &T){ } /*对以指针T所指结点为根的二叉树作右平衡旋转处理*/ void Right_Root_Balance(BTree &T){ BTree rc,ld;rc = T->rchild;//指向*T的左子树根结点 switch(rc->bf)//检查*T的右子树的平衡度，并作相应平衡处理 { case RH: //新结点插入在*T的右孩子的右子树上，要作单左旋处理 T->bf = rc->bf =EH;Left_Balance(T);break;ld = rc->lchild;//ld指向*T的右孩子的左子树根 switch(ld->bf)//修改*T及其右孩子的平衡因子 BTree lc,rd;lc = T->lchild;//指向*T的左子树根结点 switch(lc->bf)//检查*T的左子树的平衡度，并作相应平衡处理 { case LH: //新结点插入在*T的左孩子的左子树上，要作单右旋处理 } T->bf = lc->bf = EH;Right_Balance(T);break;rd = lc->rchild;//rd指向*T的左孩子的右子树根 switch(rd->bf)//修改*T及其左孩子的平衡因子 { case LH: } rd->bf = EH;Left_Balance(T->lchild);//对*T的左子树作左旋平衡处理 Right_Balance(T);//对*T作右旋平衡处理 T->bf = RH;lc->bf = EH;break;T->bf = lc->bf = EH;break;T->bf = EH;lc->bf = LH;break;case RH: //新结点插入在*T的左孩子的右子树上，要作双旋处理 case EH: case RH: case LH: //新结点插入在*T的右孩子的左子树上，要作双旋处理 — 10 — } } { case LH: } ld->bf = EH;Right_Balance(T->rchild);//对*T的右子树作左旋平衡处理 Left_Balance(T);//对*T作左旋平衡处理 T->bf = EH;rc->bf = RH;break;T->bf = rc->bf =EH;break;T->bf = LH;rc->bf = EH;break;case EH: case RH: /*插入结点i,若T中存在和i相同关键字的结点，则插入一个数据元素为i的新结点，并返回１，否则返回０*/ bool InsertAVL(BTree &T,int i,bool &taller){ if(!T)//插入新结点，树“长高”，置taller为true { } else { if(EQ(i,T->data))//树中已存在和有相同关键字的结点 { } if(LT(i,T->data))//应继续在*T的左子树中进行搜索 taller = false;printf(“已存在相同关键字的结点n”);return 0;T =(BTree)malloc(sizeof(BTNode));T->data = i;T->lchild = T->rchild =NULL;T->bf = EH;taller = true;{ if(!InsertAVL(T->lchild,i,taller))return 0;} else //应继续在*T的右子树中进行搜索 { if(!InsertAVL(T->rchild,i,taller))return 0; — 11 — } } return 1;} /*按树状打印输出二叉树的元素,m表示结点所在层次*/ void PrintBT(BTree T,int m){ } /*创建二叉树，以输入-32767为建立的结束*/ void CreatBT(BTree &T){ } int m;int i;bool taller=false;T = NULL;printf(“n请输入关键字(以-32767结束建立二叉树):”);scanf(“%i”,&i);getchar();while(i!=-32767){ } m=0;printf(“您创建的二叉树为：n”);PrintBT(T,m);InsertAVL(T,i,taller);printf(“n请输入关键字(以-32767结束建立二叉树):”);scanf(“%i”,&i);getchar();taller=false;if(T){ } else { } printf(“这是一棵空树！n”);getchar();int i;if(T->rchild)PrintBT(T->rchild,m+1);printf(“ ”);//打印i 个空格以表示出层次 for(i = 1;i<=m;i++)printf(“%dn”,T->data);//打印T 元素,换行 if(T->lchild)PrintBT(T->lchild,m+1);— 12 — /*删除结点时左平衡旋转处理*/ void Left_Root_Balance_det(BTree &p,int &shorter){ BTree p1,p2;if(p->bf==1)//p结点的左子树高，删除结点后p的bf减,树变矮 { } else if(p->bf==0)//p结点左、右子树等高，删除结点后p的bf减,树高不变 { } else //p结点的右子树高 { p1=p->rchild;//p1指向p的右子树 if(p1->bf==0)//p1结点左、右子树等高,删除结点后p的bf为-2,进行左旋处理，树高不变 { } else if(p1->bf==-1)//p1的右子树高，左旋处理后，树变矮 { } else //p1的左子树高,进行双旋处理(先右旋后左旋)，树变矮 { p2=p1->lchild;p1->lchild=p2->rchild;p2->rchild=p1;p->rchild=p2->lchild;p2->lchild=p;if(p2->bf==0){ } else if(p2->bf==-1){ p->bf=1;p1->bf=0;p->bf=0;p1->bf=0;Left_Balance(p);p1->bf=p->bf=0;shorter=1;Left_Balance(p);p1->bf=1;p->bf=-1;shorter=0;p->bf=-1;shorter=0;p->bf=0;shorter=1; } } } } else { } p2->bf=0;p=p2;shorter=1;p->bf=0;p1->bf=-1;/*删除结点时右平衡旋转处理*/ void Right_Root_Balance_det(BTree &p,int &shorter){ BTree p1,p2;if(p->bf==-1){ } else if(p->bf==0){ } else { p1=p->lchild;if(p1->bf==0){ } else if(p1->bf==1){ } else { p2=p1->rchild;Right_Balance(p);p1->bf=p->bf=0;shorter=1;Right_Balance(p);p1->bf=-1;p->bf=1;shorter=0;p->bf=1;shorter=0;p->bf=0;shorter=1;— 14 — 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) { p->bf=-1; p1->bf=0; } else { p->bf=0; p1->bf=1; } p2->bf=0; p=p2; shorter=1; } } } /*删除结点*/ void Delete(BTree q,BTree &r,int &shorter){ if(r->rchild==NULL){ q->data=r->data; q=r; r=r->lchild; free(q); shorter=1;} else { Delete(q,r->rchild,shorter); if(shorter==1) Right_Root_Balance_det(r,shorter);} } /*二叉树的删除操作*/ int DeleteAVL(BTree &p,int x,int &shorter){ } int k;BTree q;if(p==NULL){ } else if(x data)//在p的左子树中进行删除 { } else if(x>p->data)//在p的右子树中进行删除 { } else { } q=p;if(p->rchild==NULL)//右子树空则只需重接它的左子树 { } else if(p->lchild==NULL)//左子树空则只需重接它的右子树 { } else//左右子树均不空 { } return 1;Delete(q,q->lchild,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);p=q;p=p->rchild;free(q);shorter=1;p=p->lchild;free(q);shorter=1;k=DeleteAVL(p->rchild,x,shorter);if(shorter==1)Right_Root_Balance_det(p,shorter);return k;k=DeleteAVL(p->lchild,x,shorter);if(shorter==1)Left_Root_Balance_det(p,shorter);return k;printf(“不存在要删除的关键字！n”);return 0;— 16 — /*二叉树调平操作*/ void Adj_balance(BTree &T){ int m;int i;bool taller=false;T = NULL;printf(“n请输入关键字(以-32767结束建立平衡二叉树):”);scanf(“%d”,&i);getchar();while(i!=-32767){ SetAVL(T,i,taller); printf(“n请输入关键字(以-32767结束建立平衡二叉树):”); scanf(“%d”,&i); getchar(); taller=false;} m=0;printf(“平衡二叉树创建结束.n”);if(T) PrintBT(T,m);else printf(“这是一棵空树.n”);} /*调平二叉树具体方法*/ bool SetAVL(BTree &T,int i,bool &taller){ if(!T)//插入新结点，树“长高”，置taller为true { T =(BTree)malloc(sizeof(BTNode)); T->data = i; T->lchild = T->rchild =NULL; T->bf = EH; taller = true;} else { if(EQ(i,T->data))//树中已存在和有相同关键字的结点 { taller = false; printf(“已存在相同关键字的结点n”); return 0; } if(LT(i,T->data))//应继续在*T的左子树中进行搜索 { } } } if(!SetAVL(T->lchild,i,taller)) { } case LH: //原本左子树比右子树高，需要作左平衡处理 Left_Root_Balance(T);taller = false;break;T->bf = LH;taller = true;break;T->bf = EH;taller = false;break;return 0;switch(T->bf)//检查*T的平衡度 if(taller)//已插入到*T的左子树中且左子树“长高” case EH: //原本左子树、右子等高，现因左子树增高而使树增高 case RH: //原本右子树比左子树高，现左、右子树等高 else //应继续在*T的右子树中进行搜索 { } return 1;if(!SetAVL(T->rchild,i,taller)) { } case LH: //原本左子树比右子树高，现左、右子树等高 T->bf = EH;taller = false;break;T->bf = RH;taller = true;break;Right_Root_Balance(T);taller = false;break;return 0;switch(T->bf)//检查*T的平衡度 if(taller)//已插入到*T的右子树中且右子树“长高” case EH: //原本左子树、右子等高，现因右子树增高而使树增高 case RH: //原本右子树比左子树高，需要作右平衡处理 — 18 —第二篇：数据结构二叉树操作验证实验报告
第三篇：数据结构-二叉树的遍历实验报告
第四篇：数据结构课程设计-_平衡二叉树操作 - 副本
第五篇：数据结构课程设计-平衡二叉树操作
点击咨询 