数据结构树的操作实验报告.doc

《数据结构树的操作实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、*******************实践教学*******************兰州理工大学算法与数据结构课程设计题目：二叉树操作专业班级：08级计算机科学与技术（5）班姓名：金文鑫学号：08240511指导教师：李睿成绩：_______________10一、实验目的：理解二叉树特别是完全二叉树的性质，掌握二叉树的存储结构（二叉链表）；熟练掌握二叉树的常用操作算法（初始化、插入结点、删除结点、遍历等）；初步掌握二叉树的应用。二、实验内容：要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后

2、序遍历的操作，求所有叶子及结点总数的操作等。具体要求如下：①给出基于二叉链表的二叉树类的定义；②给出二叉树初始化（构造函数）的实现；③给出二叉树三种遍历算法的递归实现；④二叉树先序遍历的非递归算法实现；⑤利用二叉树的遍历算法求二叉树的结点数、二叉树的叶结点数、二叉树的高度；⑥二叉树的撤销删除三、实验步骤：1、需求分析：本演示程序用JAVA编写，完成树的生成，任意位置的插入、删除，以及遍历二叉树中的结点，查找和修改树中元素的值。①输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输

3、入删除元素的位置；遍历时采用三种遍历方法中的一种遍历方法；修改操作时需要输入的元素的值；查找操作时，需要找到要查找元素的位置。在所有输入中，元素的值都是整数。②输出的形式：在所有四种操作中都显示操作是否正确以及操作后树中的内容。其中删除操作后显示删除的元素的值，遍历二叉树中的元素，查找操作、修改操作后显示修改的值。③程序所能达到的功能：完成树的生成（通过插入操作）、插入、删除、遍历、查找、修改操作。④测试数据：A．树中已有以50,25,75,12,37,43,30,33,87,93,97为关键字的结点B．

4、插入操作中依次输入10，20，30，40，50，60，70，80，90，100十个数C．删除操作中输入10删除值为10的元素D．查找操作中输入20，30，40，50返回这个元素在树中的位置2．概要设计：1）为了实现上述程序功能，需要定义树的抽象数据类型：publicintiData;publicdoubledData;10publicNodeleftChild;publicNoderightChild;privateNoderoot;intvalue;privateNodegetSuccessor；基本操

5、作：{Tree()操作结果：构造一个空的二叉树insert()初始条件：是否存在一个空二叉树操作结果：往二叉树中插入数值delete()初始条件：存在一非空的二叉树操作条件：将二叉树中的元素删除displayTree()初始条件：存在一非空的树操作条件：显示非空树中的所有元素的值getString()初始条件：存在一非空的二叉树操作结果：返回整个字符串的数值getChar()初始条件：存在一非空的二叉树操作结果：返回字符型的数值getInt()初始条件：存在一非空的二叉树操作结果：返回整型的数值find(

6、)初始条件：存在一非空二叉树操作结果：从二叉树中查找某一元素traverse()初始条件：存在一非空的二叉树操作结果：对二叉树中的元素进行遍历preorder()初始条件：存在一非空的二叉树操作结果：对二叉树中的元素进行先根遍历inOrder()初始条件：存在一非空的二叉树操作结果：对二叉树中的元素进行中根遍历postOrder()初始条件：存在一非空的二叉树操作结果：对二叉树中的元素进行后根遍历DisplayNode()初始条件：存在一非空的二叉树操作结果：显示出二叉树中的整形数值和双精度浮点型数值pu

7、blicstaticvoidmain操作结果：调用主函数10　2）本程序包含14个函数：　　main()displayNode()postorder()delete()tree()insert()preorder()getInt()displayTree()inorder()getChar()find()traverse()getString()3．详细设计　　实现概要设计中定义的所有的数据类型，对每个操作给出java算法。对主程序和其他模块也都需要写出java算法。1)结点类型和指针类型publicin

8、tiData;publicdoubledData;publicNodeleftChild;publicNoderightChild;privateNoderoot;2)树的基本操作一、插入操作：publicvoidinsert(intid,doubledd){NodenewNode=newNode();//makenewnodenewNode.iData=id;//insertdatanewNode.dData=dd;if(r