数据结构和算法的Java实现二叉树.ppt_第1页
数据结构和算法的Java实现二叉树.ppt_第2页
数据结构和算法的Java实现二叉树.ppt_第3页
数据结构和算法的Java实现二叉树.ppt_第4页
数据结构和算法的Java实现二叉树.ppt_第5页
已阅读5页,还剩39页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2006,1,Java高级程序设计 专业教程 理论讲解部分 Ver 3.1,2006,2,课程概述,二叉树的相关概念 二叉树的实现 二叉树的查询 二叉树的删除 二叉树的遍历,重点,二叉树的实现,难点,二叉树的实现,学习目标,掌握二叉树的使用,2006,3,二叉树综合了有序数组与链表得优点.,有序数组具有较快得查找速度,链表具有非常好得插入删除效率.,树结合了两者得有点,使得它具有很高得插入 删除及查找得效率.,它得实现与其结构密切相关,下面我们来看看它的结构.,6.6 二叉树,2006,4,1,2,3,4,5,6,7,8,这是一棵很简单的树.,树主要是由结点及结点之间得关系组成的,下面给出一些相关得概念,6.6 二叉树,2006,5,二叉树或者是一棵 空树 ,或者是一棵由一个 根结 点和两棵互不相交的分别称根的 左子树 和 右子树 所组成的 非空树 ,左子树和右子树又同样都是一棵二叉树. 右图为一棵二叉树,二叉树:,1,2,3,4,5,6,6.6 二叉树,2006,6,路径:,顺着连接节点的边从一个节点走到另一个节点,所经过的节点的顺序排列就称为“路径”。,1,2,3,4,5,6,其中橙色得线就代表一条路径,6.6 二叉树,2006,7,根:,树得顶端称为根.每棵树只有一个根.,1,2,3,4,5,6,右图中 1 为根,父结点与子结点:,除根结点外,其余结点都有另外一个结点指向它.那么指向其它结点的结点称为父结点.被指向的结点称为子结点.,右图中3为6的父结点,6为3的子结点,6.6 二叉树,2006,8,1,2,3,4,5,6,叶结点:,没有子结点的结点称为叶结点.,图中4,5,6均为叶结点.,子树:,每一个结点都可以看作是其子孙结点的根.这样将其与其子孙结点的集合称为子树,图中2,4,5可以看作是一棵子树.,6.6 二叉树,2006,9,1,2,3,4,5,6,遍历:,根据某种规则,对树中所有的结点全部访问一次称作一次遍历.,例如:1,2,3,4,5,6 就是一次遍历.它是按照由高到低的顺序遍历的.或者称为广度优先遍历.,层:,树中从根开始计算的 “辈分”.,0,1,2,6.6 二叉树,2006,10,实现二叉树首先就要实现它的结点.,它的每一个结点除了要保存相应的数据之外,还要保存其子结点的引用.,其数据需要两个域,一个保存键值,另一个保存该键值所对应的数据.,private class Node int key; int value; Node left; Node right; ,6.6 二叉树,2006,11,当我们拥有了结点以后,就可以着手创建我们的树了.,一颗数最特殊的结点就是它的根结点,当拥有了根结点就意味着你拥有了整棵树.,所以我们要用一个变量来保存这个非常重要的根.,private Node root;,6.6 二叉树,2006,12,二叉树的初始化非常的简单.只需要有个根就可以了,而且树是空的.所以甚至连根的初始化都可以省略.,public MyTree() super(); root = null; ,这里唯一的一句root = null;都可以省略.因为对象在初始化时,其成员变量自动是空.为了清晰,还是把它加上.,6.6 二叉树,2006,13,二叉树的插入是保证起有序性的重要环节.如果随意的插入则无法保证其有序性.,二叉树的顺序,一棵有序的二叉树叫搜索二叉树.其定义是根要大于左子树所有结点,小于右子树所有结点.其子树仍然遵循这个规律.,我们要建立的便是一棵这样的搜索二叉树.,6.6 二叉树,2006,14,10,2,13,1,5,16,如图,该树便是一棵搜索二叉树.,下面我们要讨论如何将7插入该树.,首先我们要访问根结点,判断这个7应该放在其左子树还是右子树.,710 ,所以 7 应该放在左子树中.,6.6 二叉树,2006,15,10,2,13,1,5,16,然后,对根的左子树进行检查.判断该子树是否为空,若空则将7加入.非空则继续判断在该子树中的位置.,根的左子树非空且值为2,后判断27,则7应该在该子树的右子树中.,6.6 二叉树,2006,16,10,2,13,1,5,16,依次继续,直到判断到5后,7应该在5的右子树中,且5的右子树为空.,于是将7加入5的右子树中,7,6.6 二叉树,2006,17,private void insertNode( Node subtreeRoot,Node newNode) Node current = subtreeRoot; while(true) if(newNode.keycurrent.key) if(current.left = null) current.left = newNode; return; else current = current.left; else if(current.right = null) current.right = newNode; return; else current = current.right; ,这是插入结点代码的实现,其中 subtreeRoot是要查询子树的根 newNode是要插入的结点,新结点在当前结点的左子树,新结点在当前结点的右子树,左结点空加入,左结点非空继续查询,右结点空加入,右结点非空继续查询,6.6 二叉树,2006,18,此时,我们可以通过使用结点Node来建立一棵树.,并且,可以按照搜索树的要求调用插入insertNode()函数来使树成长.,下节课介绍树的删除 查询 及遍历,6.6 二叉树,2006,19,10,2,13,1,5,16,如图,该树便是一棵搜索二叉树.,下面我们要讨论如何查询到5所在的结点.,首先我们要访问根结点,判断根结点是否是要查询的目标.,510 ,所以根结点不是查询目标且目标可能在其左子树内,6.6 二叉树,2006,20,10,2,13,1,5,16,然后,对根的左子树进行检查.判断该子树根结点是否是要查询的目标.,25,则5可能在该子树的右子树中.,6.6 二叉树,2006,21,10,2,13,1,5,16,判断,该子树的根结点是否是要查找目标.,查找成功,返回该结点.,若查找到最后为空结点,其后再没有子树则判定树中无该结点,给出失败提示,6.6 二叉树,2006,22,private Node getNode(int key) throws Exception Node result = root; while(result.key != key) if(key result.key) result = result.left; else result = result.right; if(result = null) throw new Exception(“Cant find value by “+key); return result; ,这是插入结点代码的实现,其中 subtreeRoot是要查询子树的根 newNode是要插入的结点,目标结点在当前结点的左子树,目标结点在当前结点的右子树,查询到最终子树没有目标结点,查到目标结点,6.6 二叉树,2006,23,树的结点删除的操作相对繁琐一些.,10,2,13,1,5,16,如图,设我们将删除2这个结点.,由于要删除的结点下有两棵子树而父结点只能接收一棵子树,所以有必要对其子树的结构做一些调整.,6.6 二叉树,2006,24,10,2,13,1,5,16,查询的第一步首先要掌握目标结点(被删除结点)及其父结点.,其过程与查询类似,但要注意保留其父结点的引用.,6.6 二叉树,2006,25,10,2,13,1,5,16,获得目标结点及其父结点后要判断目标结点是其父结点的左子树还是右子树.,现2是10的左子树.,然后按照如下步骤进行.,6.6 二叉树,2006,26,10,2,13,1,5,16,将目标结点的左子树添加到其父结点的左子树中.,6.6 二叉树,2006,27,10,2,13,1,5,16,将目标结点的右子树加入到其自己的左子树中,6.6 二叉树,2006,28,10,13,1,5,16,删除目标结点,6.6 二叉树,2006,29,10,13,1,5,16,整理后为,这是当目标结点为其父结点的左子树时的操作.,下面介绍,当目标结点为其父结点的右子树时的操作,6.6 二叉树,2006,30,10,2,13,1,12,16,如图,设我们将删除13这个结点.,查询等操作相同.以获得目标结点及其父结点,6.6 二叉树,2006,31,10,2,13,1,12,16,现已知目标结点与其父结点且目标结点为其父结点的右子树,6.6 二叉树,2006,32,10,2,13,1,12,16,首先将目标结点的右子树添加到其父结点的右子树中.,6.6 二叉树,2006,33,10,2,13,1,12,16,然后 将目标结点的左子树添加到其自身的右子树中.,6.6 二叉树,2006,34,10,2,1,12,16,最后 删除目标结点,6.6 二叉树,2006,35,10,2,1,12,16,整理后为,6.6 二叉树,2006,36,public void delete(int key) throws Exception Node current = root; Node parent = null; while(current.key != key) parent = current; if(key current.key)current = current.left; elsecurrent = current.right; if(current = null) throw new Exception( “delete:Cant find value by “+key); if(parent.left = current) parent.left = current.left; insertNode(parent,current.right); current = null; else parent.right = current.right; insertNode(parent,current.left); current = null; ,这是插入结点代码的实现,其中 subtreeRoot是要查询子树的根 newNode是要插入的结点,查询目标结点及其父结点,目标结点在其父结点的左子树,目标结点在其父结点的右子树,6.6 二叉树,2006,37,二叉树的遍历分为:前序遍历 中序遍历 后序遍历.,前序遍历: 按照先访问根结点,然后分别访问其左子树 右子树.其子树的访 问顺序仍然按照该规则进行.,中序遍历: 按照先访问左子树,然后分别访问根结点.最后访问其右子树.其 子树的访问顺序仍然按照该规则进行.,后序遍历: 按照先分别访问其左子树 右子树,最后访问其根结点.其子树的 访问顺序仍然按照该规则进行.,6.6 二叉树,2006,38,这里主要介绍一下前序遍历的递归方法.其余遍历类似.,public void preOrder(Node subtreeRoot) if(subtreeRoot != null) System.out.print(“ “+subtreeRoot+“ “); preOrder(subtreeRoot.left); preOrder(subtreeRoot.right); ,6.6 二叉树,2006,39,这里主要介绍一下前序遍历的递归方法.其余遍历类似.,public void preOrder(Node subtreeRoot) if(subtreeRoot != null) System.out.print(“ “+subtreeRoot+“ “); preOrder(subtreeRoot.left); preOrder(subtreeRoot.right); ,将访问结点输出,访问其左子树,访问其右子树,关于二叉树其完整代码参见MyTrea.java,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论