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

一、实验目的： 理解二叉树特别是完全二叉树的性质，掌握二叉树的存储结构（二叉链表）；熟练掌握二叉树的常用操作算法（初始化、插入结点、删除结点、遍历等）；初步掌握二叉树的应用。 二、实验内容： 要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。 具体要求如下： ①给出基于二叉链表的二叉树类的定义； ②给出二叉树初始化（构造函数）的实现； ③给出二叉树三种遍历算法的递归实现； ④二叉树先序遍历的非递归算法实现； ⑤利用二叉树的遍历算法求二叉树的结点数、二叉树的叶结点数、二叉树的高度； ⑥二叉树的撤销删除 三、实验步骤： 1、需求分析： 本演示程序用JAVA编写，完成树的生成，任意位置的插入、删除，以及遍历二叉树中的结点，查找和修改树中元素的值。 ① 输入的形式和输入值的范围：插入元素时需要输入插入的位置和元素的值；删除元素时输入删除元素的位置；遍历时采用三种遍历方法中的一种遍历方法；修改操作时需要输入的元素的值；查找操作时，需要找到要查找元素的位置。在所有输入中，元素的值都是整数。 ② 输出的形式：在所有四种操作中都显示操作是否正确以及操作后树中的内容。其中删除操作后显示删除的元素的值，遍历二叉树中的元素，查找操作、修改操作后显示修改的值。 ③ 程序所能达到的功能：完成树的生成（通过插入操作）、插入、删除、遍历、查找、修改操作。 ④ 测试数据： A． 树中已有以50,25,75,12,37,43,30,33,87,93,97为关键字的结点 B． 插入操作中依次输入10，20，30，40，50，60，70，80，90，100十个数 C． 删除操作中输入10删除值为10的元素 D． 查找操作中输入20，30，40，50返回这个元素在树中的位置 2．概要设计： 1）为了实现上述程序功能，需要定义树的抽象数据类型： public int iData; public double dData; public Node leftChild; public Node rightChild; private Node root;int value; private Node getSuccessor； 基本操作：{ Tree () 操作结果：构造一个空的二叉树 insert () 初始条件：是否存在一个空二叉树 操作结果：往二叉树中插入数值 delete () 初始条件：存在一非空的二叉树 操作条件：将二叉树中的元素删除 displayTree () 初始条件：存在一非空的树 操作条件：显示非空树中的所有元素的值 getString () 初始条件：存在一非空的二叉树 操作结果：返回整个字符串的数值 getChar () 初始条件：存在一非空的二叉树 操作结果：返回字符型的数值 getInt () 初始条件：存在一非空的二叉树 操作结果：返回整型的数值 find () 初始条件：存在一非空二叉树 操作结果：从二叉树中查找某一元素 traverse () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行遍历 preorder () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行先根遍历 inOrder () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行中根遍历 postOrder () 初始条件：存在一非空的二叉树 操作结果：对二叉树中的元素进行后根遍历 DisplayNode () 初始条件：存在一非空的二叉树 操作结果：显示出二叉树中的整形数值和双精度浮点型数值 public static void main 操作结果：调用主函数