数据结构 树和二叉树代码.doc

树和二叉树一、实验目的：参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。二、实验要求：1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1设计实现二叉树类，要求：（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。 （3） 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。（4）编写求二叉树高度的函数 （5）编写一主函数来验证算法实现。2. 设计实现二叉线索链表类，要求：（1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。（2）编写一主函数来验证算法实现。*3. 编写创建哈夫曼树和生成哈夫曼编码的算法。*4假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。*5假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数）四、程序样例#include#includeusing namespace std;template struct BiNodeT data;BiNode *lchild, *rchild;int max(int a,int b)return a b ? a : b; template class BiTreepublic:BiTree( ); /构造函数，初始化一棵空的二叉树BiTree()/二叉树的析构函数算法BiTreeRelease(root); void InOrder() InOrder(root); /中序遍历二叉树void PreOrder() PreOrder(root);void PostOrder()PostOrder(root); /后序遍历二叉树void LeverOrder()LeverOrder(root); /层序遍历二叉树void Count()Count(root);void PreOrdercnt()PreOrdercnt(root);int Depth()int www = Depth(root); return www;private:BiNode *root; /指向根结点的头指针void Creat(BiNode *&root);void PreOrder(BiNode *root); /前序遍历二叉树 void InOrder(BiNode *root); void PostOrder(BiNode *root);void LeverOrder(BiNode *root); /层序遍历二叉树void Release(BiNode *root); /析构函数调用void Count(BiNode *root) ;/求二叉树的结点个数void PreOrdercnt(BiNode *root);/设计算法按前序次序打印二叉树中的叶子结点;int Depth(BiNode *root);/深度；;template BiTree:BiTree()Creat(root);template void BiTree :Creat(BiNode *&root) char ch; cinch; if (ch=#) root=NULL; /建立一棵空树else root=new BiNode; /生成一个结点root-data=ch;Creat(root-lchild); /递归建立左子树Creat(root-rchild); /递归建立右子树 template void BiTree:LeverOrder(BiNode *root)BiNode * Q100;int front = 0, rear = 0; /采用顺序队列，并假定不会发生上溢if (root=NULL) return; Q+rear=root;while (front!=rear)BiNode * q=Q+front;coutdatalchild!=NULL) Q+rear=q-lchild;if (q-rchild!=NULL) Q+rear=q-rchild; template void BiTree:PostOrder(BiNode *root) if (root = NULL) return; /递归调用的结束条件else PostOrder(root-lchild); /后序递归遍历root的左子树PostOrder(root - rchild);/后序递归遍历root的右子树coutdata ;/访问根结点的数据域template void BiTree:PreOrder(BiNode *root) if (root =NULL) return; /递归调用的结束条件else coutdatalchild); /前序递归遍历root的左子树PreOrder(root-rchild); /前序递归遍历root的右子树 template void BiTree :Release(BiNode *root)if (root!=NULL) Release(root-lchild); /释放左子树Release(root-rchild); /释放右子树delete root; template void BiTree:InOrder (BiNode *root)/二叉树的中序遍历递归算法InOrderif (root=NULL) return; /递归调用的结束条件else InOrder(root-lchild); /中序递归遍历root的左子树coutdatarchild); /中序递归遍历root的右子树int n = 0;template void BiTree:Count(BiNode *root) /n为全局量并已初始化为0 if (root) Count(root-lchild); n+; /求二叉树的结点个数 Count(root-rchild); int cnt = 0;template void BiTree:PreOrdercnt(BiNode *root)/设计算法按前序次序打印二叉树中的叶子结点; if (root) if (!root-lchild & !root-rchild) coutdata lchild); PreOrdercnt(root-rchild); template int BiTree:Depth(BiNode *root)/算法求二叉树的深度 if (root=NULL) return 0; else int hl= Depth(root-lchild); int hr= Depth(root -rchild); return max(hl, hr)+1; int main() BiTree mytree; cout 结点总个数: ; mytree.Count();coutnendl; cout endl; cout 前序遍利: ; mytree.PreOrder(); cout endl; cout 中序遍利: ; mytree.InOrder();cout endl; cout后序遍利: ; mytree.PostOrder(); cout endl; cout层序遍利: ; mytree.LeverOrder(); cout endl; cout叶子结点为: ; mytree.PreOrdercnt(); cout 个数: ; coutcnt ; cout endl; cout二叉树的深度: ; cout mytree.Depth()endl; return 0;2./声明类InThrBiTree及定义结构ThrNode，文件名为inthrbitree.h#ifndef INTHRBITREE_H#define INTHRBITREE_Henum flag Child, Thread; /枚举类型，枚举常量Child=0，Thread=1template struct ThrNode /二叉线索树的结点结构 T data; ThrNode *lchild, *rchild; flag ltag, rtag;template class InThrBiTreepublic: InThrBiTree( ); /构造函数，建立中序线索链表 InThrBiTree( ); /析构函数，释放线索链表中各结点的存储空间ThrNode* Getroot( ); /获取根结点 ThrNode* Next(ThrNode* p); /查找结点p的后继 void InOrder(ThrNode* root); /中序遍历线索链表private: ThrNode* root; /指向线索链表的头指针 ThrNode* Creat( ); /构造函数调用 void ThrBiTree(ThrNode* root); /构造函数调用 void Release(ThrNode* root); /析构函数调用;#endif/定义类InThrBiTree中的成员函数，文件名为inthrbitree.cpp#include#include#includeinthrbitree.husing namespace std;/构造一棵中序线索二叉树template InThrBiTree:InThrBiTree( ) ThrNode* pre = NULL;this-root = Creat( ); ThrBiTree(root);/释放中序线索二叉链表中各结点的存储空间template InThrBiTree:InThrBiTree(void) Release(root);/获取指向中序线索二叉树根结点的指针template ThrNode* InThrBiTree:Getroot( )return root;/输出指向结点p的后继结点的指针template ThrNode* InThrBiTree:Next(ThrNode* p)ThrNode* q; if (p-rtag=Thread) q = p-rchild; /右标志为1，可直接得到后继结点 else q = p-rchild; /工作指针初始化 while (q-ltag=Child) /查找最左下结点 q = q-lchild; return q;/中序遍历一棵线索二叉树template void InThrBiTree:InOrder(ThrNode *root) ThrNode* p = root; if (root=NULL) return; /如果线索链表为空，则空操作返回 while (p-ltag=Child) /查找中序遍历序列的第一个结点p并访问 p = p-lchild; coutdatarchild!=NULL) /当结点p存在后继，依次访问其后继结点 p = Next(p); coutdata ; coutendl;/构造一棵二叉树,构造函数调用template ThrNode* InThrBiTree:Creat( )ThrNode *root;T ch;cout请输入创建一棵二叉树的结点数据ch; if (ch=#) root = NULL; else root=new ThrNode; /生成一个结点 root-data = ch; root-ltag = Child; root-rtag = Child; root-lchild = Creat( ); /递归建立左子树 root-rchild = Creat( ); /递归建立右子树 return root;/给二叉树建立线索template void InThrBiTree:ThrBiTree(ThrNode *root) if (root=NULL) return; /递归结束条件 ThrBiTree(root-lchild); if (!root-lchild) /对root的左指针进行处理 root-ltag = Thread; root-lchild = pre; /设置pre的前驱线索 if (!root-rchild) root-rtag = Thread; /对root的右指针进行处理 if(pre != NULL) if (pre-rtag=Thread) pre-rchild = root; /设置pre的后继线索 pre = root; ThrBiTree(root-rchild);/释放中序线索二叉树的存储空间，析构函数调用templatevoid InThrBiTree:Release(ThrNode* root) if (root!=NULL) Release(root-lchild); /释放左子树 Release(root-rchild); /释放右子树 delete root