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

******************* 实践教学 ******************* 兰州理工大学 算法与数据结构课程设计 题 目： 二叉树操作 专业班级： 08级计算机科学与技术（5）班 姓 名： 金文鑫 学 号： 指导教师： 李睿 成 绩： _______________ 一、实验目的： 理解二叉树特别是完全二叉树的性质，掌握二叉树的存储结构（二叉链表）；熟练掌握二叉树的常用操作算法（初始化、插入结点、删除结点、遍历等）；初步掌握二叉树的应用。 二、实验内容： 要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。 具体要求如下： ①给出基于二叉链表的二叉树类的定义； ②给出二叉树初始化（构造函数）的实现； ③给出二叉树三种遍历算法的递归实现； ④二叉树先序遍历的非递归算法实现； ⑤利用二叉树的遍历算法求二叉树的结点数、二叉树的叶结点数、二叉树的高度； ⑥二叉树的撤销删除 三、实验步骤： 1、需求分析： 本演示程序用JAVA编写，完成的生成，任意位置的插入、删除，以及 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；在所有输入中，元素的值都是整数 输出的形式：在所有种操作中都显示操作是否正确以及操作后的内容。其中删除操作后显示删除的元素的值， 程序所能达到的功能：完成的生成（通过插入操作）、插入、删除、操作 测试数据：A．50,25,75,12,37,43,30,33,87,93,97为关键字的结点 B． 插入操作中依次输入． 删除操作中输入删除的元素． 查找操作中输入返回这个元素在中的位置1）为了实现上述程序功能，需要定义的抽象数据类型：public int iData;public double dData; public Node leftChild; public Node rightChild; private Node root;int value; private Node getSuccessor； 基本操作：Tree ()操作结果：构造一个空的nsert () 初始条件：是否存在一个空二叉树 操作结果：往二叉树中插入数值 delete () 初始条件：存在一非空的二叉树 操作条件：将二叉树中的元素删除 displayTree () 初始条件：存在一非空的树 操作条件：显示非空树中的所有元素的值 getString () 初始条件：存在一非空的二叉树 操作结果：返回整个字符串的数值 getChar () 初始条件：存在一非空的二叉树 操作结果：返回字符型的数值 getInt () 初始条件：存在一非空的二叉树 操作结果：返回整型的数值 find () 初始条件：存在一非空二叉树 操作结果：从二叉树中查找某一元素 traverse () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行遍历 preorder () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行先根遍历 inOrder () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行中根遍历 postOrder () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行后根遍历 DisplayNode () 初始条件：存在一非空的二叉树 操作结果：显示出二叉树中的整形数值和双精度浮点型数值 public static void main 操作结果：调用主函数 　 2）本程序包含个：　　 3．详细设计 　　实现概要设计中定义的所有的数据类型，对每个操作给出算法。对主程序和其他模块也都需要写出算法。1) 结点类型和指针类型public int iData; public double dData; public Node leftChild; public Node rightChild; private Node root; 2)树的基本操作public void insert(int id, double dd) { Node newNode = new Node(); // make new node newNode.iData = id; // insert data newNode.dData = dd; if(root==null) // no