一.课程设计题目及要求
（一）课程设计题目
用顺序和二叉链表作存储结构实现二叉排序树：
（1）以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
（2）对二叉排序树T作中序遍历，输出结果；
（3）输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作中序遍历(执行操作2)；否则输出信息“无x”。
（二）课程设计要求
在处理题目时，要求从分析题目的需求入手，按设计抽象数据类型、构思算法、通过设计实现抽象
数据类型、编制上机程序和上机调试等若干步骤完成题目，最终写出完整的分析报告。对于稍复杂
的程序设计，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，
考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。给出主要模块的算法描
述，用流程图或伪代码表示。说明：在设计的过程中，步骤1---步骤4往往是反复进行， 在后续步
骤中发现问题，往往需要从头重新分析、设计。
二.算法思想
（一）二叉排序树的定义
二叉排序树的定义：二叉排序树或者是一棵空树， 或者是一棵具有如下性质的二叉树：
(1)每个结点都有一个作为搜索依据的关键码（key），所有结点的关键码互不相同；
(2)若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
(3)若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
(4)左、右子树本身又各是一棵二叉排序树
（二）二叉排序树的实现
1.建立二叉排序树
建二叉树的结点至少应当包含三个域，分别存放结点的数据data，左子女结点指针leftChild和右子女结点指针rightChild。整个二叉树的链表要有一个表头指针，它指向二叉树的根结点，其作用是当作树的访问点
从空的二叉排序树开始，经过一系列的查找插入操作以后，生成了一棵二叉排序树。
根据二叉排序树的定义，建立一棵二叉排序树的过程是按照待排序序列元素的先后次序，不断动态生成二叉树的结点，逐个插入到二叉树中。若p为根结点指针，b为当前待插入元素，其过程可以描述为：
若为空树（p=NULL），动态生成一个结点，其数据域为当前待插入元素b，左、右指针域为“空”，p指向该结点。若非空树，比较b与根结点数据data（p）
如果b<data(p),将b插入左子树中；
如果b≥data(p)，将b插入右子树中；
左、右子树的插入方式与二叉排序树的插入方式相同。
不断调用上述的插入过程，直到所有待排序序列均排入后，就形成一棵二叉排序树。
由此可见，建立二叉排序树就是多次调用二叉排序树的插入算法。
2.二叉排序树的中序遍历
中序遍历二叉树算法的框架是：
若二叉树为空，则空操作；
否则 中序遍历左子树（L）；
访问根结点（V）；
中序遍历右子树（R）。
中序遍历二叉树也采用递归函数的方式，先访问左子树,然后访问根结点,最后访问右子树.直至所有的结点都被访问完毕
3.二叉排序树中元素的查找
在二叉排序树上进行查找，是一个从根结点开始，沿某一个分支逐层向下进行比较判等的过程。它
可以是一个递归的过程。假设我们想要在二叉排序树中查找关键码为x的元素，查找过程从根结点
开始。如果根指针为NULL，则查找不成功；否则用给定值x与根结点的关键码进行比较；如果给定
值等于根结点的关键码，则查找成功，返回查找成功的信息，并报告查找到的结点地址。如果给定
值小于根结点的关键码，则继续递归查找根结点的左子树；否则，递归搜索根结点的右子树。
4.二叉排序树中元素的查找
对于二叉排序树，删去树上的一个结点相当于删去有序序列中的一个记录，只要在删除某个结点之
后依旧保持二叉排序树的特性即可。假设在二叉排序树上被删除结点为*p（指向结点的指针是
p），其双亲结点为*f（结点指针为f），且不失一般性，可设*p是*f的左孩子，若*p结点为叶子结
点，即p和l均为空，只需修改其双亲结点指针即可。若*p结点只有左子树或者只有右子树，只要令
左子树或右子树直接成为其双亲结点即可。若左子树和右子树都不为空，令*p的直接前驱替代*p，
然后从二叉排序树中删除它的直接前驱，即可。
三.算法思想
（一）程序设计思想
程序主要设计了四个功能：首先是创建二叉排序树，完成后出现任务菜单，以数字代码确定，二叉
排序树的中序遍历和查找，删除步骤，最后完成，结束。
（二）程序模块
1.二叉链表结构（BST），C
#include
#include
typedef int ElementType;
typedef struct TNode *Position;
typedef Position BinTree;
struct TNode{
ElementType Data;
BinTree Left;
BinTree Right;
};
void PreorderTraversal( BinTree BST );
void InorderTraversal( BinTree BST );
BinTree Insert( BinTree BST, ElementType X);
BinTree Delete( BinTree BST, ElementType X);
Position Find( BinTree BST, ElementType X);
Position FindMin( BinTree BST );
Position FindMax( BinTree BST );
void solve( BinTree BST );
int calculateASL( BinTree BST,double*s,double *j,int i );
int main()
{
BinTree BST, MinP, MaxP, Tmp;
ElementType X;
int number,N, i;
BST = NULL;
scanf("%d", &N);
for ( i=0; i
scanf("%d", &X);
BST = Insert(BST, X);
}
printf("Preorder:"); PreorderTraversal(BST);printf("\n");
/*MinP = FindMin(BST);
MaxP = FindMax(BST);
scanf("%d", &N);
for( i=0; i
scanf("%d", &X);
Tmp = Find(BST, X);
if (Tmp == NULL) printf("%d is not found\n", X);
else {
printf("%d is found\n", Tmp->Data);
if (Tmp==MinP) printf("%d is the smallest key\n",Tmp->Data);
if (Tmp==MaxP) printf("%d is the largest key\n",Tmp->Data);
}
}
scanf("%d", &N);
for( i=0; i
scanf("%d", &X);
BST = Delete(BST, X);
}*/
printf("Inorder:"); InorderTraversal(BST);printf("\n");
double s=0,j=0;
int k=0;
calculateASL(BST,&s,&j,k);
printf("ASL=%0.4f\n",s/j);
solve(BST);
return 0;
}
void PreorderTraversal( BinTree BST )
{
if( BST ) {
printf(" %d", BST->Data);
PreorderTraversal( BST->Left );
PreorderTraversal( BST->Right );
}
}
void InorderTraversal( BinTree BST )
{
if( BST ) {
InorderTraversal( BST->Left );
printf(" %d", BST->Data);
InorderTraversal( BST->Right );
}
}
Position Find( BinTree BST, ElementType X )
{
if( !BST ) return NULL; /*查找失败*/
if( X > BST->Data ) {
return Find(BST->Right,X );/*在右子树中.继续查找*/
}
else if( X < BST->Data ){
return Find( BST->Left,X ); /*在左子树中继续查找*/
}
else /* X == BST->Data */
return BST; /*查找成功，返回结点的找到结点的地址*/
}
Position FindMin( BinTree BST )
{
if(BST){
while(BST->Left){
BST=BST->Left;
}
}
return BST;
}
Position FindMax( BinTree BST )
{
if(BST ){
while( BST->Right ){
BST = BST->Right;
}/*沿右分支继续查找，直到最右叶结点*/
}
return BST;
}
BinTree Insert( BinTree BST, ElementType X)
{
if( !BST ){ /*若原树为空，生成并返回一个结点的二叉搜索树*/
BST = (BinTree)malloc(sizeof(struct TNode));
BST->Data = X;
BST->Left = NULL;
BST->Right = NULL;
}
else { /*开始找要插入元素的位置*/
if( X < BST->Data )
BST->Left = Insert( BST->Left, X );/*递归插入左子树*/
elseif( X > BST->Data )
BST->Right = Insert( BST->Right,X ); /*递归插入右子树*/
/* else X已经存在，什么都不做*/
}
return BST;
}
BinTree Delete( BinTree BST, ElementType X) {
BinTree head=BST;
BinTree t=Find(BST,X);
if(!t) {
printf("Not Found\n");
return BST;
}
BinTree m=FindMax(t->Left);
if(m) {//左子树处理
t->Data=m->Data;
if(t->Left==m)t->Left=m->Left;
else {
t=t->Left;
while(t->Right!=m)t=t->Right;
t->Right=m->Left;
}
}else {
m=FindMin(t->Right);
if(m) {//左子树为空时
t->Data=m->Data;
if(t->Right==m)t->Right=m->Right;
else {
t=t->Right;
while(t->Left!=m)t=t->Left;
t->Left=m->Right;
}
} else { //当其为叶节点时
if(BST==t)return NULL;
while(BST) {
if(BST->Data>=t->Data){
if(BST->Left==t)BST->Left=NULL;
BST=BST->Left;
} else {
if(BST->Right==t)BST->Right=NULL;
BST=BST->Right;
}
}
}
}
// free(t);
return head;
}
void solve( BinTree BST )
{
ElementType X;
Position tmp;
printf("which element will you delete:");
scanf("%d",&X);
tmp = Find( BST,X );
if(tmp ==NULL)printf("thereis not X!\n");
else{
BST = Delete( BST, X );
InorderTraversal(BST);
}
}
int calculateASL(BinTree BST,double
*s,double *j,int i) /*计算平均查找长度*/
{
if(BST){
i++;
*s=*s+i;
if(calculateASL(BST->Left,s,j,i)){
(*j)++;
if(calculateASL(BST->Right,s,j,i)){
i--;
return(1);
}
}
}
else return(1);
2.顺序存储（BST）,C
#include"stdio.h"
#include"malloc.h"
#include"windows.h"
#define endflag 999999
#define N 1000
int b[N];
typedef struct
{
intdata;
intother;
intflag1;
}Link;
void Build(Link a[N])
{
intw,i,j,k;
for(i=0;i<=N;i++){
a[i].flag1=0;
a[i].data=0;
}
printf("\n\t\t\t请输入树的根结点:");
scanf("%d",&a[1].data);
a[1].flag1=1;
printf("\n\t\t\t请输入结点个数:");
scanf("%d",&k);
for(j=1;j<=k;j++){
printf("\n\t\t\t请输入结点的数值:");
scanf("%d",&w);
printf("\n\t\t\t第%d位: %d",j,w);
a[0].data=w;
a[0].flag1=1;
i=1;
if(a[0].data
loop:if(a[2*i].flag1==0){
a[2*i].data=a[0].data;
a[2*i].flag1=a[0].flag1;
}
if(a[2*i].flag1==1){
i=2*i;
if(a[0].data
if(a[0].data>a[i].data)goto loop1;
}
}
if(a[0].data>a[i].data){
loop1:if(a[2*i+1].flag1==0){
a[2*i+1].data=a[0].data;
a[2*i+1].flag1=a[0].flag1;
}
if(a[2*i+1].flag1==1){
i=2*i+1;
if(a[0].data
gotoloop;
if(a[0].data>a[i].data)
gotoloop1;
}
}
}
}
void Sdel(Link a[N])
{
inti,flag=0,q,number=1,j=1;
printf("\n\t\t\t请输入需要删除的结点的数值:");
scanf("%d",&q);
for(i=1;i<=N;i++)
if(a[i].data==q){
a[i].data=0;
printf("\n\t\t\t已删除%d: ",q);
flag=1;
for(i=1;i<=N;i++){
if(a[i].data!=0){
b[j]=a[i].data;
j++;
number++;
}
}
for(i=1;i<=N;i++){
a[i].flag1=0;
a[i].data=0;
}
a[1].data=b[1];
a[1].flag1=1;
for(j=2;j<=number-1;j++){
a[0].data=b[j];
a[0].flag1=1;
i=1;
if(a[0].data
loop:if(a[2*i].flag1==0){
a[2*i].data=a[0].data;
a[2*i].flag1=a[0].flag1;
}
if(a[2*i].flag1==1){
i=2*i;
if(a[0].data
if(a[0].data>a[i].data)goto loop1;
}
}
if(a[0].data>a[i].data){
loop1:if(a[2*i+1].flag1==0){
a[2*i+1].data=a[0].data;
a[2*i+1].flag1=a[0].flag1;
}
if(a[2*i+1].flag1==1){
i=2*i+1;
if(a[0].data
if(a[0].data>a[i].data)goto loop1;
}
}
}
printf("\n\t\t\t显示已经删除结点后的数据\n");
for(i=1;i
if(a[i].data!=0){
printf("\n\t\t\t位于二叉排序树的第%d位的数据为: ",i);
printf("->%d\n\n",a[i].data);
}
}
}
if(flag==0)printf("\n\n\n\t\t\t不存在该结点，不能删除\n");
}
int main()
{
inti,flag=0,ch=0;
Linka[N];
printf("\n1:建立二叉排序树并中序遍历输出");
printf("\n2:输入一个元素，删除后重构二叉排序树并中序输出");
while(ch==ch){
scanf("%d",&ch);
switch(ch){
case0:exit(0);
case1:printf("\t\t\t请输入信息\n");
Build(a);
printf("\n");
for(i=1;i
if(a[i].data!=0){
printf("\n\t\t\t位于二叉排序树的第%d位的数值为:",i);
printf("->%d\n\n",a[i].data);
}
}
case2:printf("输入元素x，查找二叉排序树T,若存在含x的结点，则删除该结点并作中序遍历，否则输出无x:");
Sdel(a);
break;
default:
printf("无此结点\n");
break;
}
}
return0;
}
3.二叉链表（AVL）,C
#include
#include
#include
#include
using namespace std;
typedef struct TreeNode *AvlTree;
typedef struct TreeNode *Position;
struct TreeNode
{
int Data;
AvlTree Left;
AvlTree Right;
int Height;
};
void PreorderTraversal( AvlTree AVL )
{
if( AVL ) {
printf("%d ", AVL->Data);
PreorderTraversal( AVL->Left );
PreorderTraversal( AVL->Right);
}
}
void InorderTraversal( AvlTree AVL )
{
if( AVL ) {
InorderTraversal( AVL->Left );
printf("%d ", AVL->Data);
InorderTraversal( AVL->Right);
}
}
int calculateASL(AvlTree AVL,double
*s,double *j,int i) /*计算平均查找长度*/
{
if(AVL){
i++;
*s=*s+i;
if(calculateASL(AVL->Left,s,j,i)){
(*j)++;
if(calculateASL(AVL->Right,s,j,i)){
i--;
return(1);
}
}
}
else return(1);
}
AvlTree Insert(int x, AvlTree T);//插入新节点，必要时调整
Position SingleRotateWithLeft(Positiona);//左单旋
Position SingleRotateWithRight(Positionb);//右单旋
Position DoubleRotateWithLeft(Positiona);//左右旋
Position DoubleRotateWithRight(Positionb);//右左旋
int Max(int x1, int x2);//返回两个int中较大的
int Height(Position P);//返回一个节点的高度
int main()
{
int n, x;
AvlTree T = NULL;
scanf("%d", &n);
for (int i = 0; i < n; i++)
{
scanf("%d", &x);
T = Insert(x, T);
}
printf("Preorder:");
PreorderTraversal(T);printf("\n");
printf("Inorder:");
InorderTraversal(T);printf("\n");
///printf("%d\n", T->Data);//打印根节点的值
double s=0,j=0;
int k=0;
calculateASL(T,&s,&j,k);
printf("ASL=%0.4f\n",s/j);
return 0;
}
AvlTree Insert(int x, AvlTree T)
{
if (T == NULL)
{
T = (AvlTree)malloc(sizeof(struct TreeNode));
T->Data = x;
T->Left = T->Right = NULL;
T->Height = 0;
}
else if (x < T->Data)//向左子树插入
{
T->Left = Insert(x, T->Left);
if (Height(T->Left) - Height(T->Right) == 2)//需调整
{
if (x < T->Left->Data)
T = SingleRotateWithLeft(T);
else
T = DoubleRotateWithLeft(T);
}
}
else if (x > T->Data)//向右子树插入
{
T->Right = Insert(x, T->Right);
if (Height(T->Right) - Height(T->Left) == 2)//需调整
{
if (x >T->Right->Data)
T = SingleRotateWithRight(T);
else
T = DoubleRotateWithRight(T);
}
}
/*else值为x的节点已经存在树中，无需插入*/
/*更新节点高度*/
T->Height = Max(Height(T->Left), Height(T->Right)) + 1;
return T;
}
Position SingleRotateWithLeft(Position a)
{
Position b = a->Left;
a->Left = b->Right;
b->Right = a;
//更新a, b节点高度
a->Height = Max(Height(a->Left), Height(a->Right)) + 1;
b->Height = Max(Height(b->Left), Height(b->Right)) + 1;
return b;/*新的根节点*/
}
Position SingleRotateWithRight(Position b)
{
Position a = b->Right;
b->Right = a->Left;
a->Left = b;
//更新a,b节点高度
a->Height = Max(Height(a->Left), Height(a->Right)) + 1;
b->Height = Max(Height(b->Left), Height(b->Right)) + 1;
return a;/*新的根节点*/
}
Position DoubleRotateWithLeft(Position a)
{
a->Left = SingleRotateWithRight(a->Left);
return SingleRotateWithLeft(a);
}
Position DoubleRotateWithRight(Position b)
{
b->Right = SingleRotateWithLeft(b->Right);
return SingleRotateWithRight(b);
}
int Max(int x1, int x2)
{
return (x1 > x2) ? x1 : x2;
}
int Height(Position P)
{
if (P == NULL)//空节点高度为-1
return -1;
return P->Height;
}
四.算法思想
（一）程序调试
（1）二叉链表存储（BST）：
（2）顺序存储(BST)：
（3）二叉链表存储（AVL）
（二）测试结果分析
输入一串数据，进行中序遍历，输入元素x,查找二叉排序树T,若存在含x的结点,则删除该结点,并作
中序遍历(执行操作2)；否则输出信息“无x”。验证结果正确，说明其符合算法设计的要求：(1)正确
性、可读性、健壮性、效率与低储存量需求.要写一个优质的算法，就必须考虑其时间复杂度（它
表示随问题的规模n的增大，算法执行时间的增长率和f（n）的增长率相同）和空间复杂度。遍历
二叉树的算法中的基本操作是访问结点，则不论按那一次次序进行遍历，对含n个结点的二叉树，
其时间复杂度为O（n）。所需辅助空间为遍历过程中栈的最大容量，即树的深度log(n)，最坏情况
下为n，则空间复杂度也为O（n）。
网友评论