实验2++树型数据结构.doc

《实验2++树型数据结构.doc》由会员分享，可在线阅读，更多相关《实验2++树型数据结构.doc（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、淮海工学院计算机工程学院实验报告书课程名： 数 据 结 构 题 目： 实验2 树型数据结构及其应用 班 级： 姓 名： 评语：成绩： 指导教师： 批阅时间： 年 月 日实验2 树型数据结构实验目的和要求1熟练掌握二叉树的二叉链表存储结构；二叉树的常用遍历方法：按层遍历、先序递归遍历、中序递归和非递归遍历、后序递归遍历。2掌握按先序遍历顺序输入数据，递归建立二叉树的方法。3. 掌握建立哈夫曼树的方法，实现哈夫曼编码。实验环境 Turbo C 或VC+实验学时 4学时，必做实验实验题目1. 问题描述 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。基本要求

2、 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。测试数据 ABCDEGF（其中表示空格字符） 输出结果为： 先序：ABCDEGF 中序：CBEGDFA 后序：CGBFDBA2已知二叉树按照二叉链表方式存储，编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。提示：（1）参习题6.20，实现逐层遍历（2）队中保存每个结点的打印位置，其左、右子的距离3如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图6.34所示。A CF EAD B B C D E图6.

3、34F法 F 4按凹入表形式打印树形结构，如图6.35所示。提示：参P.129例，用先根遍历。ABDCGFEAB E FC GD A B C D E F G 图6.35实现代码和运行结果第一题（采用递归方法实现）：#include #include #include typedef char DataType;typedef struct NodeDataType data;struct Node *LChild;struct Node *RChild;BiTNode, *BiTree;void CreateBiTree(BiTree *bt)char ch;ch=getchar();if(c

4、h=.) *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)/先序遍历二叉树，root为指向二叉树（或某一子树）根结点的指针if(root!=NULL)Visit(root-data);/访问根结点PreOrder(root-LChild);/先序遍历左

5、子树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(root-data);/访问根结点void

6、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 int SElemType;typedef struct Node /定义二叉树的二叉链表结点的结构char data;stru

7、ct Node *LChild;struct Node *RChild;BiTNode,*BiTree; /创建树的结点typedef struct /定义栈的结构体BiTNode *a100;int top;Sqstack;void push(Sqstack *s,BiTNode *x) /入栈操作if (s-top=100) /栈最大空间为100coutstack overflow!top+;s-as-top=x;BiTNode *pop(Sqstack *s,BiTNode *x) /出栈操作if (s-top=0)coutstack underflow!as-top;s-top-;re

8、turn (x);int CreateBiTree(BiTree &T) /创建一棵非空二叉树Tchar ch;cinch;if(ch=.) T=NULL; /当输入“.”是表示空格字符elseif(!(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

9、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);/先访问左孩子P

10、ostorder(T-RChild);/再访问右孩子coutdata ;/访问根结点 void main()/主函数分别输出先序中序后序二叉树的结果BiTree T;cout 输入要创建树的顺序，“.”表示空格n;CreateBiTree(T);cout先序遍历的结果:;Preorder(T); coutnn;cout中序遍历的结果:;Inorder(T); coutnn;cout后序遍历的结果:;Postorder(T); coutnn;第三题：#include#include#includetypedef char DataType;typedef struct NodeDataType

11、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 Visit(char ch)printf(%c,ch);v

12、oid PreOrder(BiTree root)/*先序遍历二叉树，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!=NULL)PostOrder(root-LChild);Pos

13、tOrder(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后序遍历序列为：);PostOr

14、der(T); printf(n);PrintTree(T,0);getch();第四题：#include #include #include #define TRUE 1#define FALSE 0#define ERROR 0#define OK 1#define MAXSIZE 50 /*队列的最大长度*/typedef char DataType;typedef struct NodeDataType data;struct Node *LChild;struct Node *RChild;BiTNode, *BiTree;typedef BiTree QueueElementTyp

15、e;typedef structQueueElementType elementMAXSIZE; /* 队列的元素空间*/int front; /*头指针指示器*/int rear; /*尾指针指示器*/SeqQueue;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(&(*

16、bt)-RChild); /生成右子树/*初始化操作*/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=(Q-rear+1)%MAXSIZE; /* 重新设置队尾指针 */return(TRUE); /*操作成功*/*出队操作

17、*/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) /*提取队列的队头元素，用x返回其值*/if(Q-front=Q-rear) /*队列为空*/return(TRUE);elsereturn(FALSE);

18、/*操作成功*/ void PrintTree(BiTree p ,int nLayer)if(p=NULL) return;for(int i=0;idata);PrintTree(p-LChild,nLayer+1);PrintTree(p-RChild,nLayer);int LayerOrder(BiTree bt) SeqQueue *Q;BiTree p;Q=(SeqQueue *)malloc(sizeof(SeqQueue);InitQueue(Q); /*初始化空队列Q*/if(bt = NULL)return ERROR; /* 若二叉树bt为空树，则结束遍历*/EnterQueue(Q, bt);/* 若二叉树bt非空，则根结点bt入队，开始层次遍历*/ DeleteQueue(Q, &p);/*队头元素出队并访问 */PrintTree(p,0);return OK;/* LayerOrder */void main()BiTree T;printf(按扩展先序遍历序列把树化为二叉树，输入二叉树先序序列:n); CreateBiTree(&T);printf(层次遍历输出结点为:n);LayerOrder(T);第一题（采用递归方法实现）：第一题（采用非递归方法实现）：第三题：第四题：存在的问题及实验体会