数据结构实验十

9i/n/Hoz:曜a09++OA:蜴燮将丁旱里++。：星里浦零岖二凰去朝丽阿7敌工可爵：亦牟frSIZflOZ:备秦暮熟：gW4■魏物弱麟•实验内容建立排序平衡二叉树。输入与输出输入：输入一组节点，从而建立平衡排序二叉树。输出：输出平衡二叉树的先序，中序遍历，以及每个节点的平衡因子，以便进行还原二叉树的形状，判断算法是否正确。关键数据结构与核心算法关键数据结构：因为是二叉树，则要有基本的节点，左右孩子指针，因为要排序旋转，则要知道平衡因子，注意此处可以根据需要来添加双亲指针，因为运用了引用，则省去了此处。因此数据结构为：typedefstructBSTNode{intdata;//信息intbf;//平衡因子structBSTNode*lchild,*rchild;〃平衡树左右儿子指针}BSTNode,*BSTree;//平衡二叉排序树结构的定义核心算法:建立平衡排序二叉树算是算法中比较复杂的一个了，但是找到核心之后，也就只是比较复杂一些罢了，多练习一下即可。那核心是什么呢？要回答这个问题，就要深刻理解“平衡”和“排序"两个词的含义。顾名思义，平衡二叉树加上排序二叉树即是所要建的树。1.平衡二叉树要求每一个节点的左子树深度减去右子树的深度的绝对值要小于1。2.排序二叉树要求按照中序遍历该二叉树得到从小到大排序的序列。因此在每插入一个结点的时候都要判断是否平衡，1・若平衡则按照排序二叉树的方法插入之，然后刷新平衡因子即可。2.重要是不平衡的时候就要从最接近的不平衡的地方旋转的让它平衡，这样继续下去，不断插入就可以得到排序平衡二叉树。下面主要解释一下旋转方法：旋转共有4种方式，其实，最核心的只有两种基本操作即是L_Rotate()和R_Rotate()，分别是左旋和右旋。对于LL型，即是最先出错的节点平衡因子是2,左儿子平衡因子是1，运用一次右旋操作再刷新平衡因子即可。根据镜像对称原则，RR型与此是对应的，如法炮制即可。重要的并且复杂的是LR和RL操作，这两个操作也是镜像对称的只讲一个即可。就比如LR吧，最先出错的节点的平衡因子是2,该节点的左孩子的平衡因子是・1・则要对左孩子为根的子树进行左旋，然后对该最近节点进行右旋，刷新平衡因子即可。具体算法如下：■&s s s s s ■Ji*ZX-&&&&&&&&&&&&&&，/,mmmm*.两个基本操作ummmm*/voidL_Rotate(BSTree&p){〃对以*p为根的二叉排序树做左旋处理，处理之后p指向新的树根结点//和R_Rotate()镜像对称BSTreerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}voidR_Rotate(BSTree&p){〃对以*p为根的二叉排序树做右旋处理，处理之后p指向新的树根结点//注意此处引用的好处就是不用再出现双亲指针BSTreelc;lc=p->lchild;〃指向B的位置p->lchild=lc->rchild;/此处转换仍保持中序遍历不变性lc->rchild=p;//更改a的指针位置p=lc;//lc变成新的a/**********************四个旋转操作，每两个在一起*****************/〃包含LL和LRvoidLeftBalance(BSTree&T){〃对已叮为根的二叉排序树做左平衡旋转处理BSTreelc,rd;lc=T->lchild;//lc调整左边switch(lc->bf){caseLH://若是左边高则为LL型，只需旋转即可T->bf=lc->bf=EH;//旋转后平衡因子均为0R_Rotate(T);//LL型需要右旋转break;case皿://若是右边高，则为LR型，需分两步调整rd=lc->rchild;//找到不确定因子rdswitch(rd->bf)//对不确定因子进行讨论{case］日:〃左边高调整后T->bf=RH;//根节点右边变高lc->bf=EH;//lc变平衡break;caseEH://rd有左右节点T->bf=lc->bf=EH;//调整后持平break;case皿:〃右边高T->bf=EH;//根节点平衡lc->bf=LH;//lc节点变成左边高break;}rd->bf=EH;〃调整后rd节点一定平衡，且变成新的头节点L_Rotate(T->lchild);//1.先左旋R_Rotate(T); //2.再右旋}}/*************右平衡操作，包含RR和RL*******************************/voidRightBalance(BSTree&T){〃对已*丁为根的二叉排序树做右平衡旋转处理〃因为为LeftBalance(BSTree&丁)的镜像，注释则省略BSTreelc,rd;lc=T->rchild;switch(lc->bf){case皿:〃右边高，RR型T->bf=lc->bf=EH;L_Rotate(T);break;caseLHd/左边高，RL型，分两步旋转rd=lc->lchild;switch(rd->bf){caseRH:T->bf=LH;lc->bf=EH;break;caseLH:T->bf=EH;lc->bf=RH;break;caseEH:T->bf=lc->bf=EH;break;}rd->bf=EH;R_Rotate(T->rchild);〃1先右旋L_Rotate(T); //2.再左旋}} 至于插入操作主要就是判断树是不是平衡，若不平衡是左边还是右边，对于添加的新节点改变了树的平衡了没有，改变了左边的还是右边的，然后进行相应的旋转处理。具体算法如下：intInsertAVL(BSTree&T,intkey,bool&taller){//若在平衡二叉排序树中不存在与关键字key相等的结点，则将关键字插入树中//布尔变量taller表示树是否“长高”if(T==NULL){T=(BSTree)malloc(sizeof(BSTNode));T->data=key;T->bf=EH;//叶子结点其平衡因子肯定为0T->lchild=T->rchild=NULL;taller=1;//树长高了}else{if(key==T->data){//如果树中已存放此关键字则不予插入taller=0;return0;}if(key<T->data){〃关键字小于根结点则插入其左子树中if(!InsertAVL(T->lchild,key,taller))return0;if(taller){//如果树长高了，判断是否平衡switch(T->bf){caseLHd/若左边高，这次又加上一个左边的节点，则肯定变为2,即需要调整LeftBalance(T);//不平衡时调用左平衡函数，使左子树平衡taller=0;break;caseEH://若相等，在左边加一个节点，则变为左边高T->bf=LH;taller=1;〃树变高break;case皿://若右边高，在左边加一个节点，则持平T->bf=EH;taller=0;break;}}}else{//插入右子树中if(!InsertAVL(T->rchild,key,taller))return0;if(taller){switch(T->bf){caseLH://同理，本来左边高，在右边加一个节点则持平T->bf=EH;taller=0;break;caseEH://右边变高T->bf=RH;taller=1;break;case皿://右边不平衡了，需要调整RightBalance(T);taller=0;break;}}}}return1;}理论与测试理论：如图，给定一个序列的节点数组，按照几种变换规则得到了图示的排序二叉树，可以得到三序遍历和平衡因子。（由于图形比较多，暂时为手工画图）该序列为：47,63,54,28,31,14,26,53,99,81先序遍历：31，26，14,28,54,47,53,81，63，99中序遍历：14,26,28,31,47,53,54,63,81,99平衡因子：31和47的平衡因子为-1，其他的都为0测试：运行程序之后输出为:

由先序和中序序列可以还原出树的原型，对照可知结果是正确的。讨论与体会排序二叉树的中序遍历结果即为升序排列，但是运算速率不是最高的，为了寻找更好的方法，平衡排序二叉树便诞生了。对于开创者而言这是令人称赞的，但是对于后学者来说，在学习算法的核心思想的同时，更重要的是别人是怎样想到的，当一个现实生活的需要放在眼前是，我们要有开创的眼光，具有创新能力，这点是非常重要的，因为对于应用上来说有了第一个其他的就不再令人惊奇了。同时，递归，引用，开关、选择分支语句的运用也要引起注意。学习图的最好方法，就是数形结合，一定要多画图。六・附录（源代码）#include<stdio.h>#include<stdlib.h>#include<iostream>usingnamespacestd;#defineLH1//左边高#defineEH0//一样高#defineRH-Uf右边高typedefstructBSTNode{int《2也;〃信息intbf;//平衡因子structBSTNode*lchild,*rchild;〃平衡树左右儿子指针}BSTNode,*BSTree;//平衡二叉排序树结构的定义voidR_Rotate(BSTree&p){〃对以*p为根的二叉排序树做右旋处理，处理之后p指向新的树根结点//注意此处引用的好处就是不用再出现双亲指针BSTreelc;lc=p->lchild;//指向B的位置p->lchild=lc->rchild;//此处转换仍保持中序遍历不变性lc->rchild=p;//更改a的指针位置p=lc;//lc变成新的a}voidL_Rotate(BSTree&p){〃对以*p为根的二叉排序树做左旋处理，处理之后p指向新的树根结点//和R_Rotate()镜像对称BSTreerc;rc=p->rchild;p->rchild=rc->lchild;rc->lchild=p;p=rc;}〃包含LL和LRvoidLeftBalance(BSTree&T){〃对已叮为根的二叉排序树做左平衡旋转处理BSTreelc,rd;lc=T->lchild;//lc调整左边switch(lc->bf){caseLH://若是左边高则为LL型，只需旋转即可T->bf=lc->bf=EH;/旋转后平衡因子均为0R_Rotate(T);//LL型需要右旋转break;case皿://若是右边高，则为LR型，需分两步调整rd=lc->rchild;//找到不确定因子rdswitch(rd->bf)//对不确定因子进行讨论case1日:〃左边高调整后T->bf=RH;//根节点右边变高lc->bf=EH;//lc变平衡break;caseEH://rd有左右节点T->bf=lc->bf=EH;/调整后持平break;case皿:〃右边高T->bf=EH;//根节点平衡lc->bf=LH;//lc节点变成左边高break;}rd->bf=EH;//调整后rd节点一定平衡，且变成新的头节点L_Rotate(T->lchild);//1先左旋R_Rotate(T); 〃2.再右旋/*************右平衡操作，包含RR和rl*******************************/voidRightBalance(BSTree&T){〃对已*T为根的二叉排序树做右平衡旋转处理〃因为为LeftBalance(BSTree&丁)的镜像，注释则省略BSTreelc,rd;lc=T->rchild;switch(lc->bf){case皿:〃右边高，RR型T->bf=lc->bf=EH;L_Rotate(T);break;caseLHd/左边高，RL型，分两步旋转rd=lc->lchild;switch(rd->bf){caseRH:T->bf=LH;lc->bf=EH;break;caseLH:T->bf=EH;lc->bf=RH;break;caseEH:T->bf=lc->bf=EH;break;}rd->bf=EH;R_Rotate(T->rchild);111先右旋L_Rotate(T); //2.再左旋}}intInsertAVL(BSTree&T,intkey,bool&taller){//若在平衡二叉排序树中不存在与关键字key相等的结点，则将关键字插入树中//布尔变量taller表示树是否“长高”if(T==NULL){T=(BSTree)malloc(sizeof(BSTNode));T->data=key;T->bf=EH;//叶子结点其平衡因子肯定为0T->lchild=T->rchild=NULL;taller=1;//树长高了}else{if(key==T->data){//如果树中已存放此关键字则不予插入taller=0;return0;}if(key<T->data){〃关键字小于根结点则插入其左子树中if(!InsertAVL(T->lchild,key,taller))return0;if(taller){//如果树长高了，判断是否平衡switch(T->bf){case1任//若左边高，这次又加上一个左边的节点，则肯定变为2,即需要调整LeftBalance(T);//不平衡时调用左平衡函数，使左子树平衡taller=0;break;caseEH://若相等，在左边加一个节点，则变为左边高T->bf=LH;taller=1;//树变高break;case皿://若右边高，在左边加一个节点，则持平T->bf=EH;taller=0;break;}}else{//插入右子树中if(!InsertAVL(T->rchild,key,taller))return0;if(taller){switch(T->bf){caseLH://同理，本来左边高，在右边加一个节点则持平T->bf=EH;taller=0;break;caseEH://右边变高T->bf=RH;taller=1;break;case皿: