题目:二叉排序树的实现
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, )*sizeof(SElemType));
if (!S.base) exit(OVERFLOW);
S.top = S.base + S.stacksize;
S.stacksize += STACKINCREMENT;
}
*S.top++ = e;
return OK;
}//Push
S.stacksize (+
STACKINCREMENT
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;
}
先根遍历
int PreOrderTraverse(BiTree T, int(*Visit)(ElemType e))
{
SqStack S;
BiTree p;
InitStack(S);
p = T;
while (p || !StackEmpty(S))
{
if (p)
{
Push(S, p);
if (!Visit(p->data)) return ERROR;
p = p->lchild;
}
else
{
Pop(S, p);
p = p->rchild;
}
}
return OK;
}
中根遍历
int InOrderTraverse(BiTree T, int(*Visit)(ElemType e))
{
SqStack S;
BiTree p;
InitStack(S);
p = T;
while (p || !StackEmpty(S))
{
if (p)
{
Push(S, p);
p = p->lchild;
}
else
{
Pop(S, p);
if (!Visit(p->data)) return ERROR;
p = p->rchild;
}
}
return OK;
}
后根遍历
int PostOrderTraverse(BiTree T, int(*Visit)(ElemType e))
{
SqStack S, SS;
BiTree p;
InitStack(S);
InitStack(SS);
p = T;
while (p || !StackEmpty(S))
{
if (p)
{
Push(S, p);
Push(SS, p);
p = p->rchild;
}
else
{
if (!StackEmpty(S))
{
Pop(S, p);
p = p->lchild;
}
}
}
while (!StackEmpty(SS))
{
Pop(SS, p);
if (!Visit(p->data)) return ERROR;
}
return OK;
}
利用数组存储一个班学生信息
ElemType a[] = { 51, \"陈继真\", 88,
82, \"黄景元\", 89,
53, \"贾成\", 88,
44, \"呼颜\", 90,
25, \"鲁修德\", 88,
56, \"须成\", 88,
47, \"孙祥\", 87,
38, \"柏有患\", 89,
9, \" 革高\", 89,
10, \"考鬲\", 87,
31, \"李燧\", 86,
12, \"夏祥\", 89,
53, \"余惠\", 84,
4, \"鲁芝\", 90,
75, \"黄丙庆\", 88,
16, \"李应\", 89,
87, \"杨志\", 86,
18, \"李逵\", 89,
9, \"阮小五\", 85,
20, \"史进\", 88,
21, \"秦明\", 88,
82, \"杨雄\", 89,
23, \"刘唐\", 85,
64, \"武松\", 88,
25, \"李俊\", 88,
86, \"卢俊义\", 88,
27, \"华荣\", 87,
28, \"杨胜\", 88,
29, \"林冲\", 89,
70, \"李跃\", 85,
31, \"蓝虎\", 90,
32, \"宋禄\", 84,
73, \"鲁智深\", 89,
34, \"关斌\", 90,
55, \"龚成\", 87,
36, \"黄乌\", 87,
57, \"孔道灵\", 87,
38, \"张焕\", 84,
59, \"李信\", 88,
30, \"徐山\", 83,
41, \"秦祥\", 85,
42, \"葛公\", 85,
23, \"武衍公\", 87,
94, \"范斌\", 83,
45, \"黄乌\", 60,
67, \"叶景昌\", 99,
7, \"焦龙\", 89,
78, \"星姚烨\", 85,
49, \"孙吉\", 90,
60, \"陈梦庚\", 95,
};
数组查询函数
void ArraySearch(ElemType a[], int key, int length){
int i;
for (i = 0; i <= length; i++){
if (key == a[i].key){
cout << \"学号：\" << a[i].key << \" 姓名：\" << a[i].name << \" 成绩：\" << a[i].grade << endl;
break;
}
}
}
二叉树查询函数
上文二叉树根本函数中的SearchBST()即为二叉树查询函数。
3 数据测试与结果
3.1实现二叉树生成、插入、删除及前中后根遍历
测试主函数
void main()
{
int nlayer;
BiTree BT, p;
BT = NULL;
p = NULL;
nlayer = 1;
ElemType e,d;
CreateBST(BT, p);
printf(\"二叉排序树树形输出为：\\n\");
DispalyBST(BT, nlayer);
printf(\"请输入插入的元素：\");
scanf_s(\"%d\", &e.key);
InsertBST(BT, e);
printf(\"\\n\");
DispalyBST(BT, nlayer);
printf(\"请输入删除的元素：\");
scanf_s(\"%d\", &d.key);
DeleteBST(BT, d.key);
printf(\"\\n\");
DispalyBST(BT, nlayer);
printf(\"先序遍历为：\");
PreOrderTraverse(BT, Visit);
printf(\"\\n中序遍历为：\");
InOrderTraverse(BT, Visit);
printf(\"\\n后序遍历为：\");
PostOrderTraverse(BT, Visit);
ClearBiTree(BT);
printf(\"\\n二叉排序树已清空.\\n\");
DispalyBST(BT, nlayer);
DestroyBiTree(BT);
printf(\"\\n二叉排序树已销毁.\\n\");
system(\"pause\");
}
测试结果截图
3.2比照二叉排序树查询和数组查询的效率
3.2.1测试主函数
void main()
{
int nlayer, key, length;
clock_t start, finish;
BiTree BT, p;
double duration;
BT = NULL;
p = NULL;
nlayer = 1;
ElemType a[] = { 51, \"陈继真\", 88,
82, \"黄景元\", 89,
53, \"贾成\", 88,
44, \"呼颜\", 90,
25, \"鲁修德\", 88,
56, \"须成\", 88,
47, \"孙祥\", 87,
38, \"柏有患\", 89,
9, \" 革高\", 89,
10, \"考鬲\", 87,
31, \"李燧\", 86,
12, \"夏祥\", 89,
53, \"余惠\", 84,
4, \"鲁芝\", 90,
75, \"黄丙庆\", 88,
16, \"李应\", 89,
87, \"杨志\", 86,
18, \"李逵\", 89,
9, \"阮小五\", 85,
20, \"史进\", 88,
21, \"秦明\", 88,
82, \"杨雄\", 89,
23, \"刘唐\", 85,
64, \"武松\", 88,
25, \"李俊\", 88,
86, \"卢俊义\", 88,
27, \"华荣\", 87,
28, \"杨胜\", 88,
29, \"林冲\", 89,
70, \"李跃\", 85,
31, \"蓝虎\", 90,
32, \"宋禄\", 84,
73, \"鲁智深\", 89,
34, \"关斌\", 90,
55, \"龚成\", 87,
36, \"黄乌\", 87,
57, \"孔道灵\", 87,
38, \"张焕\", 84,
59, \"李信\", 88,
30, \"徐山\", 83,
41, \"秦祥\", 85,
42, \"葛公\", 85,
23, \"武衍公\", 87,
94, \"范斌\", 83,
45, \"黄乌\", 60,
67, \"叶景昌\", 99,
7, \"焦龙\", 89,
78, \"星姚烨\", 85,
49, \"孙吉\", 90,
60, \"陈梦庚\", 95,
};
length = sizeof(a) / sizeof(a[0]);
CreateBST(BT, p, a, length);
//树形显示二叉排序树
printf(\"二叉排序树树形输出为：\\n\");
ShowBST(BT, nlayer);
while (1){
printf(\"请输入需要查找的学生学号:\\n\");
cin >> key;
if (!key)
break;
//通过二叉树搜索记录
start = clock();
SearchBST(BT, key, NULL, p);
cout << \"学号：\" << p->data.key << \" 姓名：\" << p->data.name << \" 成绩：\" << p->data.grade << endl;
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << \"二叉树查询时间：\" << duration << endl;
//通过数组搜索记录
start = clock();
ArraySearch(a, key, length);
finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC;
cout << \"数组查询时间：\" << duration << endl;
}
}
测试结果截图
结论：
经过三次查询可以看出，二叉树的查找效率要高于数组。当二叉排序树为满二叉树时，树的查找效率最高，因为二叉排序树的平均查找长度和logn是等数量级的，树的深度越小，查找效率越高。因此，要进步二叉排序树的查找效率，可以将二叉排序树转变为平衡二叉树。
4 总结与改进
4.1总结
通过这次课程设计将栈、链表等根本数据构造和一起实现了一遍，并且理解到，不同数据构造的查找效率是不同的，在选择算法时，不仅要考虑算法实现的难易程度，还要考虑它的效率。
在这次课设中也暴露出了平时练习的缺乏，自身的编程才能不强，本次很多代码都是参看大神
博客直接拿来用的，调bug的时候经常无从入手，需要舍友的帮助。编程还是要多练习，看懂理论跟真的实现出来还有很长的间隔 ，理论要应用于理论才能出真知。
4.2改进
改进成平衡二叉树效率可能更高
因篇幅问题不能全部显示，请点此查看更多更全内容