2022年树形数据结构及其应用 .pdf

《2022年树形数据结构及其应用 .pdf》由会员分享，可在线阅读，更多相关《2022年树形数据结构及其应用 .pdf（11页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、淮海工学院计算机工程学院实 验 报 告 书课 程 名 ： 数 据 结 构题目：树形数据结构及其应用班级：学号：姓名：评语：成绩：指导教师：批阅时间：年月日名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 11 页 - - - - - - - - - 数据结构实验报告- 1 - 实验 2树形数据结构实验目的和要求1熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先序递归遍历、中序递归和非递归遍历、后序递归遍历。2掌握按先序遍历顺序输入数据，递归建立二叉树的方

2、法。3. 掌握建立哈夫曼树的方法，实现哈夫曼编码。实验环境Turbo C 或 VC+ 实验学时4 学时，必做实验实验题目1. 问题描述 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。 基本要求 从键盘接受输入先序序列， 以二叉链表作为存储结构， 建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。 测试数据 ABCDE G F（其中 表示空格字符）输出结果为：先序： ABCDEGF 中序： CBEGDFA 后序： CGBFDBA 2已知二叉树按照二叉链表方式存储，编写算法，要求实现二

3、叉树的竖向显示（竖向显示就是二叉树的按层显示）。 提示 ：（1）参习题 6.20 ，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离3如题 1 要求建立好二叉树，按凹入表形式打印二叉树结构，如图6.34 所示。A B C D E 图 6.34 F C F E A D B 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 11 页 - - - - - - - - - 数据结构实验报告- 2 - 主要数据结构1.typedef char DataType; typ

4、edef struct Node DataType data; struct Node *LChild; struct Node *RChild; BiTNode, *BiTree; 2. ypedef BiTree QueueElementType; typedef struct QueueElementType elementMAXSIZE; /* 队列的元素空间*/ int front; /*头指针指示器 */ int rear; /*尾指针指示器 */ SeqQueue; 3.void InitQueue(SeqQueue *Q)/*初始化操作 */ 4.int EnterQueue(

5、SeqQueue *Q, QueueElementType x)/*入队操作 */ 5.int DeleteQueue(SeqQueue *Q, QueueElementType *x)/*出队操作 */ 6.int LayerOrder(BiTree bt) 7.InitQueue(Q); /*初始化空队列Q*/ 8. void CreateBiTree(BiTree *bt) 9.void PreOrder(BiTree root)/ 先序遍历二叉树10.void InOrder(BiTree root)/ 中序遍历二叉树11.void PostOrder(BiTree root)/ 后序

6、遍历二叉树12.int CreateBiTree(BiTree &T) /创建一棵非空二叉树13.void PrintTree(BiTree Boot,int nLayer) /* 打印二叉树*/ 主要算法1.用递归和非递归进行遍历（先序、中序、后序）2.按图进行遍历3.用队列编写二叉链表存储：初始化、入队、出队运行结果1.递归非递归名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 11 页 - - - - - - - - - 数据结构实验报告- 3 - 2. 3. 实验体

7、会1.代码可能有点冗长，对后序线索二叉树求后继节点实现的不是很好。2.这次任务量有点大，实现的函数太多，全部放在一个文件里不利于维护与修改。附源代码1. 递归：#include #include #include typedef char DataType; typedef struct Node DataType data; struct Node *LChild; struct Node *RChild; BiTNode, *BiTree; void CreateBiTree(BiTree *bt) char ch; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

8、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 11 页 - - - - - - - - - 数据结构实验报告- 4 - ch=getchar(); if(ch= ) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree(&(*bt)-LChild); CreateBiTree(&(*bt)-RChild); void Visit(char ch) printf(%c ,ch); void PreOrder(BiTree root)/先序遍

9、历二叉树 if(root!=NULL) Visit(root-data); PreOrder(root-LChild); PreOrder(root-RChild); void InOrder(BiTree root)/中序遍历二叉树 if(root!=NULL) InOrder(root-LChild); Visit(root-data); InOrder(root-RChild); void PostOrder(BiTree root)/后序遍历二叉树 if(root!=NULL) PostOrder(root-LChild); PostOrder(root-RChild); Visit(

10、root-data); void main() BiTree T; CreateBiTree(&T); printf(先序遍历序列为:); PreOrder(T); printf(n中序遍历序列为:); InOrder(T); printf(n后序遍历序列为:); PostOrder(T); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 11 页 - - - - - - - - - 数据结构实验报告- 5 - getch(); 非递归：#include using na

11、mespace std; #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int SElemType; typedef struct Node char data; struct Node *LChild; struct Node *RChild; BiTNode,*BiTree; typedef struct BiTNode *a100; int top; Sqstack; void push(Sqstack *s,BiTNode *x) if (s-top=100) coutstack overflow!top+; s-as

12、-top=x; BiTNode *pop(Sqstack *s,BiTNode *x) if (s-top=0) coutstack underflow!as-top; s-top-; return (x); int CreateBiTree(BiTree &T) /创建一棵非空二叉树 char ch; cinch; if(ch=.) T=NULL; else 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 11 页 - - - - - - - - - 数据结构实验报告-

