二叉树实验报告

1、实 验 报 告课程名称 data structure 专业班级 计算机1441 姓 名 刘博楠 学 号 19 计算机技术与工程学院和谐 勤奋 求是 创新实验教学考核和成绩评定办法1 课内实验考核成绩，严格按照该课程教学大纲中明确规定的比重执行。实验成绩不合格者，不能参加课程考试，待补做合格后方能参加考试。2 单独设立的实验课考核按百分制评分，考核内容应包括基本理论、实验原理和实验。3 实验考核内容包括：1）实验预习；2）实验过程（包括实验操作、实验记录和实验态度、表现）；3）实验报告；权重分别为0.2 、0.4 、 0.4；原则上根据上述三个方面进行综合评定。学生未取得1）和2）项成绩时，第3

2、）项成绩无效。4 实验指导教师应严格按照考核内容分项给出评定成绩，并及时批改实验报告，给出综合成绩，反馈实验中出现的问题。实验成绩在教师手册中有记载。实验报告主要内容一 实验目的 二 实验仪器及设备三 实验原理四 实验步骤五 实验记录及原始记录六 数据处理及结论七 实验体会（可选项）注：1. 为了节省纸张，保护环境，便于保管实验报告，统一采用A4纸，实验报告建议双面打印（正文采用宋体五号字）或手写,右侧装订。2. 实验类别指验证、演示、综合、设计、创新（研究）、操作六种类型实验。3. 验证性实验：是指为了使学生巩固课程基本理论知识而开设的强调演示和证明，注重实验结果（事实、概念或理论）的实验。

3、4. 综合性实验：是指实验内容涉及本课程的综合知识或本课程相关的课程知识的实验。5. 设计性实验：是指给定实验目的、要求和实验条件，由学生自行设计实验方案并加以实现的实验。实验题目binary tree实验室311机房实验时间2015 年 11 月23 日 实验类别验证同组人数1 成 绩一、experiment purposes1Master logical structure of binary tree; 2Master the storage structure based on binary linked list ;3Master four traversal methods of

4、binary trees.二、experiment content1Construct a binary tree which contains n nodes and is stored by binary linked list.2Traverse the binary tree by preorder, inorder, postorder, and level order.3 Find the depth, the number of nodes and the parent of a node whose data field is x, and print the leaf nod

5、es.4Construct a Huffman tree.(选作)( 其中，1、2、3题是一个程序，4题是一个程序，共两个大程序；1、2题程序在word文档中已给出，大家只是在此程序基础上添加3题的4个成员函数即可；哈夫曼树的构造可以参考书上134页的函数，此题不用C+，用C语言即可完成，134页是一个子函数，自己再编写一个select子函数，然后再写一个主函数就可以了)三、Program and running results1./声明类BiTree及定义结构BiNode,文件名为bitree.h/#include "StdAfx.h"#include"iost

6、ream"using namespace std;template <class T>struct BiNode /二叉树的结点结构 T data; BiNode<T> *lchild, *rchild;template <class T>class BiTreepublic: BiTree( ); /构造函数，初始化一棵二叉树，其前序序列由键盘输入 BiTree(void); /析构函数，释放二叉链表中各结点的存储空间BiNode<T>* Getroot(); /获得指向根结点的指针 void PreOrder(BiNode<T

7、> *root); /前序遍历二叉树 void InOrder(BiNode<T> *root); /中序遍历二叉树 void PostOrder(BiNode<T> *root); /后序遍历二叉树 void LeverOrder(BiNode<T> *root); /层序遍历二叉树int Depth(BiNode<T> *root);int Count(BiNode<T> *root); void Parent(BiNode<T> *root,T x);void Print(BiNode<T> *ro

8、ot);BiNode<T> *p;private: BiNode<T> *root; /指向根结点的头指针 BiNode<T> *Creat(); /有参构造函数调用 void Release(BiNode<T> *root); /析构函数调用 ;/定义类中的成员函数，文件名为bitree.cpp/#include<iostream.h>/#include"bitree.h"/* *前置条件：二叉树不存在 *输 入：无 *功 能：构造一棵二叉树 *输 出：无 *后置条件：产生一棵二叉树 */template<

9、class T>BiTree<T>:BiTree( )this->root = Creat( );/* *前置条件：二叉树已存在 *输 入：无 *功 能：释放二叉链表中各结点的存储空间 *输 出：无 *后置条件：二叉树不存在 */template<class T>BiTree<T>:BiTree(void)Release(root);/* *前置条件：二叉树已存在 *输 入：无 *功 能：获取指向二叉树根结点的指针 *输 出：指向二叉树根结点的指针 *后置条件：二叉树不变 */template<class T>BiNode<T&

