数据结构c语言课设-二叉树排序
- 格式：docx
- 大小：90.15 KB
- 文档页数：15
题目:二叉排序树的实现
1 内容和要求
1） 编程实现二叉排序树， 包括生成、插入，删除；
2） 对二叉排序树进展先根、中根、 和后根非递归遍历；
3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4） 分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),比照查找效率，并说明在什么情况下二叉排序树效率高,为什么?
2 解决方案和关键代码
2.1 解决方案：
先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。
前中后根遍历需要用到栈的数据构造，分模块编写栈与遍历代码。
要求比照二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock〔〕函数记录查找时间来比照查找效率。
2.2关键代码
树的根本构造定义及根本函数
typedef struct
{
KeyType key;
} ElemType;
typedef struct BiTNode //定义链表
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree, *SElemType;
//销毁树
int DestroyBiTree(BiTree &T)
{
if (T != NULL)
free(T); return 0;
}
//清空树
int ClearBiTree(BiTree &T)
{
if (T != NULL)
{
T->lchild = NULL;
T->rchild = NULL;
T = NULL;
}
return 0;
}
//查找关键字,指针p返回
int SearchBST(BiTree T, KeyType
key, BiTree f, BiTree &p)
{
if (!T)
{
p = f;
return FALSE;
}
else
if EQ(key, T->data.key)
{
p = T;
return TRUE;
}
else if LT(key, T->data.key)
return SearchBST(T->lchild, key, T, p);
else
return SearchBST(T->rchild, key, T, p);
}
二叉树的生成、插入，删除
生成
void CreateBST(BiTree &BT, BiTree p)
{
int i;
ElemType k;
printf("请输入元素值以创立排序二叉树:\n");
scanf_s("%d", &k.key);
for (i = 0; k.key != NULL; i++)
{
//判断是否重复 if (!SearchBST(BT, k.key, NULL, p))
{
InsertBST(BT, k);
scanf_s("%d", &k.key);
}
else
{
printf("输入数据重复！\n");
return;
}
}
}
插入
int InsertBST(BiTree &T,
ElemType e)
{
BiTree s, p;
if (!SearchBST(T, e.key, NULL, p))
{
s = (BiTree)malloc(sizeof(BiTNode));
s->data = e;
s->lchild = s->rchild = NULL;
if (!p)
T = s;
else if LT(e.key, p->data.key)
p->lchild = s;
else
p->rchild = s;
return TRUE;
}
else return FALSE;
}
删除
//某个节点元素的删除
int DeleteEle(BiTree &p)
{
BiTree q, s;
if (!p->rchild) //右子树为空
{
q = p;
p = p->lchild;
free(q);
}
else if (!p->lchild) //左子树为空
{ q = p;
p = p->rchild;
free(q);
}
else
{
q = p;
s = p->lchild;
while (s->rchild)
{
q = s;
s = s->rchild;
}
p->data = s->data;
if (q != p)
q->rchild = s->lchild;
else
q->lchild = s->lchild;
delete s;
}
return TRUE;
}
//整棵树的删除
int DeleteBST(BiTree &T, KeyType
key)
//实现二叉排序树的删除操作
{
if (!T)
{
return
FALSE;
}
else
{
if (EQ(key,
T->data.key)) //是否相等
return DeleteEle(T);
else if (LT(key,
T->data.key)) //是否小于
return DeleteBST(T->lchild, key);
else
return DeleteBST(T->rchild,
key);
}
return 0;
}
二叉树的前中后根遍历
栈的定义
typedef struct
{
SElemType *base;
SElemType *top;
int stacksize;
}SqStack;
int InitStack(SqStack &S)
//构造空栈
{
S.base = (SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType));
if (!S.base) exit(OVERFLOW);
S.top = S.base;
S.stacksize = STACK_INIT_SIZE;
return OK;
}//InitStack
int Push(SqStack &S,
SElemType e) //插入元素e为新栈顶
{
if (S.top - S.base >= S.stacksize)
{
S.base = (SElemType*)realloc(S.base, (S.stacksize + STACKINCREMENT)*sizeof(SElemType));
if (!S.base) exit(OVERFLOW);
S.top =
S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}//Push
int Pop(SqStack &S,
SElemType &e) //删除栈顶,应用e返回其值
{
if (S.top == S.base) return ERROR;
e = *--S.top;
return OK;
}//Pop
int StackEmpty(SqStack S) //判断是否为空栈
{
if (S.base == S.top) return TRUE;
return FALSE;
}
