树和二叉树 一、实验目的： 参照给定的二叉树类的程序样例，验证给出的有关二叉树的常见算法，并实现有关的操作。 二、实验要求： 1、掌握二叉树、哈夫曼树和树的特点。掌握它们的常见算法。 2、提交实验报告，报告内容包括：目的、要求、算法描述、程序结构、主要变量说明、程序清单、调试情况、设计技巧、心得体会。 三、实验内容： 1．设计实现二叉树类，要求： （1）编写一个程序，首先建立不带头结点的二叉链式存储结构的二叉树，然后分别输出按照前序遍历二叉树、中序遍历二叉树和后序遍历二叉树访问各结点的序列信息，最后再测试查找函数和撤销函数的正确性。 （2）实现二叉树层次遍历的非递归算法。 （3） 假设二叉树采用链式存储结构进行存储，编写一个算法，输出一个二叉树的所有叶子结点，并统计叶子结点个数。 （4）编写求二叉树高度的函数 （5）编写一主函数来验证算法实现。 2. 设计实现二叉线索链表类，要求： （1）编写一个程序，首先建立中序线索链表的二叉树，然后实现中序线索链表的遍历算法。 （2）编写一主函数来验证算法实现。 *3. 编写创建哈夫曼树和生成哈夫曼编码的算法。 *4．假设二叉树采用链式存储结构进行存储，试设计一个算法，输出从每个叶子结点到根结点的路径。 *5．假设二叉树采用链式存储结构进行存储，试设计一个算法，求二叉树的宽度（即具有结点数最多的层次上结点总数） 四、程序样例 #include #include using namespace std; template 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 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 I...