10、gt;* BiTree<T>:Getroot( )return root;/*深度*/template<class T>int BiTree<T>:Depth(BiNode<T> *root)if(root=NULL) return 0;elseint h1=Depth(root->lchild);int h2=Depth(root->rchild);return (h1>h2?h1:h2)+1;/*节点数*/template<class T>int BiTree<T>:Count(BiNode<T

11、> *root) static count=0;if(root=NULL) return 0;elsecount+;Count(root->lchild);Count(root->rchild);return count;/*双亲*/template<class T>void BiTree<T>:Parent(BiNode<T> *root,T x)if(root=NULL) if(x=root->data) return ;else p=root;Parent(root->lchild,x);Parent(root->r

12、child,x);cout<<x<<"的双亲节点为"<<root->data<<endl;/*打印*/template<class T>void BiTree<T>:Print(BiNode<T> *root)if(root)if(!root->lchild&&!root->rchild)cout<<root->data<<" "Print(root->lchild);Print(root->rc

13、hild);/* *前置条件：二叉树已存在 *输 入：无 *功 能：前序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */template<class T>void BiTree<T>:PreOrder(BiNode<T> *root)if(root=NULL) return;elsecout<<root->data<<" " PreOrder(root->lchild);PreOrder(root->rchild);/* *前置条件：二叉树已存在 *输 入：无 *功

14、能：中序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */template <class T>void BiTree<T>:InOrder (BiNode<T> *root) if (root=NULL) return; /递归调用的结束条件 else InOrder(root->lchild); /中序递归遍历root的左子树 cout<<root->data<<" " /访问根结点的数据域 InOrder(root->rchild); /中序递归遍历root的右子树

15、/* *前置条件：二叉树已存在 *输 入：无 *功 能：后序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */template <class T>void BiTree<T>:PostOrder(BiNode<T> *root) if (root=NULL) return; /递归调用的结束条件 else PostOrder(root->lchild); /后序递归遍历root的左子树 PostOrder(root->rchild); /后序递归遍历root的右子树 cout<<root->data&

16、lt;<" " /访问根结点的数据域/* *前置条件：二叉树已存在 *输 入：无 *功 能：层序遍历二叉树 *输 出：二叉树中结点的一个线性排列 *后置条件：二叉树不变 */template <class T>void BiTree<T>:LeverOrder(BiNode<T> *root)const int MaxSize = 100;int front = 0;int rear = 0; /采用顺序队列，并假定不会发生上溢BiNode<T>* QMaxSize; BiNode<T>* q;if (roo

17、t=NULL) return;elseQrear+ = root;while (front != rear)q = Qfront+; cout<<q->data<<" " if (q->lchild != NULL) Qrear+ = q->lchild;if (q->rchild != NULL) Qrear+ = q->rchild;/* *前置条件：空二叉树 *输 入：数据ch; *功 能：初始化一棵二叉树,构造函数调用 *输 出：无 *后置条件：产生一棵二叉树 */template <class T>

18、BiNode<T>* BiTree<T>:Creat( )BiNode<T>* root;T ch;cout<<"请输入创建一棵二叉树的结点数据"<<endl;cin>>ch; if (ch='#') root = NULL; else root = new BiNode<T> /生成一个结点 root->lchild = Creat( ); /递归建立左子树root->data=ch; root->rchild = Creat( ); /递归建立右子树 r

19、eturn root;/* *前置条件：二叉树已经存在 *输 入：无 *功 能：释放二叉树的存储空间，析构函数调用 *输 出：无 *后置条件：二叉树不存在 */template<class T>void BiTree<T>:Release(BiNode<T>* root) if (root != NULL) Release(root->lchild); /释放左子树 Release(root->rchild); /释放右子树 delete root; / 主函数，文件名为main.cpp/#include<iostream.h>/#i

20、nclude"bitree.cpp"void main()BiTree<char> bt; /创建一棵树BiNode<char>* root = bt.Getroot(); /获取指向根结点的指针 cout<<"计算机1441"<<endl;cout<<"刘博楠"<<endl; cout<<"-二叉树深度- "<<endl; cout<<"二叉树深度为"<<bt.Depth(r

21、oot)<<endl;cout<<"-二叉树节点个数- "<<endl;cout<<"二叉树节点个数为"<<bt.Count(root)<<endl;cout<<"-节点x双亲- "<<endl;bt.Parent(root,'b');cout<<"-叶子节点- "<<endl; bt.Print(root);cout<<endl;cout<<"-

22、前序遍历- "<<endl;bt.PreOrder(root);cout<<endl;cout<<"-中序遍历- "<<endl;bt.InOrder(root);cout<<endl;cout<<"-后序遍历- "<<endl;bt.PostOrder(root);cout<<endl;cout<<"-层序遍历- "<<endl;bt.LeverOrder(root);cout<<endl;2

23、.#include <stdio.h>#define MAXVALUE 10000#define MAXLEAF 30#define MAXNODE MAXLEAF*2 -1typedef struct int weight; int parent; int lchild; int rchild; HNodeType; void HuffmanTree (HNodeType HuffNodeMAXNODE, int n) int i, j, m1, m2, x1, x2; for (i=0; i<2*n-1; i+) HuffNodei.weight = 0; HuffNodei.parent =-1; HuffNodei.lchild =-1; HuffNodei.rchild =-1; for (i=0;