内蒙古科技大学

本科生课程设计说明书

题 目：数据结构课程设计

—— 二叉树的遍历和应用

学生姓名：

学 号：

专 业：

班 级：

指导教师：

20xx年5月29日

内蒙古科技大学课程设计说明书

内蒙古科技大学课程设计任务书

I

内蒙古科技大学课程设计说明书

目 录

内蒙古科技大学课程设计任务书 ······························································ 错误！未定义书签。 目 录 ···································································································································· II

第一章 需求分析 ·····················································································································3

1.1 课程设计目的 ··········································································································3

1.2 任务概述 ··················································································································3

1.3 课程设计内容 ··········································································································3

…… …… 余下全文

广西工学院计算机学院

《数据结构》课程实验报告书

实验六二叉树的基本操作及其应用

            学生姓名：

            学    号：

            班级：

            指导老师：

            专    业：计算机学院软件学院

提交日期：20##年6月22日

1．实验目的

1） 了解二叉树的特点、掌握二叉树的主要存储结构。

2）  掌握二叉树的基本操作，能针对二叉树的具体应用选择相应的存储结构。

3） 掌握递归算法的设计方法。

2.实验内容

（1）二叉链表表示二叉树，建立一棵二叉树，实现下列基本操作,通过数据测试每个操作的正确性，包括：

1. CreateBinTree(&T)：  建立一颗二叉树：。

2. BinTreeEmpty(T):     判断一棵二叉树是否为空树。

3. PreOrderTraverse(T): 先序遍历二叉树T，并输出节点序列。

4. InOrderTraverse(T):  中序遍历二叉树T，并输出节点序列。

…… …… 余下全文

数据结构实验报告

实验题目：树和二叉树的应用

实验内容：重言式判别

实验目的：掌握树和二叉树的概念及工作原理，运用其原理及概念完成上述实验题中的内

容。

实验要求：为了使学生更好的掌握与理解课堂上老师所讲的概念与原理，实验前每个学生

要认真预习所做的实验内容及编写源程序伪码（写在纸上及盘中均可）以

便在实验课中完成老师所布置的实验内容。

设计原理：

1.一个逻辑表达式如果对于其变元的任一种取值均为真，则成为重言式；反之，如果对于其变元的任一种取值都为假，则称为矛盾式，然而，更多的情况下，既非重言式，也非矛盾式。写一个程序通过真值表判别一个逻辑表达式属于上述哪一类。基本要求如下：

（1）逻辑表达式从终端输入，长度不超过一行。逻辑运算符包括“｜”、“＆”和“～”，分别表示或、与和非，运算优先程度递增，但可有括号改变，即括号内的运算优先。逻辑变元为大写字母。表达式中任何地方都可以含有多个空格符。

（2）若是重言式或矛盾式，可以只显示“True Forever”或“False Forever”，否则显示“Statisfactible”以及变量名序列，与用户交互。若用户对表达式变元取定一组值，程序就求出并显示逻辑表达式的值。

（3）本程序先使用栈将逻辑表达式的变量进行存储，然后将栈中的元素作为二叉树的结点结构，然后根据优先级读取表达式建立二叉树，并通过逐个判断根实现对重言式的判别。

2. 程序执行的命令

（1）输入逻辑表达式 （2）判断表达式是重言式还是矛盾式 （3）若既不是重言式也不是矛盾式，则对变元取定值，并显示逻辑表达式的值 （4）结束

3．测试数据

(1) (A|~A)&(B|~B)

(2) (A&~A)&C

(3) A|B|C|D|E|~A

(4) A&B&C&~B

(5) (A|B)&(A|~B)

…… …… 余下全文

实 验 报 告

课程名称 ____数据结构上机实验__________ 实验项目 ______二叉树的应用 ____________ 实验仪器 ________PC机___________________

系 别____________________________ 专 业_____________________________ 班级/学号____________________________ 学生姓名 _____________________________ 实验日期 _______________________ 成 绩 _______________________ 指导教师 _______________________

实验三.二叉树的应用

1. 实验目的：掌握二叉树的链式存储结构和常用算法。利用哈夫曼树设计最优压缩编码。

2. 实验内容：

1) 编写函数，实现建立哈夫曼树和显示哈夫曼树的功能。

2) 编写函数，实现生成哈夫曼编码的功能。

3) 编写主函数，从终端输入一段英文文本；统计各个字符出现的频率，然后构建哈夫曼树并求出对应的哈夫曼编码；显示哈夫曼树和哈夫曼编码。

选做内容：修改程序，选择实现以下功能：

