数据结构 树和二叉树代码.doc
树和二叉树一、实验目的：参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。二、实验要求：1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。三、实验内容： 1设计实现二叉树类，要求：（1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。（2）实现二叉树层次遍历的非递归算法。 （3） 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。（4）编写求二叉树高度的函数 （5）编写一主函数来验证算法实现。2. 设计实现二叉线索链表类，要求：（1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。（2）编写一主函数来验证算法实现。*3. 编写创建哈夫曼树和生成哈夫曼编码的算法。*4假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。*5假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数）四、程序样例#include<iostream>#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: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<T> *root; /指向根结点的头指针void Creat(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);/设计算法按前序次序打印二叉树中的叶子结点;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 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 (front!=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->lchild); /后序递归遍历root的左子树PostOrder(root -> rchild);/后序递归遍历root的右子树cout<<root->data<<" "/访问根结点的数据域template <class T>void BiTree<T>:PreOrder(BiNode<T> *root) if (root =NULL) return; /递归调用的结束条件else cout<<root->data<<" " /访问根结点的数据域 PreOrder(root->lchild); /前序递归遍历root的左子树PreOrder(root->rchild); /前序递归遍历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 BiTree<T>:InOrder (BiNode<T> *root)/二叉树的中序遍历递归算法InOrderif (root=NULL) return; /递归调用的结束条件else InOrder(root->lchild); /中序递归遍历root的左子树cout<<root->data<<" " /访问根结点的数据域InOrder(root->rchild); /中序递归遍历root的右子树int n = 0;template <class T>void BiTree<T>:Count(BiNode<T> *root) /n为全局量并已初始化为0 if (root) Count(root->lchild); n+; /求二叉树的结点个数 Count(root->rchild); int cnt = 0;template <class T>void BiTree<T>:PreOrdercnt(BiNode<T> *root)/设计算法按前序次序打印二叉树中的叶子结点; if (root) if (!root->lchild && !root->rchild) cout<<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; int main() BiTree<char> mytree; cout<< "结点总个数: " mytree.Count();cout<<n<<endl; 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<<" 个数: " cout<<cnt<<" " 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 <class T> struct ThrNode /二叉线索树的结点结构 T data; ThrNode<T> *lchild, *rchild; flag ltag, rtag;template <class T>class InThrBiTreepublic: InThrBiTree( ); /构造函数，建立中序线索链表 InThrBiTree( ); /析构函数，释放线索链表中各结点的存储空间ThrNode<T>* Getroot( ); /获取根结点 ThrNode<T>* Next(ThrNode<T>* p); /查找结点p的后继 void InOrder(ThrNode<T>* root); /中序遍历线索链表private: ThrNode<T>* root; /指向线索链表的头指针 ThrNode<T>* Creat( ); /构造函数调用 void ThrBiTree(ThrNode<T>* root); /构造函数调用 void Release(ThrNode<T>* root); /析构函数调用;#endif/定义类InThrBiTree中的成员函数，文件名为inthrbitree.cpp#include<iostream>#include<string>#include"inthrbitree.h"using namespace std;/构造一棵中序线索二叉树template <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>: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，可直接得到后继结点 else q = p->rchild; /工作指针初始化 while (q->ltag=Child) /查找最左下结点 q = q->lchild; return q;/中序遍历一棵线索二叉树template <class T>void InThrBiTree<T>:InOrder(ThrNode<T> *root) ThrNode<T>* p = root; if (root=NULL) return; /如果线索链表为空，则空操作返回 while (p->ltag=Child) /查找中序遍历序列的第一个结点p并访问 p = p->lchild; cout<<p->data<<" " while (p->rchild!=NULL) /当结点p存在后继，依次访问其后继结点 p = Next(p); cout<<p->data<<" " cout<<endl;/构造一棵二叉树,构造函数调用template <class T>ThrNode<T>* InThrBiTree<T>:Creat( )ThrNode<T> *root;T ch;cout<<"请输入创建一棵二叉树的结点数据"<<endl;cin>>ch; if (ch="#") root = NULL; else root=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的左指针进行处理 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);/释放中序线索二叉树的存储空间，析构函数调用template<class T>void InThrBiTree<T>:Release(ThrNode<T>* root) if (root!=NULL) Release(root->lchild); /释放左子树 Release(root->rchild); /释放右子树 delete root; /线索二叉树的主函数，文件名为inthrbitreemain.cpp#include<iostream>#include<string>#include"inthrbitree.cpp"using namespace std;ThrNode<string>* pre; void main() InThrBiTree<string> inbt;/构造一棵线索二叉树ThrNode<string>* p = inbt.Getroot( ); /获取指向根结点的指针 cout<<"-中序遍历线索二叉树-"<<endl;inbt.InOrder(p);注意问题 1注意理解有关树的各种递归算法的执行步骤。2注意字符类型数据在输入时的处理。3重点理解如何利用栈结构实现非递归算法。
