数据结构课程设计报告_二叉树_哈弗曼_链表.docVIP

北京XX大学 数据结构课程设计(报告) 院 （系）：计算机与信息工程学院 班 级:软件082 学 号:XXXXXXX 姓 名:XXXXXXX 同组学生：_____________________ 指导教师______________________ 成 绩______________________ 实践地点：______________________ 实践时间：2010年5月1日至2010年5月20日 二叉树的操作： 实验目的：建立二叉树，建立后的先序。中序。后序。的遍历，及输出。 思路：用递归的方法建立二叉树，用先序建立，然后调整建立时左右孩子，和根结点的顺序， 就完成了，三种顺序的遍历。 遇到的困难：在先序建立时忘记了用#符号表示该节点没有孩子。 如何解决的：用if(ch==#) T=NULL;语句解决。 收获：明白了，二叉树的三种建立，和他们之间的区别以及递归的一些简单的应用。 运行结果：输入数字元素用#表示结点没有左孩子或右孩子。然后屏幕上显示出三种顺序的遍历。 #includeiostream.h #includestdlib.h #define NULL 0 #define OVERFLOW -2 #define OK 1 typedef int status; typedef struct TreeNode { char data; TreeNode *lchild,*rchild; }*diaoTree; status Creat_Tree(diaoTree T); status Preorder_Traversal(diaoTree T); status Inorder_Traversal(diaoTree T); status PostOrder_Traverse(diaoTree T); void main() { diaoTree t; cout先序建立:; coutendl; cout输入元素: ; Creat_Tree(t); cout先序遍历: ; Preorder_Traversal(t); coutendl; cout中序遍历: ; Inorder_Traversal(t); coutendl; cout后续遍历: ; PostOrder_Traverse(t); coutendl; } status Creat_Tree(diaoTree T) { char ch; cinch; if(ch==#) T=NULL; else{ T=(diaoTree)malloc(sizeof(TreeNode)); if(!T) exit(OVERFLOW); T-data=ch; Creat_Tree(T-lchild); Creat_Tree(T-rchild); } return OK; } status Preorder_Traversal(diaoTree T) { if(T) { coutT-data ; Preorder_Traversal(T-lchild); Preorder_Traversal(T-rchild); } return OK; } status Inorder_Traversal(diaoTree T) { if(T) { Inorder_Traversal(T-lchild); coutT-data ; Inorder_Traversal(T-rchild); } return OK; } status PostOrder_Traverse(diaoTree T) { if(T) { PostOrder_Traverse(T-lchild); PostOrder_Traverse(T-rchild); coutT-data ; } return OK; } 哈夫曼编码： 实验目的：给出各节点权值的大小，然后建立哈弗曼树，然后根据哈弗曼树给对应的权值生成对应的不等长的二进制编码。 思路：先输入权值的个数，然后输入权值的大小，再输入对应权值的英文字母，然后对每个结点的父亲，左右孩子进行初始化赋0，然后用select函数建立哈弗曼树，然后存储 根据求出的哈弗曼表建立哈弗曼码，选用左孩子为零右孩子为一，最后得出各个英文字母所对应的不等长的二进制编码。 遇到的难点：如何编写select选择函数。 如何解决的：先判断所