数据结构课程设计-_平衡二叉树操作（共2篇）
一． 需求分析
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 —平衡二叉树加入新节点并调平
删除结点
六．心得体会
了解了建立树的方法；
学会了利用二分法建立树结构。、； 学习到了二叉树的调平方法；
学会了向一个已知树插入或删除结点的方法。
题目：
用先序递归过程监理二叉树（存储结构：二叉链表）
输入数据按先序遍历输入，当某节点左子树或者右子树为空时，输入‘*’号，如输入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指针的构造函数。可见，对于构造函数的含参调用应该小心谨慎。 【数据结构课程设计-_平衡二叉树操作】推荐阅读： 数据结构课程总结06-27 数据结构课程简介05-26 《数据结构》课程教学反思06-07 数据库技术与应用课程设计06-25 《电子商务数据库技术课程设计》报告格式06-29 数据结构和算法06-10 数据结构期末总结07-13 《数据结构》实验报告——排序05-30 实验数据结构与算法06-23 大学数据结构考研真题06-29