13、 6 - if(!(T=(BiTNode*)malloc(sizeof(BiTNode) exit(OVERFLOW); T-data=ch; CreateBiTree(T-LChild); CreateBiTree(T-RChild); return OK; void Preorder(BiTree T) /先序递归操作遍历二叉树 if(T) coutdataLChild); Preorder(T-RChild); void Inorder(BiTree T) /中序非递归操作遍历二叉树 Sqstack s; BiTNode *p; s.top=0; push(&s,T); while (s

14、.top!=0) while (s.as.top!=NULL) p=s.as.top; push(&s,p-LChild); p=pop(&s,T); if(s.top!=0) p=pop(&s,T); coutdataRChild); void Postorder(BiTree T) /后序非递归操作遍历二叉树 if(T) Postorder(T-LChild); Postorder(T-RChild); coutdata ; void main() BiTree T; cout 输入要创建树的顺序:; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - -

15、 - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 11 页 - - - - - - - - - 数据结构实验报告- 7 - CreateBiTree(T); cout 先序遍历的结果:; Preorder(T); coutn; cout 中序遍历的结果:; Inorder(T); coutn; cout 后序遍历的结果:; Postorder(T); coutn; 2.typedef struct Node DataType data; struct Node *LChild; struct Node *RChild; BiTNode, *BiTree; 按照

16、右根左方式遍历孩子兄弟表示树，然后先根遍历。#include stdio.h #include #include #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OK 1 #define MAXSIZE 50 /*队列的最大长度*/ Typedef char DataTpye typedef struct Node DataType data; struct Node *LChild; struct Node *RChild; BiTNode, *BiTree; typedef BiTree QueueElementType; ty

17、pedef struct QueueElementType elementMAXSIZE; /* 队列的元素空间*/ int front; /*头指针指示器 */ int rear; /*尾指针指示器 */ SeqQueue; /* 初始化操作 */ void InitQueue(SeqQueue *Q) /* 将*Q 初始化为一个空的循环队列 */ Q-front=Q-rear=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 11 页 - - - - - - -

18、- - 数据结构实验报告- 8 - /* 入队操作 */ int EnterQueue(SeqQueue *Q, QueueElementType x) /* 将元素 x 入队 */ if(Q-rear+1)%MAXSIZE=Q-front) /*队列已经满了*/ return(FALSE); Q-elementQ-rear=x; Q-rear=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */ return(TRUE); /*操作成功 */ /* 出队操作 */ int DeleteQueue(SeqQueue *Q, QueueElementType *x) /* 删除队

19、列的队头元素，用x 返回其值 */ if(Q-front=Q-rear) /*队列为空 */ return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/ return(TRUE); /*操作成功 */ int IsEmpty(SeqQueue *Q) /* 提取队列的队头元素，用x 返回其值 */ if(Q-front=Q-rear) /*队列为空 */ return(TRUE); else return(FALSE); /*操作成功 */ int LayerOrder(BiTree bt) Seq

20、Queue *Q; BiTree p; Q=(SeqQueue *)malloc(sizeof(SeqQueue); /p=(BiTree *)malloc(sizeof(BiTree); InitQueue(Q); /*初始化空队列Q*/ if(bt = NULL) return ERROR; /* 若二叉树 bt 为空树，则结束遍历*/ EnterQueue(Q, bt);/* 若二叉树 bt 非空，则根结点bt 入队，开始层次遍历*/ while(!IsEmpty(Q)/*若队列非空，则遍历为结束，继续进行*/ DeleteQueue(Q, &p);/*队头元素出队并访问 */ prin

21、tf(%c ,p-data); if(p-LChild ) EnterQueue(Q, p-LChild);/*若 p 的左孩子非空，则进队*/ 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 11 页 - - - - - - - - - 数据结构实验报告- 9 - if(p-RChild ) EnterQueue(Q, p-RChild); /*若 p 的右孩子非空，则进队*/ /*while*/ return OK; /* LayerOrder */ void mai

22、n() BiTree T; printf(按扩展先序遍历序列建立二叉树，请输入序列:n); CreateBiTree(&T); printf(层次遍历输出结点为:); LayerOrder(T); getch(); 3. #include #include #include typedef char DataType; typedef struct Node DataType data; struct Node *LChild; struct Node *RChild; BiTNode, *BiTree; void CreateBiTree(BiTree *bt) char ch; ch=ge

23、tchar(); if(ch= ) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree(&(*bt)-LChild); CreateBiTree(&(*bt)-RChild); void Visit(char ch) printf(%c,ch); void PreOrder(BiTree root) if(root!=NULL) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1

24、0 页，共 11 页 - - - - - - - - - 数据结构实验报告- 10 - Visit(root-data); PreOrder(root-LChild); PreOrder(root-RChild); void InOrder(BiTree root) if(root!=NULL) InOrder(root-LChild); Visit(root-data); InOrder(root-RChild); void PostOrder(BiTree root) if(root!=NULL) PostOrder(root-LChild); PostOrder(root-RChild)

25、; Visit(root-data); void PrintTree(BiTree Boot,int nLayer) if(Boot=NULL) return; PrintTree(Boot-RChild,nLayer+1); for(int i=0;idata); PrintTree(Boot-LChild,nLayer+1); void main() BiTree T; CreateBiTree(&T); printf(先序遍历序列为：); PreOrder(T); printf(n中序遍历序列为：); InOrder(T); printf(n后序遍历序列为：); PostOrder(T); printf(n); PrintTree(T,0); getch(); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 11 页 - - - - - - - - -