北京物资学院信息学院实验报告课程名数据结构(C++)实验实验名称二叉树算法的实现实验日期年月日实验报告日期年月日姓名______ ___ 班级_____ _______ 学号___一、实验目的1.掌握二叉树的存储的结构；2. 掌握建立二叉树的算法；3. 掌握对二叉树的遍历算法；4. 掌握二叉搜索树的算法；5. 掌握建立哈夫曼树和哈夫曼编码的算法；二、实验内容基本部分1. 采用广义表形式建立二叉树(参考图5-11(a)和/或图5-13(a))；2. 对已建立的二叉树，进行先、中、后序和按层遍历；3. 用广义表形式输出二叉树；4. 【习题5-3】1, 2 (2题选作)【提示：参考递归遍历算法】；特殊二叉树部分1．用插入算法建立一棵二叉搜索树，原始数据为：{30,50,20,40,25,70,54,23,80,92}，并中序遍历该树、查找其中的元素；2. 构造一棵叶子结点权值分别为3，5，6，7，9，13，21的哈夫曼树；3. 对2题进行哈夫曼编码。
三、实验地点与环境3.1 实验地点(南实验楼教室)3.2实验环境(所用语言环境)四、实验步骤1.2.3.…五、实验结果与分析5.1 实验结果(原始数据，预期结果和运行结果)序号算法名称(函数名) 所在头文件名原始数据与与功能主函数所在文件名运行结果*1 函数名：功能：头文件：CPP文件：原始数据：运行结果：23* 如果不能按“原始数据”、“运行结果”列出数据则不列，必要时在“分析”部分说明5.2 分析（选择部分算法分析，包括函数参数说明、调试中所遇到的问题和解决方法、中间结果等，必要时给出函数和主函数的关键段落。
所选算法应是：重要的算法、有编程特点的算法等）六、小结（收获与心得）。
题目:二叉排序树的实现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);elsereturn 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;elsep->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;elseq->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);elsereturn 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;}//InitStackint 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;}//Pushint Pop(SqStack &S, SElemType &e) //删除栈顶,应用e返回其值{if (S.top == S.base) return ERROR;e = *--S.top;return OK;}//Popint 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()即为二叉树查询函数。
《数据结构》【教案】第五章树和二叉树目录5.1树的定义和基本术语 (2)5.2二叉树 (3)5.2.1 二叉树的定义 (3)5.2.2 二叉树的性质 (5)5.2.3 二叉树的存储结构 (6)5.3树和森林 (7)5.4二叉树的先|中|后序遍历算法 (8)5.5先|后|中序遍历的应用扩展 (9)5.5.1 基于先序遍历的二叉树(二叉链)的创建 (10)5.5.2 求二叉树的叶子结点的数目 (10)5.5.3 求二叉树的高度 (11)5.5.4 释放二叉树的所有结点空间 (12)5.5.5 删除并释放二叉树中以元素值为x的结点作为根的各子树(12)5.5.6 线索二叉树 (13)5.5.7 树和森林的遍历 (14)5.6二叉树的层次遍历 (15)5.7判断一棵二叉树是否为完全二叉树 (16)5.8哈夫曼树及其应用 (18)5.8.1 最优二叉树(哈夫曼树) (18)5.8.2 哈夫曼编码 (18)第5章二叉树和树5.1 树的定义和基本术语1、树的递归定义有且仅有一个根结点、m个互不相交的有限结点集——m棵子树结点数n≥02、基本术语结点：叶子(终端结点)、根、内部结点；终端结点、非终端结点(分支结点)树的规模：结点的度、树的度、结点的层次、树的高度(深度)结点间的关系：双亲(1)—孩子(m)，祖先—子孙，兄弟，堂兄弟兄弟间是否存在次序：无序树、有序树去掉根结点树森林引入一个根结点3、抽象数据类型定义树特有的操作：查找：双亲、最左的孩子、右兄弟结点的度不定，给出这两种操作可以查找到一个结点的全部孩子插入、删除：孩子遍历：存在一对多的关系，给出一种有规律的方法遍历(有且仅访问一次)树中的结点ADT Tree{数据对象：D={a i|a i∈ElemSet, i=1,2,…,n, n≥0}数据关系：若D为空集，则称为空树；若D仅含一个数据元素，则R为空集，否则R={H}，H是如下二元关系：(1) 在D中存在唯一的称为根的数据元素root，它在关系H下无前驱；(2) 若D-{root}≠Ф，则存在D-{root}的一个划分D1,D2, …, D m(m>0)（D i表示构成第i棵子树的结点集），对任意j≠k(1≤j,k≤m)有D j∩D k=Ф，且对任意的i(1≤i≤m)，唯一存在数据元素x i∈D i, 有∈H（H表示结点之间的父子关系）；(3) 对应于D-{root}的划分，H-{,…, }有唯一的一个划分H1,H2, …, H m(m>0)（H i表示第i棵子树中的父子关系），对任意j≠k(1≤j,k≤m)有H j∩H k=Ф，且对任意i(1≤i≤m)，H i是D i 上的二元关系，(D i, {H i})是一棵符合本定义的树，称为根root的子树。
二叉排序树操作一、设计步骤1）分析课程设计题目的要求2）写出详细设计说明3）编写程序代码，调试程序使其能正确运行4）设计完成的软件要便于操作和使用5）设计完成后提交课程设计报告（一）程序功能：1）创建二叉排序树2）输出二叉排序树3）在二叉排序树中插入新结点4）在二叉排序树中删除给定的值5）在二叉排序树中查找所给定的值（二）函数功能：1） struct BiTnode 定义二叉链表结点类型包含结点的信息2） class BT 二叉排序树类，以实现二叉排序树的相关操作3） InitBitree() 构造函数，使根节点指向空4) ~BT () 析构函数，释放结点空间5) void InsertBST(&t,key) 实现二叉排序树的插入功能6) int SearchBST(t,key) 实现二叉排序树的查找功能7) int DelBST(&t,key) 实现二叉排序树的删除功能8) void InorderBiTree (t) 实现二叉排序树的排序（输出功能）9) int main() 主函数，用来完成对二叉排序树类中各个函数的测试二、设计理论分析方法（一）二叉排序树定义首先，我们应该明确所谓二叉排序树是指满足下列条件的二叉树：（1）左子树上的所有结点值均小于根结点值；（2）右子数上的所有结点值均不小于根结点值；（3）左、右子数也满足上述两个条件。
根据对上述的理解和分析，我们就可以先创建出一个二叉链表结点的结构体类型（struct BiTNode）和一个二叉排序树类（class BT），以及类中的构造函数、析构函数和其他实现相关功能的函数。
（二）插入函数（void InsertBST(&t,key)）首先定义一个与BiTNode<k> *BT同一类型的结点p，并为其申请空间，使p->data=key,p->lchild和p->rchild=NULL。
