1、完整word版树形数据结构及其应用word文档良心出品淮海工学院计算机工程学院实验报告书课程名： 数 据 结 构 题 目： 树形数据结构及其应用 班 级： 学 号： 姓 名： 实验2 树形数据结构实验目的和要求1熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先序递归遍历、中序递归和非递归遍历、后序递归遍历。2掌握按先序遍历顺序输入数据，递归建立二叉树的方法。3. 掌握建立哈夫曼树的方法，实现哈夫曼编码。实验环境 Turbo C 或VC+实验学时 4学时，必做实验实验题目1. 问题描述 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
2、基本要求 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。测试数据 ABCDEGF（其中表示空格字符） 输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA2已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。提示：（1）参习题6.20，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离3如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图6.34所示。A B C D E图6.34 F
3、主要数据结构1.typedef char DataType;typedef 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、始化操作*/4.int EnterQueue(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(BiT
5、ree root)/后序遍历二叉树12.int CreateBiTree(BiTree &T) /创建一棵非空二叉树13.void PrintTree(BiTree Boot,int nLayer) /* 打印二叉树 */主要算法1.用递归和非递归进行遍历（先序、中序、后序）2.按图进行遍历3.用队列编写二叉链表存储：初始化、入队、出队运行结果1.递归非递归2.3.实验体会1.代码可能有点冗长，对后序线索二叉树求后继节点实现的不是很好。2.这次任务量有点大，实现的函数太多，全部放在一个文件里不利于维护与修改。附源代码1.递归：#include #include #include typedef
6、 char DataType;typedef struct Node DataType data; struct Node *LChild; struct Node *RChild;BiTNode, *BiTree;void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch= ) *bt=NULL; else *bt=(BiTree)malloc(sizeof(BiTNode); (*bt)-data=ch; CreateBiTree(&(*bt)-LChild); CreateBiTree(&(*bt)-RChild); void V
7、isit(char ch) printf(%c ,ch);void PreOrder(BiTree root)/先序遍历二叉树 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!=N
8、ULL) PostOrder(root-LChild); PostOrder(root-RChild); Visit(root-data); void main() BiTree T; CreateBiTree(&T); printf(先序遍历序列为:); PreOrder(T); printf(n中序遍历序列为:); InOrder(T); printf(n后序遍历序列为:); PostOrder(T); getch();非递归：#include using namespace std;#define OK 1#define ERROR 0#define OVERFLOW -2typedef
9、 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-top=x; BiTNode *pop(Sqstack *s,BiTNode *x) if (s-top=0) coutstack underf
10、low!as-top; s-top-; return (x); int CreateBiTree(BiTree &T) /创建一棵非空二叉树 char ch; cinch; if(ch=.) T=NULL; else 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); Preor
11、der(T-RChild); void Inorder(BiTree T) /中序非递归操作遍历二叉树 Sqstack s; BiTNode *p; s.top=0; push(&s,T); while (s.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
12、-RChild); coutdata ; void main() BiTree T; cout 输入要创建树的顺序:; 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;按照右根左方式遍历孩子兄弟表示树，然后先根遍历。#in
13、clude stdio.h#include #include #define TRUE 1#define FALSE 0#define ERROR 0#define OK 1#define MAXSIZE 50 /*队列的最大长度*/Typedef char DataTpyetypedef struct Node DataType data; struct Node *LChild; struct Node *RChild;BiTNode, *BiTree;typedef BiTree QueueElementType;typedef struct QueueElementType eleme
14、ntMAXSIZE; /* 队列的元素空间*/ int front; /*头指针指示器*/ int rear; /*尾指针指示器*/SeqQueue;/*初始化操作*/void InitQueue(SeqQueue *Q) /* 将*Q初始化为一个空的循环队列 */ Q-front=Q-rear=0;/*入队操作*/int EnterQueue(SeqQueue *Q, QueueElementType x) /*将元素x入队*/ if(Q-rear+1)%MAXSIZE=Q-front) /*队列已经满了*/ return(FALSE); Q-elementQ-rear=x; Q-rear=
15、(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */ return(TRUE); /*操作成功*/*出队操作*/int DeleteQueue(SeqQueue *Q, QueueElementType *x) /*删除队列的队头元素，用x返回其值*/ if(Q-front=Q-rear) /*队列为空*/ return(FALSE); *x=Q-elementQ-front; Q-front=(Q-front+1)%MAXSIZE; /*重新设置队头指针*/ return(TRUE); /*操作成功*/int IsEmpty(SeqQueue *Q) /*提取队列的队头元素，
16、用x返回其值*/ if(Q-front=Q-rear) /*队列为空*/ return(TRUE); else return(FALSE); /*操作成功*/int LayerOrder(BiTree bt) SeqQueue *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);/* 若
17、二叉树bt非空，则根结点bt入队，开始层次遍历*/ while(!IsEmpty(Q)/*若队列非空，则遍历为结束，继续进行*/ DeleteQueue(Q, &p);/*队头元素出队并访问 */ printf(%c ,p-data); if(p-LChild ) EnterQueue(Q, p-LChild);/*若p的左孩子非空，则进队*/ if(p-RChild ) EnterQueue(Q, p-RChild); /*若p的右孩子非空，则进队*/ /*while*/ return OK;/* LayerOrder */void main() BiTree T; printf(按扩展先序
18、遍历序列建立二叉树，请输入序列:n); CreateBiTree(&T); printf(层次遍历输出结点为:); LayerOrder(T); getch();3.#include#include#includetypedef char DataType;typedef struct Node DataType data; struct Node *LChild; struct Node *RChild;BiTNode, *BiTree;void CreateBiTree(BiTree *bt) char ch; ch=getchar(); if(ch= ) *bt=NULL; else *
19、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) Visit(root-data); PreOrder(root-LChild); PreOrder(root-RChild); void InOrder(BiTree root) if(root!=NULL) InOrder(roo
20、t-LChild); Visit(root-data); InOrder(root-RChild); void PostOrder(BiTree root) if(root!=NULL) PostOrder(root-LChild); PostOrder(root-RChild); 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();
