数据结构树与叉树代码

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

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

3、m>#include<queue>using namespace std;template <class T>struct BiNodeT data;BiNode<T> *lchild, *rchild;int max（int a,int b）return a > b ? a : b; template <class T>class BiTreepublic:9 / 8BiTree( ); /构造函数，初始化一棵空的二叉树BiTree()/ 二叉树的析构函数算法 BiTree Release(root); void InOrder()

4、 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<T> *root; / 指向根结点的头指针void Creat(

5、BiNode<T> *&root);void PreOrder(BiNode<T> *root); / void InOrder(BiNode<T> *root);void PostOrder(BiNode<T> *root);void LeverOrder(BiNode<T> *root); /void Release(BiNode<T> *root); /void Count(BiNode<T> *root) ;/void PreOrdercnt(BiNode<T> *root);/ 的

6、叶子结点 ;前序遍历二叉树层序遍历二叉树析构函数调用 求二叉树的结点个数 设计算法按前序次序打印二叉树中int Depth(BiNode<T> *root);/ 深度； ;template <class T>BiTree<T>:BiTree()Creat(root);template <class T>void BiTree<T> :Creat(BiNode<T> *&root) char ch;cin>>ch;if (ch='#') root=NULL; /else root=new

7、BiNode<T> / root->data=ch; Creat(root->lchild); / Creat(root->rchild); /建立一棵空树生成一个结点递归建立左子树递归建立右子树template <class T>void BiTree<T>:LeverOrder(BiNode<T> *root) BiNode<T> * Q100;int front = 0, rear = 0; /采用顺序队列，并假定不会发生上溢if (root=NULL) return;Q+rear=root;while (fr

8、ont!=rear)BiNode<T> * q=Q+front;cout<<q->data<<" "if (q->lchild!=NULL) Q+rear=q->lchild; if (q->rchild!=NULL) Q+rear=q->rchild;template <class T>void BiTree<T>:PostOrder(BiNode<T> *root)if (root = NULL) return; / else PostOrder(root->lc

9、hild); / PostOrder(root -> rchild);/ cout<<root->data<<" "/递归调用的结束条件后序递归遍历 root 的左子树 后序递归遍历 root 的右子树 访问根结点的数据域template <class T>void BiTree<T>:PreOrder(BiNode<T> *root)if (root =NULL) return; / else cout<<root->data<<" "/PreOrde

10、r(root->lchild); /PreOrder(root->rchild); / 递归调用的结束条件访问根结点的数据域前序递归遍历 root 的左子树前序递归遍历 root 的右子树template <class T>void BiTree<T> :Release(BiNode<T> *root)if (root!=NULL) Release(root->lchild); /释放左子树Release(root->rchild); /释放右子树delete root;template <class T>void BiT

11、ree<T>:InOrderInOrderif (root=NULL) return; / else InOrder(root->lchild); / cout<<root->data<<" " / InOrder(root->rchild); /int n = 0;template <class T>void BiTree<T>:Count(BiNode<T> *root) /n if (root)Count(root->lchild);n+; /求二叉树的结点个数Count(

12、root->rchild);(BiNode<T>root)/ 二叉 树的中序遍历 递归算 法 递归调用的结束条件中序递归遍历 root 的左子树访问根结点的数据域中序递归遍历 root 的右子树为全局量并已初始化为 0int cnt = 0;template <class T>void BiTree<T>:PreOrdercnt(BiNode<T> *root)/ 设计算法按前序次序打印 叉树中的叶子结点 ;if (root) if (!root->lchild && !root->rchild)cout<

13、<root->data <<" "cnt+;PreOrdercnt(root->lchild);PreOrdercnt(root->rchild);template <class T>int BiTree<T>:Depth(BiNode<T> *root)/ 算法求二叉树的深度if (root=NULL) return 0;else int hl= Depth(root->lchild);int hr= Depth(root ->rchild);return max(hl, hr)+1;in

14、t main()BiTree<char> mytree;cout<< " 结点总个数 : "mytree.Count();cout<<n<<endl; cout << endl;cout<< " 前序遍利 : "mytree.PreOrder();cout << endl; cout<< " 中序遍利 : "mytree.InOrder();cout << endl; cout<<" 后序遍利 : &quo

15、t; mytree.PostOrder(); cout << endl;cout<<" 层序遍利 : "mytree.LeverOrder();cout << endl; cout<<" 叶子结点为 : "mytree.PreOrdercnt(); cout<<" 个数 : "cout<<cnt<<" " cout << endl;cout<<" 二叉树的深度 : "cout <&l

16、t;mytree.Depth()<<endl;return 0;2./声明类InThrBiTree 及定义结构 ThrNode,文件名为inthrbitree.h #ifndef INTHRBITREE_H#define INTHRBITREE_Henum flag Child, Thread; /枚举类型,枚举常量 Child=0 , Thread=1二叉线索树的结点结构template <class T> struct ThrNode / T data;ThrNode<T> *lchild, *rchild; flag ltag, rtag;templa

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

18、e<T>* root; / ThrNode<T>* Creat( ); / void ThrBiTree(ThrNode<T>* root); void Release(ThrNode<T>* root); #endif/ 定义类 InThrBiTree #include<iostream> #include<string> #include"inthrbitree.h"中的成员函数，文件名为inthrbitree.cppusing namespace std;/ 构造一棵中序线索二叉树template

19、 <class T>InThrBiTree<T>:InThrBiTree( )ThrNode<T>* pre = NULL;this->root = Creat( );ThrBiTree(root);/ 释放中序线索二叉链表中各结点的存储空间 template <class T>InThrBiTree<T>:InThrBiTree(void)Release(root);/ 获取指向中序线索二叉树根结点的指针 template <class T>ThrNode<T>* InThrBiTree<T>

20、;:Getroot( )return root;/ 输出指向结点 p 的后继结点的指针 template <class T>ThrNode<T>* InThrBiTree<T>:Next(ThrNode<T>* p)ThrNode<T>* q;if (p->rtag=Thread) q = p->rchild; / 右标志为 1 ，可直接得到后继结点八、elseq = p->rchild;/while (q->ltag=Child) / q = q->lchild;return q;工作指针初始化 查找最

21、左下结点/ 中序遍历一棵线索二叉树 template <class T> void InThrBiTree<T>:InOrder(ThrNode<T> *root)ThrNode<T>* p = root;if (root=NULL) return; /while (p->ltag=Child) /p = p->lchild;cout<<p->data<<" "while (p->rchild!=NULL) /p = Next(p);cout<<p->data&

22、lt;<" "cout<<endl;/ 构造一棵二叉树 , 构造函数调用 template <class T>ThrNode<T>* InThrBiTree<T>:Creat( ) 如果线索链表为空，则空操作返回 查找中序遍历序列的第一个结点 p 并访问当结点 p 存在后继，依次访问其后继结点ThrNode<T> *root;T ch;cout<<" 请输入创建一棵二叉树的结点数据 "<<endl; cin>>ch;if (ch="#"

23、;) root = NULL;elseroot=new ThrNode<T> / root->data = ch; root->ltag = Child;root->rtag = Child; root->lchild = Creat( ); / root->rchild = Creat( ); /生成一个结点递归建立左子树 递归建立右子树return root;/ 给二叉树建立线索template <class T>void InThrBiTree<T>:ThrBiTree(ThrNode<T> *root)if (root=NULL) return;/ThrBiTree(root->lchild);if (!root->lchild) / root->ltag = Thread; root->lchild = pre; /if (!root->rchild) root-&