树的实验报告

2011-2012学年第一学期数据结构课内实验报告 学院：计算机学院 专业：计算机科学与技术 姓名: 学号： 指导老师： 实验题目1、 实验目的1. 掌握二叉树的建立，递归遍历（先序，中序，后序），打印树状二叉树，计算叶子节点的个数。2. 二叉树的非递归遍历3. 掌握哈夫曼树的基本算法。2、 实验内容1.树的递归与非递归遍历 (1) 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树(以先序来建立)， (2) 将此二叉树按照“树状形式”打印输出， (3) 对其进行遍历(先序、中序和后序)， (4) 最后将遍历结果打印输出在遍历算法中 (5) 要求至少有一种遍历采用非递归方法2.哈夫曼 基本要求： (1) 从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树； (2) 打印每一个字符对应的哈夫曼编码。 (3) 对从终端读入的字符串进行编码，并显示编码结果。四：模块化分各个模块详细的功能描述。void PreOrder(BTree root);先序遍历void InOrder(BTree root);中序遍历void PostOrder(BTree root);后序遍历void Preleaf(BTree root);先序求叶子节点个数void PrintfTree(BTree root,int h);打印二叉树int PostHeight(BTree root);后序求树的深度void InitTree(BiTree *bt);初始化树int InitStack(Stack *top);初始化栈BiTnode * Create();/扩展结点创建二叉树int Push(Stack *top,BiTree p);入栈int Pop(Stack *top,BiTree *p);出栈int GetTop(Stack top,BiTree p);取栈顶元素void PreStack(BTree root);/非递归先序遍历void Select(HTree ht,int pos/*寻找的范围*/,int *s1,int *s2) /查找最小的两个节点的下标void CreatHuffmanTree(HTree ht,int w,int n) /创建哈夫曼树voi Output(HTree ht,int n) /输出哈夫曼树void CodeHuffmanTree(HTree ht,HCode hc,int n) /编码void OutputCode(HCode hc,int w,int n) /输出编码3、 详细设计及运行结果void preOrder(BiTree bt)/先序遍历。if(bt!=NULL)printf(%c,bt-data);preOrder(bt-LChild);preOrder(bt-RChild);void InOrder(BiTree bt)/中序遍历。if(bt!=NULL)InOrder(bt-LChild);printf(%c,bt-data);InOrder(bt-RChild);void PostOrder(BiTree bt)/后序遍历。if(bt!=NULL)PostOrder(bt-LChild);PostOrder(bt-RChild);printf(%c,bt-data);void Traver(BiTree bt)int PostTreeDepth(BiTree bt)int hl,hr,max;if(bt!=NULL)hl=PostTreeDepth(bt-LChild);hr=PostTreeDepth(bt-RChild);max=hlhr?hl:hr;return(max+1);elsereturn 0;void PreStack(BiTree bt)/非递归遍历BiTree p;LinkStack s;InitStack(&s);/p=bt;PushStack(s, bt);while(!Isempty(s)PopStack(s, &p);printf(%c,p-data);if(p-RChild != NULL)PushStack(s,p-RChild);if(p-LChild != NULL)PushStack(s, p-LChild);/*void PreStack(BiTree bt)/非递归先序遍历BiTree p;LinkStack s;InitStack(&s);p=bt;while(p|!Isempty(s)if(p)printf(%c,p-data);PushStack(s,p);p=p-LChild;elsePopStack(s,&p);p=p-RChild;*/void PrintTree(BiTree bt,int nLayer)int i;if(bt=NULL)return;PrintTree(bt-RChild,nLayer+1);for(i=0;idata);PrintTree(bt-LChild,nLayer+1);void LeafTree(BiTree bt)/树的叶子结点遍历if(bt!=NULL)if(bt-LChild=NULL&bt-RChild=NULL)printf(%c,bt-data);LeafTree(bt-LChild);LeafTree(bt-RChild);void Travel(BiTree bt)/树的按层遍历BiTree p;LinkQueue Q;InitQueue(&Q);if(bt=NULL)return;p=bt;EnterQueue(&Q,p);while(Q.front!=Q.rear)DeleteQueue(&Q,&p);printf(%c,p-data);if(p-LChild)EnterQueue(&Q,p-LChild);if(p-RChild)EnterQueue(&Q,p-RChild);2：哈弗曼void Creat(HuffmanTree ht,int w,char p,int n)/构造哈弗曼树。int s1,s2,i;for(i=1;i=n;i+)/前n个叶子结点的初始化hti.weight=wi;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)/权值的初始化。select(ht,i-1,&s1,&s2);hti.weight=hts1.weight+hts2.weight;hti.parent=0;hts1.parent=i;hts2.parent=i;hti.LChild=s1;hti.RChild=s2;/生成哈弗曼树的函数编码。void OrderHuffman(HuffmanTree ht,Huffmancode hc,char str,int m)/根据哈弗曼树构成哈弗曼编码表hc。int qN;char *cd;/临时存放编码串。int c,p,i;/c,p分别为孩子和双亲。int start;/制定编码cd的起始位置。cd=(char *)malloc(m*sizeof(char);cdm-1=0;/最后一位置放上字符串的结束标志。i=0;while(im)switch(stri)case s:qi=3;break;case t:qi=4;break;case a:qi=2;break;case e:qi=6;break;default: break;start=m-1;c=qi;p=htqi.parent;while(p!=0)-start;if(htp.LChild=c)cdstart=0;/左孩子生成0else/右孩子生成1cdstart=1;c=p;p=htp.parent;hci=(char *)malloc(m-start)*sizeof(char);strcpy(hci,&cdstart);printf(%s,hci);i+;free(cd);void print(HuffmanTree ht,int n)int i;for(i=1;i=2*n-1;i+)printf(%4d%4d%4dn,hti.weight,hti.LChild,hti.RChild);4、 调试情况，设计技巧及体会1对自己的设计进行评价，指出合理和不足之处，提出改进方案； 打印树状二叉树的模块没有能按照自然数的形式打印，有待改进。2对设计及调试过程的心得体会。5、 源程序清单（电子版）/*建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。1:从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树(以先序来建立)，2:将此二叉树按照“树状形式”打印输出，3:对其进行遍历(先序、中序和后序)，4:最后将遍历结果打印输出在遍历算法中5:要求至少有一种遍历采用非递归方法。*/#include#include#include#define FALSE 0#define TRUE 1typedef struct Nodechar data;struct Node *LChild;struct Node *RChild;BitNode,*BiTree;typedef struct nodBiTree elem;struct nod *next;SeqStack,*LinkStack;void InitStack(LinkStack *top)(*top)=(LinkStack)malloc(sizeof(SeqStack);(*top)-next=NULL;int Isempty(LinkStack top)if(top-next=NULL)return TRUE;return FALSE;int PushStack(LinkStack top,BiTree x)LinkStack temp;temp=(SeqStack *)malloc(sizeof(SeqStack);if(temp=NULL)return FALSE;temp-elem=x;temp-next=top-next;top-next=temp;return TRUE;int PopStack(LinkStack top,BiTree *x)LinkStack temp;temp=top-next;if(temp=NULL)return FALSE;*x=temp-elem;top-next=temp-next;free(temp);return TRUE;int CreatBiTree(BiTree *bt)/树的先序建立char ch;ch=getchar();if(ch=#)*bt=NULL;else*bt=(BitNode *)malloc(sizeof(BitNode);if(*bt=NULL)return 0;(*bt)-data=ch;CreatBiTree(&(*bt)-LChild);CreatBiTree(&(*bt)-RChild);return 1;typedef struct nodeBiTree w;struct node *next;LinkNode;typedef structLinkNode *front;LinkNode *rear;LinkQueue;int InitQueue(LinkQueue *Q)Q-front=(LinkNode *)malloc(sizeof(LinkNode);if(Q-front!=NULL)Q-rear=Q-front;Q-front-next=NULL;return TRUE;elsereturn FALSE;int EnterQueue(LinkQueue *Q,BiTree x)LinkNode *NewNode;NewNode=(LinkNode *)malloc(sizeof(LinkQueue);if(NewNode!=NULL)NewNode-w=x;NewNode-next=NULL;Q-rear-next=NewNode;Q-rear=NewNode;return TRUE;elsereturn FALSE;int DeleteQueue(LinkQueue *Q,BiTree *x)LinkNode *p;if(Q-front=Q-rear)return FALSE;p=Q-front-next;Q-front-next=p-next;if(Q-rear=p)Q-rear=Q-front;*x=p-w;free(p);return TRUE;void preOrder(BiTree bt)/先序遍历。if(bt!=NULL)printf(%c,bt-data);preOrder(bt-LChild);preOrder(bt-RChild);void InOrder(BiTree bt)/中序遍历。if(bt!=NULL)InOrder(bt-LChild);printf(%c,bt-data);InOrder(bt-RChild);void PostOrder(BiTree bt)/后序遍历。if(bt!=NULL)PostOrder(bt-LChild);PostOrder(bt-RChild);printf(%c,bt-data);void Traver(BiTree bt)int PostTreeDepth(BiTree bt)int hl,hr,max;if(bt!=NULL)hl=PostTreeDepth(bt-LChild);hr=PostTreeDepth(bt-RChild);max=hlhr?hl:hr;return(max+1);elsereturn 0;void PreStack(BiTree bt)/非递归遍历BiTree p;LinkStack s;InitStack(&s);/p=bt;PushStack(s, bt);while(!Isempty(s)PopStack(s, &p);printf(%c,p-data);if(p-RChild != NULL)PushStack(s,p-RChild);if(p-LChild != NULL)PushStack(s, p-LChild);/*void PreStack(BiTree bt)/非递归先序遍历BiTree p;LinkStack s;InitStack(&s);p=bt;while(p|!Isempty(s)if(p)printf(%c,p-data);PushStack(s,p);p=p-LChild;elsePopStack(s,&p);p=p-RChild;*/void PrintTree(BiTree bt,int nLayer)int i;if(bt=NULL)return;PrintTree(bt-RChild,nLayer+1);for(i=0;idata);PrintTree(bt-LChild,nLayer+1);void LeafTree(BiTree bt)/树的叶子结点遍历if(bt!=NULL)if(bt-LChild=NULL&bt-RChild=NULL)printf(%c,bt-data);LeafTree(bt-LChild);LeafTree(bt-RChild);void Travel(BiTree bt)/树的按层遍历BiTree p;LinkQueue Q;InitQueue(&Q);if(bt=NULL)return;p=bt;EnterQueue(&Q,p);while(Q.front!=Q.rear)DeleteQueue(&Q,&p);printf(%c,p-data);if(p-LChild)EnterQueue(&Q,p-LChild);if(p-RChild)EnterQueue(&Q,p-RChild);void main()BiTree bt;int nLayer;CreatBiTree(&bt);nLayer=PostTreeDepth(bt);printf(树的深度：%dn,nLayer);printf(树的树状打印：n);PrintTree(bt,nLayer);printf(前序访问：n);preOrder(bt);printf(n);printf(中序访问：n);InOrder(bt);printf(n);printf(后序访问：n);PostOrder(bt);printf(n);printf(非递归访问：n);PreStack(bt);printf(n);printf(树的叶子结点有:n);LeafTree(bt);printf(n);printf(树的按层遍历：n);Travel(bt);printf(n);2：/huffman#include#include#include#define N 20#define M 2*N-1typedef char * HuffmancodeN+1;typedef structint weight;int parent;int LChild;int RChild;HTNode,HuffmanTreeM+1;/建立哈弗曼树的几个函数。void select(HuffmanTree ht,int pos,int *s1,int *s2)/寻找最小孩子 形成最优二叉树。int m1,m2;int i;m1=m2=32767;for(i=1;i=pos;i+)if(hti.parent=0&hti.weightm1)m2=m1;m1=hti.weight;*s2=*s1;*s1=i;else if(hti.parent=0&hti.weight*s2)i=*s1;*s1=*s2;*s2=i;void Creat(HuffmanTree ht,int w,char p,int n)/构造哈弗曼树。int s1,s2,i;for(i=1;i=n;i+)/前n个叶子结点的初始化hti.weight=wi;hti.parent=0;hti.LChild=0;hti.RChild=0;for(i=n+1;i=2*n-1;i+)/权值的初始化。select(ht,i-1,&s1,&s2);hti.weight=hts1.weight+hts2.weight;hti.parent=0;hts1.parent=i;hts2.parent=i;hti.LChild=s1;hti.RChild=s2;/生成哈弗曼树的函数编码。void OrderHuffman(HuffmanTree ht,Huffmancode hc,char str,int m)/根据哈弗曼树构成哈弗曼编码表hc。int qN;char *cd;/临时存放编码串。int c,p,i;/c,p分别为孩子和双亲。int start;/制定编码cd的起始位置。cd=(char *