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

*实践教学* 兰州理工大学算法与数据结构课程设计题 目： 二叉树操作 专业班级： 08级计算机科学与技术（5）班 姓 名： 金文鑫 学 号： 08240511 指导教师： 李睿 成 绩： _一、实验目的：理解二叉树特别是完全二叉树的性质，掌握二叉树的存储结构（二叉链表）；熟练掌握二叉树的常用操作算法（初始化、插入结点、删除结点、遍历等）；初步掌握二叉树的应用。二、实验内容：要求采用二叉链表作为存储结构，完成二叉树的建立，前序、中序和后序遍历的操作，求所有叶子及结点总数的操作等。具体要求如下：给出基于二叉链表的二叉树类的定义；给出二叉树初始化（构造函数）的实现；给出二叉树三种遍历算法的递归实现；二叉树先序遍历的非递归算法实现；利用二叉树的遍历算法求二叉树的结点数、二叉树的叶结点数、二叉树的高度；二叉树的撤销删除三、实验步骤：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操作结果：调用主函数2）本程序包含14个函数：main()displayNode()postorder()delete()tree()insert()preorder()getInt()displayTree()inorder()getChar()find()traverse()getString()3详细设计实现概要设计中定义的所有的数据类型，对每个操作给出java算法。对主程序和其他模块也都需要写出java算法。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 node in root root = newNode; else / root occupied Node current = root; / start at root Node parent; while(true) / (exits internally) parent = current; if(id current.iData) / go left? current = current.leftChild; if(current = null) / if end of the line, / insert on left parent.leftChild = newNode; return; / end if go left else / or go right? current = current.rightChild; if(current = null) / if end of the line / insert on right parent.rightChild = newNode; return; / end else go right / end while / end else not root / end insert()首先判断根节点是否为空，若为空，则新输入一个根节点。若不为空，则进行比较。如果插入的数据是整型，则将二叉树里的整型数值和当前要插入的整型数值比较，若idcurrent.iData，则将指针指向该节点的右孩子(current= current.rightChild)，再进行比较。此时，如果存在右孩子，和上述比较方法一样。如果没有右孩子，则将要插入的数值作为刚才比较过的父母节点的右孩子(parent.rightChild = newNode)。然后，返回。二、删除操作：public boolean delete(int key) / delete node with given key / (assumes non-empty list) Node current = root; Node parent = root; boolean isLeftChild = true; while(current.iData != key) / search for node parent = current; if(key current.iData) / go left? isLeftChild = true; current = current.leftChild; else / or go right? isLeftChild = false; current = current.rightChild; if(current = null) / end of the line, return false; / didnt find it / end while / found node to delete / if no children, simply delete it if(current.leftChild=null & current.rightChild=null) if(current = root) / if root, root = null; / tree is empty else if(isLeftChild) parent.leftChild = null; / disconnect else / from parent parent.rightChild = null; / if no right child, replace with left subtree else if(current.rightChild=null) if(current = root) root = current.leftChild; else if(isLeftChild) parent.leftChild = current.leftChild; else parent.rightChild = current.leftChild; / if no left child, replace with right subtree else if(current.leftChild=null) if(current = root) root = current.rightChild; else if(isLeftChild) parent.leftChild = current.rightChild; else parent.rightChild = current.rightChild; else / two children, so replace with inorder successor / get successor of node to delete (current) Node successor = getSuccessor(current); / connect parent of current to successor instead if(current = root) root = successor; else if(isLeftChild) parent.leftChild = successor; else parent.rightChild = successor; / connect successor to currents left child successor.leftChild = current.leftChild; / end else two children / (successor cannot have a left child) return true; / success / end delete()做删除时，首先，先查找树是否有左孩子和右孩子。如果没有，则查找是否是存在根节点。如果存在根节点，则将根节点置为空。如果是左孩子，则将父母节点的左孩子置为空 (parent.leftChild = null)。如果是右孩子，则将右孩子置为空(parent.rightChild = null)。三、遍历操作public void traverse(int traverseType) switch(traverseType) case 1: System.out.print(nPreorder traversal: ); preOrder(root); break; case 2: System.out.print(nInorder traversal: ); inOrder(root); break; case 3: System.out.print(nPostorder traversal: ); postOrder(root); break; System.out.println(); 进行遍历操作，通过switch 操作选择遍历的方式：先根遍历、中根遍历、后跟遍历。四、查找操作public Node find(int key) / find node with given key / (assumes non-empty tree) Node current = root; / start at root while(current.iData != key) / while no match, if(key current.iData) / go left? current = current.leftChild; else / or go right? current = current.rightChild; if(current = null) / if no child, return null; / didnt find it return current; / found it / end find()首先，将当前指针指向树的根节点(Node current = root)。然后，当查找元素时，先比较要找的元素与当前找到的元素的数值大小关系，如果比当前找到的元素数值小(key current.iData)，则指针就接着找此节点的左孩子节点继续寻找(current = c