4) 编码：用哈夫曼编码对一段英文文本进行压缩编码，显示编码后的文本编码序列；

5) 统计：计算并显示文本的压缩比例；

6) 解码：将采用哈夫曼编码压缩的文本还原为英文文本。

3. 算法说明：

1) 二叉树和哈夫曼树的相关算法见讲义。

2) 编码的方法是：从头开始逐个读取文本字符串中的每个字符，查编码表得到它的编码并输出。重复处理直至文本结束。

3) 解码的方法是：将指针指向哈夫曼树的树根，从头开始逐个读取编码序列中的每位，若该位为1则向右子树走，为

0则向左子树走。当走到叶子节点时，取出节点中的字符并输出。重新将指针放到树根，继续以上过程直至编码序列处理完毕。

…… …… 余下全文

#include "stdio.h"

#include "stdlib.h"

#include "string.h"

#include "math.h"

typedef char TElemType; //定义结点数据为字符型 typedef int Status; //定义函数类型为int型 #define ERROR 0

#define OK 1

typedef struct BiTNode{ //定义结构体 TElemType data; //结点数值

struct BiTNode *lchild; //左孩子指针

struct BiTNode *rchild; //右孩子指针

struct BiTNode *next; //下一结点指针 }BiTNode, *BiTree;

Status NumJudge(char ch[20]){

//限制输入数据必须为大于零的整形

char ch1[20];

int num;

while(1){

scanf("%s",ch);

num=atoi(ch); //将字符串转换为整型

itoa(num,ch1,10); //将整型转换为字符串型

if(strcmp(ch,ch1)==0&&num>0)break;

else{printf("请输入一个大于零的整数: ");}

}

return num;

}//NumJudge

Status InitBiTree(BiTree &T){

//构造空二叉树T

if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(ERROR); //若申请空间失败则退出 T->next=NULL;

…… …… 余下全文

#include "stdio.h"

#include "malloc.h"

#define maxsize 20 //规定树中结点的最大数目 

#include"windows.h"

typedef struct node{ //定义数据结构

int ltag,rtag; //表示child 域指示该结点是否孩子

char data; //记录结点的数据

struct node *lchild,*rchild; //记录左右孩子的指针

}Bithptr;

Bithptr *Q[maxsize]; //建队，保存已输入的结点的地

址

Bithptr *CreatTree(){ //建树函数，返回根指针

char ch;

int front,rear;

Bithptr *T,*s;

 T=NULL;

front=1;rear=0; //置空二叉树

printf("                       

***********************************\n");

printf("                        *                          

…… …… 余下全文

实验五 二叉树基本操作的编程实现

【实验目的】

内容：二叉树基本操作的编程实现

要求：

二叉树基本操作的编程实现（2学时，验证型），掌握二叉树的建立、遍历、插入、删除等基本操作的编程实现，也可以进一步编程实现查找等操作，存储结构主要采用顺序或链接结构。也鼓励学生利用基本操作进行一些应用的程序设计。

【实验性质】

验证性实验（学时数：2H）

【实验内容】

以下的选题都可以作为本次实验的推荐题目

1. 建立二叉树，并以前序遍历的方式将结点内容输出。

2. 将一个表示二叉树的数组结构转换成链表结构。

3. 将表达式二叉树方式存入数组，以递归方式建立表达式之二叉树状结构，再分别输出前序、中序及后序遍历结果，并计算出表达式之结果。

【思考问题】

1. 二叉树是树吗？它的定义为什么是递归的？

2. 三种根序遍历主要思路是什么？

3. 如果不用遍历算法一般启用什么数据结构实现后序遍历？

4. 举出二叉树的应用范例？

【参考代码】

（一）建立二叉树，并以前序遍历的方式将结点内容输出*/

/*===============================================*/ /*程序构思： */ /*输入元素值后建立二叉树，以递归的方式做前序遍历，*/ /*其顺序为：结点－左子－右子树，并将二叉树结点内容输出。*/ #include<stdlib.h> #include<stdio.h> struct tree /*声明树的结构 */ { struct tree *left; /*存放左子树的指针 */ int data; /*存放结点数据内容 */ struct tree *right; /*存放右子树的指针 */ }; typedef struct tree treenode; /*声明新类型树结构 */ typedef treenode *b_tree; /*声明二叉树的链表 */ /*===============================================*/ /*插入二叉树结点 */ /*===============================================*/ b_tree insert_node (b_tree root, int node) { b_tree newnode; /*声明树根指针 */ b_tree currentnode; /*声明目前结点指针 */ b_tree parentnode; /*声明父结点指针 */

…… …… 余下全文