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

《数据结构树和二叉树代码.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

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

3、设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数）四、程序样例#include#includeusingnamespacestd;templatestructBiNode{Tdata;BiNode*lchild,*rchild;};intmax(inta,intb){returna>b?a:b;}templateclassBiTree{public:BiTree();//构造函数，初始化

4、一棵空的二叉树~BiTree()//二叉树的析构函数算法BiTree{Release(root);}voidInOrder(){InOrder(root);}//中序遍历二叉树voidPreOrder(){PreOrder(root);}voidPostOrder(){PostOrder(root);}//后序遍历二叉树voidLeverOrder(){LeverOrder(root);}//层序遍历二叉树voidCount(){Count(root);}voidPreOrdercnt(){PreOrder

5、cnt(root);}intDepth(){intwww=Depth(root);returnwww;}private:BiNode*root;//指向根结点的头指针voidCreat(BiNode*&root);voidPreOrder(BiNode*root);//前序遍历二叉树voidInOrder(BiNode*root);voidPostOrder(BiNode*root);voidLeverOrder(BiNode*root);//层序遍历二叉树voidRel

6、ease(BiNode*root);//析构函数调用voidCount(BiNode*root);/////求二叉树的结点个数voidPreOrdercnt(BiNode*root);///设计算法按前序次序打印二叉树中的叶子结点;intDepth(BiNode*root);//深度；};templateBiTree::BiTree(){Creat(root);}templatevoidBiTree::Creat(BiNode*&ro

7、ot){charch;cin>>ch;if(ch=='#')root=NULL;//建立一棵空树else{root=newBiNode;//生成一个结点root->data=ch;Creat(root->lchild);//递归建立左子树Creat(root->rchild);//递归建立右子树}}templatevoidBiTree::LeverOrder(BiNode*root){BiNode*Q[100];intfront=0,rear=0;//采用顺序队列，并

8、假定不会发生上溢if(root==NULL)return;Q[++rear]=root;while(front!=rear){BiNode*q=Q[++front];cout<data<<"";if(q->lchild!=NULL)Q[++rear]=q->lchild;if(q->rchild!=NULL)Q[++rear]=q->rchild;}}templatevoidBiTr