题目:二叉排序树的实现
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)
ＩＳＳＮ １００９－３０４４ Ｃｏｍｐｕｔｅｒ Ｋｎｏｗｌｅｄｇｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ电脑知识与技术 Ｖｏ１．１０，Ｎｏ．１，Ｊａｎｕａｒｙ ２０１４ Ｅ—ｍａｉｌ：ｋｆｙｊ＠ｄｎｚｓ．ｎｅｔ．ｃｎ ｈｔｔｐ：／／ｗｗｗ．ｄｎｚｓ．ｎｅｔ．ｃｎ Ｔｅｌ：＋８６—５５ １－６５６９０９６３ ６５６９０９６４
一种二叉树非递归遍历算法的Ｃ语言实现
龚佳，袁赘，刘远军
（邵阳学院信息工程系，湖南邵阳４２２００４）
摘要：针对二叉树的链式存储结构，分析了二叉树的各种遍历算法，探讨了递归算法的递推消除问题，提出了一种改进的
非递归遍历算法并用Ｃ语言予以实现。
关键词：二叉树；遍历算法；非递归；Ｃ语言实现
中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１００９—３０４４（２０１４）０１一Ｏ２２３一Ｏ３
Ｏｎｅ Ｋｉｎｄ ｏｆ Ｂｉｎａｒｙ Ｔｒｅｅ Ｔｒａｖｅｒｓａｌ Ｎｏｎ—－ｒｅｅｕｒｓｉｖｅ Ａｌｇｏｒｉｔｈｍ ｉｎ Ｃ Ｌａｎｇｕａｇｅ
ＧＯＮＧ Ｊｉａ，ＹＵＡＮ Ｙｕｎ，ＬＩＵ Ｙｕｎ－ｊｔｉｎ
（Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｄｅｐａｒｔｍｅｎｔ，Ｓｈａｏｙａｎｇ Ｕｎｉｖｅｒｓｉｔｙ，Ｓｈａｏｙａｎｇ ４２２００４，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ａｃｃｏｒｄｉｎｇ ｔＯ ｔｈｅ ｃｈａｉｎ ｓｔｏｒｅ ｓｔｒｕｃｔｕｒｅ ｏｆ ｂｉｎａｒｙ ｔｒｅｅ，ｔｈｉｓ ｐａｐｅｒ ａｎａｌｙｚｅｓ ｂｉｎａｒｙ ｔｒｅｅ ｔｒａｖｅｒｓａｌ ａｌｇｏｒｉｔｈｍｓ，ｄｉｓｃｕｓｓｅｓ ｒｅｃｕｒ— ｓｉｖｅ ｒｅｃｕｒｓｉｖｅ ａｌｇｏｒｉｔｈｍ ｔｏ ｅｌｉｍｉｎａｔｅ ｐｒｏｂｌｅｍｓ，ａｎｄ ｐｕｔ ｆｏｒｗａｒｄ ａｎ ｉｍｐｒｏｖｅｄ ａｎｄ ｎｏｎ—ｒｅｃｕｒｓｉｖｅ ｔｒａｖｅｒｓａｌ ａｌｇｏｒｉｔｈｍ ｔｏ ｂｅ ｉｍｐｌｅ－
ｍｅｎｔｅｄ ｉｎ Ｃ ｌａｎｇｕａｇｅ．
数据结构（⼆⼗四）⼆叉树的链式存储结构（⼆叉链表）
⼀、⼆叉树每个结点最多有两个孩⼦，所以为它设计⼀个数据域和两个指针域，称这样的链表叫做⼆叉链表。
⼆、结点结构包括：lchild左孩⼦指针域、data数据域和rchild右孩⼦指针域。
三、⼆叉链表的C语⾔代码实现：
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
#include "io.h"
#include "math.h"
#include "time.h"
#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define MAXSIZE 100 /* 存储空间初始分配量 */
typedef int Status; /* Status是函数的类型,其值是函数结果状态代码，如OK等 */
/* ⽤于构造⼆叉树********************************** */
int index=1;
typedef char String[24]; /* 0号单元存放串的长度 */
String str;
Status StrAssign(String T,char *chars)
{
int i;
if(strlen(chars)>MAXSIZE)
return ERROR;
else
{
T[0]=strlen(chars);
for(i=1;i<=T[0];i++)
T[i]=*(chars+i-1);
return OK;
}
}
/* ************************************************ */
typedef char TElemType;
TElemType Nil=' '; /* 字符型以空格符为空 */
Status visit(TElemType e)
{
printf("%c ",e);
《数据结构和算法》
实验指导书
实验及学时数分配
序号 实验名称 学时数（小时）
1 实验一 线性表 4
2 实验二 树和二叉树 2
3 实验三 图 2
4 实验四 查找 2
5 实验五 内部排序 2
合计 12
几点要求：
一、 上机前：认真预习相关实验内容，提前编写算法程序，上机时检查（未提前编写程序者，扣除平时成绩中实验相关分数）。
二、 上机中：在Turbo C或VC6.0环境中，认真调试程序，记录调试过程中的问题、解决方法以及运行结果。上机时签到；下机时验收签字。
三、 下机后：按要求完成实验报告，并及时提交（实验后1周内）。
实验一 线性表
【实验目的】
1、 掌握用Turbo c上机调试线性表的基本方法；
2、 掌握线性表的基本操作，插入、删除、查找以及线性表合并等运算在顺序存储结构和链式存储结构上的运算；
3、 运用线性表解决线性结构问题。
【实验学时】
4 学时
【实验类型】
设计型
【实验内容】
1、 顺序表的插入、删除操作的实现；
2、 单链表的插入、删除操作的实现；
3、 两个线性表合并算法的实现。(选做)
【实验原理】
1、 当我们在线性表的顺序存储结构上的第i个位置上插入一个元素时，必须先将线性表中第i个元素之后的所有元素依次后移一个位置，以便腾出一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置；
2、 当我们在线性表的链式存储结构上的第i个位置上插入一个元素时，只需先确定第i个元素前一个元素位置，然后修改相应指针将新元素插入即可。若是欲删除第i个元素时，也必须先确定第i个元素前一个元素位置，然后修改相应指针将该元素删除即可；
3、 详细原理请参考教材。
【实验步骤】
一、用C语言编程实现建立一个顺序表，并在此表中插入一个元素和删除一个元素。
1、 通过键盘读取元素建立线性表；（从键盘接受元素个数n以及n个整形数；按一定格式显示所建立的线性表）
