题目:二叉排序树的实现
1 内容和要求
1） 编程实现二叉排序树， 包括生成、插入，删除； 2） 对二叉排序树进行先根、中根、 和后根非递归遍历；
3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4） 分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓
名、成绩 3 项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么?
2 解决方案和关键代码
2.1 解决方案：
先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。
前中后根遍历需要用到栈的数据结构，分模块编写栈与遍历代码。
要求对比二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock（）函数记录查找时间来对比查找效率。
2.2关键代码
2.2.1树的基本结构定义及基本函数
typedef struct {
} ElemType;
typedef struct BiTNode //定义链表 {
//销毁树
int DestroyBiTree(BiTree &T) {
if (T != NULL)
free(T); ElemType data;
struct BiTNode *lchild, *rchild; KeyType key;
}BiTNode, *BiTree, *SElemType;
}
return 0;
//清空树
int ClearBiTree(BiTree &T) { }
//查找关键字,指针p返回
int SearchBST(BiTree T, KeyType key, BiTree f, BiTree &p) { }
if (!T) { }
else if EQ(key, T->data.key) { }
else if LT(key, T->data.key)
return SearchBST(T->lchild, key, T, p); return SearchBST(T->rchild, key, T, p); else
p = T; return TRUE; p = f; return FALSE; if (T != NULL) { } return 0;
T->lchild = NULL; T->rchild = NULL; T = NULL;
2.2.2二叉树的生成、插入，删除 生成
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)) { } else { }
printf(\"输入数据重复！\\n\"); return;
InsertBST(BT, k); scanf_s(\"%d\", &k.key);
插入
int InsertBST(BiTree &T, ElemType e) { }
BiTree s, p;
if (!SearchBST(T, e.key, NULL, p)) { }
else return FALSE;
s = (BiTree)malloc(sizeof(BiTNode)); s->data = e;
s->lchild = s->rchild = NULL; if (!p)
T = s;
p->lchild = s; p->rchild = s;
else if LT(e.key, p->data.key) else
return TRUE;
删除
//某个节点元素的删除 int DeleteEle(BiTree &p) {
BiTree q, s;
if (!p->rchild) //右子树为空 { }
else if (!p->lchild) //左子树为空 {
q = p; p = p->lchild; free(q);
}
}
q = p; p = p->rchild; free(q);
else { }
return TRUE;
q = p; s = p->lchild; while (s->rchild) { }
p->data = s->data; if (q != p)
q->rchild = s->lchild; q->lchild = s->lchild; else delete s;
q = s;
s = s->rchild;
//整棵树的删除
int DeleteBST(BiTree &T, KeyType key) //实现二叉排序树的删除操作 { }
if (!T) { } else { } return 0;
if (EQ(key, T->data.key)) //是否相等
return DeleteEle(T);
return DeleteBST(T->lchild, key); return DeleteBST(T->rchild, key); else if (LT(key, T->data.key)) //是否小于 else
return FALSE;
2.2.3二叉树的前中后根遍历 栈的定义
typedef struct {
int InitStack(SqStack &S) //构造空栈 {
int Push(SqStack &S, SElemType e) //插入元素e为新栈顶 {
int Pop(SqStack &S, SElemType &e) //删除栈顶,应用e返回其值 {
int StackEmpty(SqStack S) //判断是否为空栈 { }
if (S.base == S.top) return TRUE; return FALSE;
if (S.top == S.base) return ERROR; e = *--S.top; return OK;
if (S.top - S.base >= S.stacksize) { }
*S.top++ = e; return OK;
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.base = (SElemType*)malloc(STACK_INIT_SIZE *sizeof(SElemType)); if (!S.base) exit(OVERFLOW); S.top = S.base;
S.stacksize = STACK_INIT_SIZE; return OK; SElemType *base; SElemType *top; int stacksize;
}SqStack;
}//InitStack
}//Push
}//Pop
先根遍历
int PreOrderTraverse(BiTree T, int(*Visit)(ElemType e)) { }
SqStack S; BiTree p; InitStack(S); p = T;
while (p || !StackEmpty(S)) { }
return OK;
if (p) { } else { }
Pop(S, p); p = p->rchild; Push(S, p);
if (!Visit(p->data)) return ERROR; p = p->lchild;
中根遍历
int InOrderTraverse(BiTree T, int(*Visit)(ElemType e)) {
SqStack S; BiTree p; InitStack(S); p = T;
while (p || !StackEmpty(S)) {
if (p) { } else { }
Pop(S, p);
if (!Visit(p->data)) return ERROR; p = p->rchild; Push(S, p); p = p->lchild;
}
}
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)) { }
while (!StackEmpty(SS)) { }
return OK;
Pop(SS, p);
if (!Visit(p->data)) return ERROR; if (p) { } else { }
if (!StackEmpty(S)) { }
Pop(S, p); p = p->lchild; Push(S, p); Push(SS, p); p = p->rchild;
2.2.4利用数组存储一个班学生信息
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,
};
2.2.5数组查询函数
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 << break;
endl;
2.2.6二叉树查询函数
上文二叉树基本函数中的SearchBST()即为二叉树查询函数。
3 数据测试与结果
3.1实现二叉树生成、插入、删除及前中后根遍历
3.1.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.1.2测试结果截图
3.2对比二叉排序树查询和数组查询的效率
3.2.1测试主函数
void main() {
ElemType a[] = { 51, \"陈继真\", 88,
82, \"黄景元\", 89, 53, \"贾成\", 88, 44, \"呼颜\", 90, int nlayer, key, length; clock_t start, finish; BiTree BT, p; double duration; BT = NULL; p = NULL; nlayer = 1;
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 << \" 成绩：\" << finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC; cout << \"二叉树查询时间：\" << duration << endl;
p->data.grade << endl;
}
//通过数组搜索记录 start = clock();
ArraySearch(a, key, length); finish = clock();
duration = (double)(finish - start) / CLOCKS_PER_SEC; cout << \"数组查询时间：\" << duration << endl;
3.2.2测试结果截图
3.2.3结论：
经过三次查询可以看出，二叉树的查找效率要高于数组。当二叉排序树为满二叉树时，树的查找效率最高，因为二叉排序树的平均查找长度和logn是等数量级的，树的深度越小，查找效率越高。因此，要提高二叉排序树的查找效率，可以将二叉排序树转变为平衡二叉树。
4 总结与改进
4.1总结
通过这次课程设计将栈、链表等基本数据结构和一起实现了一遍，并且了解到，不同数据结构的查找效率是不同的，在选择算法时，不仅要考虑算法实现的难易程度，还要考虑它的效率。
在这次课设中也暴露出了平时练习的不足，自身的编程能力不强，本次很多代码都是参看大神博客直接拿来用的，调bug的时候经常无从入手，需要舍友的帮忙。编程还是要多练习，看懂理论跟真的实现出来还有很长的距离，理论要应用于实践才能出真知。
4.2改进
改进成平衡二叉树效率可能更高
因篇幅问题不能全部显示，请点此查看更多更全内容