数据结构树的操作实验报告.docx
- 文档编号:15948708
- 上传时间:2023-07-09
- 格式:DOCX
- 页数:14
- 大小:132.57KB
数据结构树的操作实验报告.docx
《数据结构树的操作实验报告.docx》由会员分享,可在线阅读,更多相关《数据结构树的操作实验报告.docx(14页珍藏版)》请在冰点文库上搜索。
数据结构树的操作实验报告
*******************
实践教学
*******************
兰州理工大学
算法与数据结构课程设计
题目:
二叉树操作
专业班级:
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)为了实现上述程序功能,需要定义树的抽象数据类型:
publicintiData;
publicdoubledData;
publicNodeleftChild;
publicNoderightChild;
privateNoderoot;intvalue;
privateNodegetSuccessor;
基本操作:
{
Tree()
操作结果:
构造一个空的二叉树
insert()
初始条件:
是否存在一个空二叉树
操作结果:
往二叉树中插入数值
delete()
初始条件:
存在一非空的二叉树
操作条件:
将二叉树中的元素删除
displayTree()
初始条件:
存在一非空的树
操作条件:
显示非空树中的所有元素的值
getString()
初始条件:
存在一非空的二叉树
操作结果:
返回整个字符串的数值
getChar()
初始条件:
存在一非空的二叉树
操作结果:
返回字符型的数值
getInt()
初始条件:
存在一非空的二叉树
操作结果:
返回整型的数值
find()
初始条件:
存在一非空二叉树
操作结果:
从二叉树中查找某一元素
traverse()
初始条件:
存在一非空的二叉树
操作结果:
对二叉树中的元素进行遍历
preorder()
初始条件:
存在一非空的二叉树
操作结果:
对二叉树中的元素进行先根遍历
inOrder()
初始条件:
存在一非空的二叉树
操作结果:
对二叉树中的元素进行中根遍历
postOrder()
初始条件:
存在一非空的二叉树
操作结果:
对二叉树中的元素进行后根遍历
DisplayNode()
初始条件:
存在一非空的二叉树
操作结果:
显示出二叉树中的整形数值和双精度浮点型数值
publicstaticvoidmain
操作结果:
调用主函数
2)本程序包含14个函数:
3.详细设计
实现概要设计中定义的所有的数据类型,对每个操作给出java算法。
对主程序和其他模块也都需要写出java算法。
1)结点类型和指针类型
publicintiData;
publicdoubledData;
publicNodeleftChild;
publicNoderightChild;
privateNoderoot;
2)树的基本操作
一、插入操作:
publicvoidinsert(intid,doubledd){
NodenewNode=newNode();//makenewnode
newNode.iData=id;//insertdata
newNode.dData=dd;
if(root==null)//nonodeinroot
root=newNode;
else//rootoccupied
{
Nodecurrent=root;//startatroot
Nodeparent;
while(true)//(exitsinternally)
{
parent=current;
if(id { current=current.leftChild; if(current==null)//ifendoftheline, {//insertonleft parent.leftChild=newNode; return; } }//endifgoleft else//orgoright? { current=current.rightChild; if(current==null)//ifendoftheline {//insertonright parent.rightChild=newNode; return; } }//endelsegoright }//endwhile }//endelsenotroot }//endinsert() 首先判断根节点是否为空,若为空,则新输入一个根节点。 若不为空,则进行比较。 如果插入的数据是整型,则将二叉树里的整型数值和当前要插入的整型数值比较,若id 此时,如果存在左孩子,那么就和上述的比较方法一样进行比较。 如果,不存在左孩子,则就将要插入的数值作为刚才比较过的父母节点的左孩子(parent.leftChild=newNode)。 然后,返回。 如果id>current.iData,则将指针指向该节点的右孩子(current=current.rightChild),再进行比较。 。 此时,如果存在右孩子,和上述比较方法一样。 如果没有右孩子,则将要插入的数值作为刚才比较过的父母节点的右孩子(parent.rightChild=newNode)。 然后,返回。 二、删除操作: publicbooleandelete(intkey)//deletenodewithgivenkey {//(assumesnon-emptylist) Nodecurrent=root; Nodeparent=root; booleanisLeftChild=true; while(current.iData! =key)//searchfornode { parent=current; if(key { isLeftChild=true; current=current.leftChild; } else//orgoright? { isLeftChild=false; current=current.rightChild; } if(current==null)//endoftheline, returnfalse;//didn'tfindit }//endwhile //foundnodetodelete //ifnochildren,simplydeleteit if(current.leftChild==null&& current.rightChild==null) { if(current==root)//ifroot, root=null;//treeisempty elseif(isLeftChild) parent.leftChild=null;//disconnect else//fromparent parent.rightChild=null; } //ifnorightchild,replacewithleftsubtree elseif(current.rightChild==null) if(current==root) root=current.leftChild; elseif(isLeftChild) parent.leftChild=current.leftChild; else parent.rightChild=current.leftChild; //ifnoleftchild,replacewithrightsubtree elseif(current.leftChild==null) if(current==root) root=current.rightChild; elseif(isLeftChild) parent.leftChild=current.rightChild; else parent.rightChild=current.rightChild; else//twochildren,soreplacewithinordersuccessor { //getsuccessorofnodetodelete(current) Nodesuccessor=getSuccessor(current); //connectparentofcurrenttosuccessorinstead if(current==root) root=successor; elseif(isLeftChild) parent.leftChild=successor; else parent.rightChild=successor; //connectsuccessortocurrent'sleftchild successor.leftChild=current.leftChild; }//endelsetwochildren //(successorcannothavealeftchild) returntrue;//success }//enddelete() 做删除时,首先,先查找树是否有左孩子和右孩子。 如果没有,则查找是否是存在根节点。 如果存在根节点,则将根节点置为空。 如果是左孩子,则将父母节点的左孩子置为空(parent.leftChild=null)。 如果是右孩子,则将右孩子置为空(parent.rightChild=null)。 三、遍历操作 publicvoidtraverse(inttraverseType) { switch(traverseType) { case1: System.out.print("\nPreordertraversal: "); preOrder(root); break; case2: System.out.print("\nInordertraversal: "); inOrder(root); break; case3: System.out.print("\nPostordertraversal: "); postOrder(root); break; } System.out.println(); } 进行遍历操作,通过switch操作选择遍历的方式: 先根遍历、中根遍历、后跟遍历。 四、查找操作 publicNodefind(intkey)//findnodewithgivenkey {//(assumesnon-emptytree) Nodecurrent=root;//startatroot while(current.iData! =key)//whilenomatch, { if(key current=current.leftChild; else//orgoright? current=current.rightChild; if(current==null)//ifnochild, returnnull;//didn'tfindit } returncurrent;//foundit }//endfind() 首先,将当前指针指向树的根节点(Nodecurrent=root)。 然后,当查找元素时,先比较要找的元素与当前找到的元素的数值大小关系,如果比当前找到的元素数值小((key 如果,找到的节点的数值比要找的元素数值大的话,则指针就接着此节点的右孩子继续寻找(current=current.rightChild)。 知道找到位置。 若整棵树为空(current==null),则显示空(returnnull)。 4.调试分析: 利用二叉树的遍历算法求二叉树的结点数、二叉树的叶结点数、二叉树的高度无法通过编译 5.测试结果: 一、插入操作: 二、删除操作: 三、遍历操作: 四、查找操作(先根遍历;中根遍历;后根遍历): 6.使用说明: 程序名为tree.exe,运行环境为DOS。 程序执行后显示: Enterfirstletterofshow,insert,find,delete,ortraverse: 选择s: 显示树中已有的结点; 选择i: 插入结点,要求输入要结点的关键字的值。 选择f: 查找结点,要求显示出指定关键字值的结点及位置。 选择d: 要求输入所要删去结点的值, 选择t: 遍历书中的结点,要求输入数字,选择遍历的方式 按1,先根遍历 按2,中根遍历 按3,后根遍历 四、实验总结(结果分析和体会): 通过这次实验,我近一步理解了二叉树特别是完全二叉树的性质,掌握了二叉树的存储结构(二叉链表);更近一步地熟练了二叉树的常用操作算法(初始化、插入结点、删除结点、遍历等);初步地掌握二叉树的应用。 总之,通过本次实验,我对树的相关知识有了进一步的加深和记忆。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 操作 实验 报告