数据结构-二叉树实验报告

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

1、实验5实现二叉树班级试验142学号1408160206姓名龙耀威一、问题描述实现二叉树的的基本操作。二、需求分析1、简述程序的棊木功能BinaryTree();二义树的构造函数，主要作用是在建立二义树类的对象吋，建立一个根结点的对象的指针并指向根结点。~BinaryTree();二叉树的析构两数，主耍作用是在程序运行结束或删除对象时删除指针，销毁二义树，禅放内存空间。voidPreOrder(BinTreeNodesubTree,void(visit)(Tt));二叉树的成员函数，主要实现二叉树的前序遍历操作。算法规则：

2、若二叉树为空，则空操作；否则(1)访问根结点；(2)前序遍历左子树；(3)前序遍历右子树。voidInOrder(BinTreeNodesubTree,void(visit)(Tt));二叉树的成员函数，主要实现二叉树的屮序遍历操作。算法规则：若二叉树为空，则空操作；否则(1)中序遍历左子树；(2)访问根结点；(3)屮序遍历右子树。voidPostOrder(BinTreeNodesubTree,void(visit)(Tt));二叉树的成员函数，主要实现二叉树的后序遍历操作。算法规则：若二叉树为空，则空操作；否则

3、(1)后序遍历左子树；(2)示序遍历右了树。(3)访问根结点；voidLevelOrder(void(visit)(Tt));二叉树的成员函数，主要实现二叉树的层次序遍历操作，将利用队列的有关操作。boolCreateBinaryTree(BinTreeNode&r,char&sir);二叉树的成员函数，主耍实现创建二叉树。函数的形参是一个二叉树结点类的指针的引用和一个指向字符型数据的指针的引用。intNodcNumbcr(BinTrccNodcsubTrcc);二叉树的成员函数，主要实现计算二叉树的结点数。主要将

4、利用二义树的前序遍历算法，计算二叉树中的结点数。intDepthNumber(BinTreeNodesubTree);二叉树的成员函数，主要实现计算二叉树的深度。主要利用二叉树的前序遍历算法,计算二叉树的深度。voidFindWidth(BinTreeNodesubTree,intcount,inti=0);二义树的成员函数，主要实现计算二义树的宽度。将利用一个整形数组，通过计算每层二叉树的宽度，进行比较，得出其中的最大数值即二叉树的宽度。voidDestroy(BinTreeNodesubTree);二义树

5、的成员两数，主耍实现删除二叉树。将二叉树的每个结点的数据指针都删除,将利用二叉树的前序遍历算法。boolvalid(charsh)；此函数可以进行字符有效值的判定，在根据广义表建立二叉树需要调用此函数。函数主要通过判断字符的ASCII码的值进行有效值的判断。voidvisit(Tt)；此函数的功能是向屏幕输出赋值给函数形参的值，在运行二叉树的遍丿力函数时调用函数。2、输入的形式和输入值的范围程序将提供给用户一个WIN32控制台应用程序(如图所示)，用户输入用广义表表示的二叉树，程序会自动根据广义表的表示创建一个二叉树，进行有关

6、的操作演示。C:WINDOWSsystem32cmd.exeI>I>j>I>I>I>I>I>gj>I>j>I>I>I>I>I>gj>

7、要求用户按广义二义树的标准输入一个字符串，以冋车键作为输入结束的标志。三、概要设计1、抽象数据类型(如templateclassTLlinearList)〃树的结点tcmplatcclassBinTreeNodepublic:friendclassBinaryTree;BinTreeNode();〃构造函数〃带有参数的构造函数BinTreeNode(Tt,BinTreeNode1二NULL,BinTreeNoder=NULL);private:BinTreeNodeleftChild,r

8、ightChild;〃左子女、右子女链域Tdata;//数据域}；templateclassBinaryTree〃二叉树的类{public:BinaryTree();〃构造函数~BinaryTree();〃析构函数〃遍历函数〃二叉树的前序遍历voidPrcOr