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

《数据结构 树和二叉树代码.docx》由会员分享，可在线阅读，更多相关《数据结构 树和二叉树代码.docx（11页珍藏版）》请在三一办公上搜索。

1、数据结构 树和二叉树代码树和二叉树 一、实验目的： 参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。 二、实验要求： 1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1设计实现二叉树类，要求： 编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。 实现二叉树层次遍历的非递归算法。 假设二叉树

2、采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。 编写求二叉树高度的函数 编写一主函数来验证算法实现。 2. 设计实现二叉线索链表类，要求： 编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。 编写一主函数来验证算法实现。 *3. 编写创建哈夫曼树和生成哈夫曼编码的算法。 *4假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。 *5假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度 四、程序样例 #include #include using namespace std; t

3、emplate struct BiNode T data; BiNode *lchild, *rchild; ; int max(int a,int b) return a b ? a : b; template class BiTree public: BiTree( ); /构造函数，初始化一棵空的二叉树 BiTree/二叉树的析构函数算法BiTree Release(root); void InOrder InOrder(root); /中序遍历二叉树 void PreOrder PreOrder(root); void PostOrderPostOrder(root); /后序遍历二叉

4、树 void LeverOrderLeverOrder(root); /层序遍历二叉树 void CountCount(root); void PreOrdercntPreOrdercnt(root); int Depthint www = Depth(root); return www; private: BiNode *root; /指向根结点的头指针 void Creat(BiNode *&root); void PreOrder(BiNode *root); /前序遍历二叉树 void InOrder(BiNode *root); void PostOrder(BiNode *root

5、); 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 (

6、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+

7、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

8、(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

9、)/二叉树的中序遍历递归算法InOrder if (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:Pre

10、Ordercnt(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

11、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二叉树的

12、深度: ; cout mytree.Depthendl; return 0; 2. /声明类InThrBiTree及定义结构ThrNode，文件名为inthrbitree.h #ifndef INTHRBITREE_H #define INTHRBITREE_H enum flag Child, Thread; /枚举类型，枚举常量Child=0，Thread=1 template struct ThrNode /二叉线索树的结点结构 T data; ThrNode *lchild, *rchild; flag ltag, rtag; ; template class InThrBiTree

13、public: InThrBiTree( ); /构造函数，建立中序线索链表 InThrBiTree( ); /析构函数，释放线索链表中各结点的存储空间 ThrNode* Getroot( ); /获取根结点 ThrNode* Next(ThrNode* p); /查找结点p的后继 void InOrder(ThrNode* root); /中序遍历线索链表 private: ThrNode* root; /指向线索链表的头指针 ThrNode* Creat( ); /构造函数调用 void ThrBiTree(ThrNode* root); /构造函数调用 void Release(ThrN

14、ode* root); /析构函数调用 ; #endif /定义类InThrBiTree中的成员函数，文件名为inthrbitree.cpp #include #include #includeinthrbitree.h using namespace std; /构造一棵中序线索二叉树 template InThrBiTree:InThrBiTree( ) ThrNode* pre = NULL; this-root = Creat( ); ThrBiTree(root); /释放中序线索二叉链表中各结点的存储空间 template InThrBiTree:InThrBiTree(void)

15、 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; /中序

16、遍历一棵线索二叉树 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

17、( ) 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 (

18、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); /释放中序线索二

19、叉树的存储空间，析构函数调用 template void InThrBiTree:Release(ThrNode* root) if (root!=NULL) Release(root-lchild); /释放左子树 Release(root-rchild); /释放右子树 delete root; /线索二叉树的主函数，文件名为inthrbitreemain.cpp #include #include #includeinthrbitree.cpp using namespace std; ThrNode* pre; void main InThrBiTree inbt;/构造一棵线索二叉树 ThrNode* p = inbt.Getroot( ); /获取指向根结点的指针 cout-中序遍历线索二叉树-endl; inbt.InOrder(p); 注意问题 1注意理解有关树的各种递归算法的执行步骤。 2注意字符类型数据在输入时的处理。 3重点理解如何利用栈结构实现非递归算法。