目 录
一、 需求分析 ........................................................................................................................... 1
1. 主功能模块 ................................................................................................................... 1
2. 创建树模块 ................................................................................................................... 1
3. 遍历树模块 ................................................................................................................... 1
二、 概要设计 ........................................................................................................................... 2
1. 功能设计 ....................................................................................................................... 2
（1） 创建二叉树 ....................................................................................................... 2
.
word 资料 平衡二叉树操作的演示
1. 需求分析
本程序是利用平衡二叉树，实现动态查找表的基本功能：创建表，查找、插入、删除。
具体功能：
（1） 初始，平衡二叉树为空树，操作界面给出创建、查找、插入、删除、合并、分裂六种操作供选择。每种操作均提示输入关键字。每次插入或删除一个结点后，更新平衡二叉树的显示。
（2） 平衡二叉树的显示采用凹入表现形式。
（3） 合并两棵平衡二叉树。
（4） 把一棵二叉树分裂为两棵平衡二叉树，使得在一棵树中的所有关键字都小于或等于x，另一棵树中的任一关键字都大于x。
如下图：
2．概要设计
平衡二叉树是在构造二叉排序树的过程中，每当插入一个新结点时，首先检查是否因插入新结点而破坏了二叉排序树的平衡性，若是则找出其中的最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。
.
word 资料 具体步骤：
（1） 每当插入一个新结点，从该结点开始向上计算各结点的平衡因子，即计算该结点的祖先结点的平衡因子，若该结点的祖先结点的平衡因子的绝对值不超过1，则平衡二叉树没有失去平衡，继续插入结点；
（2） 若插入结点的某祖先结点的平衡因子的绝对值大于1，则找出其中最小不平衡子树的根结点；
（3） 判断新插入的结点与最小不平衡子树的根结点个关系，确定是那种类型的调整；
（4） 如果是LL型或RR型，只需应用扁担原理旋转一次，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；如果是LR型或RL型，则需应用扁担原理旋转两次，第一次最小不平衡子树的根结点先不动，调整插入结点所在子树，第二次再调整最小不平衡子树，在旋转过程中，如果出现冲突，应用旋转优先原则调整冲突；
（5） 计算调整后的平衡二叉树中各结点的平衡因子，检验是否因为旋转而破坏其他结点的平衡因子，以及调整后平衡二叉树中是否存在平衡因子大于1的结点。
// 二叉树的层次遍历.cpp: 定义控制台应用程序的入口点。
//
#include "stdafx.h"
#include
#include
using namespace std;
//队列类的定义
template
struct LinkNode {
T data;
LinkNode *link;
LinkNode(LinkNode *ptr = NULL) {
link = ptr;
}
LinkNode(const T& item, LinkNode *ptr = NULL) {
data = item;
link = ptr;
}
};
template
class LinkedQueue
{
public:
LinkedQueue() { rear = front = new LinkNode; }
~LinkedQueue() { makeEmpty(); }
bool EnQueue(T x);
bool DeQueue(T& x);
bool getFront(T& x);
void makeEmpty();
bool IsEmpty() const { return front == rear; }
int getSize();
void output();
private:
LinkNode *front, *rear; //队头、队尾指针
};
template
bool LinkedQueue::EnQueue(T x)
{ //入队列，将新元素x插到队尾
if (front == NULL) return false;
rear->link = new LinkNode(x);
实 验 报 告
课程名称： 数据结构实验
实验项目： 二叉树的创建及遍历
姓 名：
专 业： 计算机科学与技术
班 级：
学 号：
计算机科学与技术学院
20 17年11 月 22 日 成绩：
哈尔滨理工大学计算机科学与技术学院 实验报告
实验项目名称： 二叉树的建立及遍历
一、实验目的
1.熟悉掌握课本二叉树相关理论知识
2.实践与理论相结合，掌握二叉树的应用程序
3.学会二叉树的创建，遍历等其他基本操作的代码实现
二、实验内容
1.二叉树的创建代码实现
2.二叉树先序、中序、后序遍历代码实现
三、实验操作步骤
1.二叉树的建立
（1）树节点的定义
由于每个节点都由数据域和指左子树和右子树的指针，故结构体封装如下：
typedef struct node
{
int data;
struct node *left;
struct node *right;
}Tree,*bitree;
（2）建立
采用递归的思想，先建立根再建立左子树，再建立右子树。递归截止条件子树为空，用-1代表树空
*T=(struct node *)malloc(sizeof(struct node));
哈尔滨理工大学计算机科学与技术学院实验教学中心 实验报告
(*T)->data=a;
printf("%d的左节点",a);
create(&(*T)->left);
printf("%d的右节点",a);
create(&(*T)->right);
2.三种遍历的实现
