广工数据结构课程设计完整版

广工数据结构课程设计完整版，包括源代码和实验报告

#include “bstree.h“

/*
   创建一棵带根结点的平衡二叉树
   若原先的二叉树不为空，先销毁原先的二叉树，再重新创建，并放回OK
*/
Status CreatAVL（BSTree &TStatus &taller）{
	ElemType e;
	int count = 0;
	if（T）    //判断平衡二叉树是否为空，若不空则将该树释放
	{
		printf（“\n之前创建的树还未被销毁，现在为你销毁>>>>>>>>>>>>\n“）;
		DestroyAVL（T）;
		T=NULL;
		printf（“销毁成功！\n\n“）;
	}
	printf（“\n■请输入要构造的平衡二叉树结点的关键字（输入0结束创建）:  “）;
	scanf（“%d“&e.key）;
	printf（“姓名：“）;
	scanf（“%s“e.name）;
	printf（“年龄：“）;
	scanf（“%d“&e.age）;
	while（e.key!=0）{
		count++;
		InsertAVL（Tetaller）;
		printf（“\n■请输入要构造的平衡二叉树结点的关键字（输入0结束创建）:  “）;
	    scanf（“%d“&e.key）;
	    printf（“姓名：“）;
	    scanf（“%s“e.name）;
	    printf（“年龄：“）;
	    scanf（“%d“&e.age）;
	}
	return count;
}

/*
   实现将结点e插入到二叉树的操作
   若二叉树中已经存在与e相同的结点，插入失败，放回FALSE
   否则插入成功，放回TRUE
*/
Status InsertAVL（BSTree &TElemType eStatus &taller）{
	if（NULL==T）{   //空树，树长高
		T = （BSTree）malloc（sizeof（BSTNode））; T->data = e;
		T->bf = EH; T->lchild = NULL; T->rchild = NULL; taller = TRUE;
	}
	else if（e.key == T->data.key）{  //存在和e相同的结点
		taller = FALSE; 
		return FALSE;//未插入
	}
	else if（e.keydata.key）{//插入到左边
		if（!InsertAVL（T->lchildetaller）） return FALSE;
		if（taller==TRUE）{
			switch（T->bf）{//检查T的平衡因子
			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（!InsertAVL（T->rchildetaller）） 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;
}

/*
   实现对树T的左平衡处理
*/
void LeftBalance（BSTree &T）{
	BSTree lcrd;
	lc = T->lchild;   //lc指向T的左孩子
	switch（lc->bf）{   //检查T的左孩子的平衡因子，并作相应的处理
	case LH://LL型，需要右旋转
		T->bf = lc->bf = EH; R_Rotate（T）; break;
	case RH://LR型，作双旋转
		rd = lc->rchild;
		switch（rd->bf）{//修改T及其左孩子的平衡因子
		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）;  //对T的左孩子作左旋转
		R_Rotate（T）;          //对T作右旋转
		break;
	}
}

/*
   实现对树T的右平衡处理
*/
void RightBalance（BSTree &T）{
	BSTree rcld;
	rc = T->rchild;
	switch（rc->bf）{
	case RH://RR型，需要左旋转
		T->bf = rc->bf = EH; L_Rotate（T）; break;
	case LH://新结点插入在T的右孩子的左子树上属于RL型，做双旋处理
		ld = rc->lchild;
		switch（ld->bf）{
		case LH:T->bf = EH; rc->bf = RH; break;
		case EH:rc->bf = T->bf = EH; break;
		case RH:T->bf = LH; rc->bf = EH; break;
		}
		ld->bf = EH;
		R_Rotate（T->rchild）;//对T的右孩子作右旋转调整
		L_Rotate（T）;        //对T作左旋转调整
		break;
	}
}

/*
   实现对最小失衡子树的左旋转调整
*/
void L_Rotate（BSTree &p）{
	BSTree rc = p->rchild;
	p->rchild = rc->lchild;
	rc->lchild = p;
	p = rc;
}

/*
   实现对最小失衡子树的右旋转调整
*/
void R_Rotate（BSTree &p）{
	BSTree lc = p->lchild;
	p->lchild = lc->rchild;
	lc->rchild = p;
	p = lc;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     目录           0  2016-01-05 09:16  数据结构课程设计\
     目录           0  2015-12-26 14:34  数据结构课程设计\Debug\
     文件       17759  2015-12-26 13:02  数据结构课程设计\Debug\bstree.obj
     文件       13915  2015-12-26 13:11  数据结构课程设计\Debug\main.obj
     文件       50176  2015-12-26 13:12  数据结构课程设计\Debug\vc60.idb
     文件       53248  2015-12-26 13:11  数据结构课程设计\Debug\vc60.pdb
     文件      184397  2015-12-26 13:11  数据结构课程设计\Debug\数据结构课程设计.exe
     文件      264240  2015-12-26 13:11  数据结构课程设计\Debug\数据结构课程设计.ilk
     文件      186988  2015-12-25 14:12  数据结构课程设计\Debug\数据结构课程设计.pch
     文件      476160  2015-12-26 13:11  数据结构课程设计\Debug\数据结构课程设计.pdb
     文件        8825  2015-12-26 12:52  数据结构课程设计\bstree.cpp
     文件        1365  2015-12-26 13:02  数据结构课程设计\bstree.h
     文件        3839  2015-12-26 13:11  数据结构课程设计\main.cpp
     文件        4516  2015-12-25 16:52  数据结构课程设计\数据结构课程设计.dsp
     文件         540  2015-12-25 13:20  数据结构课程设计\数据结构课程设计.dsw
     文件       50176  2015-12-26 13:31  数据结构课程设计\数据结构课程设计.ncb
     文件       48640  2015-12-26 13:31  数据结构课程设计\数据结构课程设计.opt
     文件        1338  2015-12-26 13:11  数据结构课程设计\数据结构课程设计.plg
     文件      446418  2016-01-05 09:16  数据结构课程设计\数据结构课程设计报告.docx