《049050数据结构和算法的Java实现二叉树》由会员分享，可在线阅读，更多相关《049050数据结构和算法的Java实现二叉树（44页珍藏版）》请在金锄头文库上搜索。
1、Java高级程序设计专业教程理论讲解部分VerVer 3.1 3.120061 1第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现课程概述二叉树的相关概念 二叉树的实现 二叉树的查询 二叉树的删除 二叉树的遍历重点二叉树的实现难点二叉树的实现学习目标掌握二叉树的使用20062 2第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现二叉树综合了有序数组与链表得优点.有序数组具有较快得查找速度,链表具有非常好得插入删除效率.树结合了两者得有点,使得它具有很高得插入 删除及查找得效率.它得实现与其结构密切相关,下面我们来看看它的结构.6.6 二叉树2006
2、3 3第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现12345678这是一棵很简单的树.树主要是由结点及结点之间得关系组 成的下面给出一些相关得概念6.6 二叉树20064 4第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现二叉树或者是一棵 空树 ，或者 是一棵由一个 根结 点和两棵互 不相交的分别称根的 左子树 和 右子树 所组成的 非空树 ，左子 树和右子树又同样都是一棵二叉 树. 右图为一棵二叉树二叉树:1234566.6 二叉树20065 5第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现路径:顺着连接节点的边从
3、一个节 点走到另一个节点，所经过 的节点的顺序排列就称为“ 路径”。123456其中橙色得线就代表一条路径6.6 二叉树20066 6第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现根:树得顶端称为根.每棵树只有 一个根.123456右图中 1 为根父结点与子结点:除根结点外,其余结点都有另外一个 结点指向它.那么指向其它结点的结 点称为父结点.被指向的结点称为子 结点.右图中3为6的父结点,6为3的子结点6.6 二叉树20067 7第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现123456叶结点: 没有子结点的结点称为叶结点.图中4,5,6均
4、为叶结点.子树: 每一个结点都可以看作是其子 孙结点的根.这样将其与其子孙 结点的集合称为子树图中2,4,5可以看作是一棵子树.6.6 二叉树20068 8第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现123456遍历:根据某种规则,对树中所有的结点 全部访问一次称作一次遍历.例如:1,2,3,4,5,6 就是一次遍历.它是 按照由高到低的顺序遍历的.或者称为 广度优先遍历.层:树中从根开始计算的 “辈分”.0126.6 二叉树20069 9第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现实现二叉树首先就要实现它的 结点.它的每一个结点除了要保
5、存相 应的数据之外,还要保存其子 结点的引用.其数据需要两个域,一个保存键 值,另一个保存该键值所对应的 数据.private class Node int key; int value; Node left; Node right; 6.6 二叉树20061010第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现当我们拥有了结点以后,就可以着手创建我们的树了.一颗数最特殊的结点就是它的根结点,当拥有了根结点就意味着你拥有 了整棵树.所以我们要用一个变量来保存这个非常重要的根.private Node root;6.6 二叉树20061111第第6 6章章 数据结构和算法
6、的数据结构和算法的JavaJava实现实现二叉树的初始化非常的简单.只需要有个根就可以了,而且树是空的.所以 甚至连根的初始化都可以省略.public MyTree() super(); root = null; 这里唯一的一句root = null;都可 以省略.因为对象在初始化时,其 成员变量自动是空.为了清晰,还 是把它加上.6.6 二叉树20061212第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现二叉树的插入是保证起有序性的重要环节.如果随意的插入则无法保证其 有序性.二叉树的顺序一棵有序的二叉树叫搜索二叉树.其定义是根要大于左子树所有结点,小于右 子树所有
7、结点.其子树仍然遵循这个规律.我们要建立的便是一棵这样的搜索二叉树.6.6 二叉树20061313第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6如图,该树便是一棵搜索二叉树.下面我们要讨论如何将7插入该树.首先我们要访问根结点,判断这个7应 该放在其左子树还是右子树.710 ,所以 7 应该放在左子树中.6.6 二叉树20061414第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6然后,对根的左子树进行检查.判断 该子树是否为空,若空则将7加入.非 空则继续判断在该子树中的位置.根的左子树非空且值
8、为2,后判断 27,则7应该在该子树的右子树中.6.6 二叉树20061515第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6依次继续,直到判断到5后,7应该在5 的右子树中,且5的右子树为空.于是将7加入5的右子树中76.6 二叉树20061616第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现private void insertNode( Node subtreeRoot,Node newNode)Node current = subtreeRoot;while(true)if(newNode.keycurrent.
9、key)if(current.left = null)current.left = newNode;return;elsecurrent = current.left;elseif(current.right = null)current.right = newNode;return;elsecurrent = current.right; 这是插入结点代 码的实现其中 subtreeRoot是 要查询子树的根newNode是要 插入的结点新结点在当前 结点的左子树新结点在当前 结点的右子树左结点 空加入左结点 非空继 续查询右结点 空加入右结点 非空继 续查询6.6 二叉树20061717第
10、第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现此时,我们可以通过使用结点Node来建立一棵树.并且,可以按照搜索树的要求调用插入insertNode()函数来使树成长.下节课介绍树的删除 查询 及遍历6.6 二叉树20061818第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6如图,该树便是一棵搜索二叉树.下面我们要讨论如何查询到5所在的结点.首先我们要访问根结点,判断根结点是 否是要查询的目标.510 ,所以根结点不是查询目标且目标 可能在其左子树内6.6 二叉树20061919第第6 6章章 数据结构和算法的数据结构和
11、算法的JavaJava实现实现1 021 3151 6然后,对根的左子树进行检查.判断 该子树根结点是否是要查询的目标.25,则5可能在该子树的右子树中.6.6 二叉树20062020第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6判断,该子树的根结点是否是要查找 目标.查找成功,返回该结点.若查找到最后为空结点,其后再没有子 树则判定树中无该结点,给出失败提示 .6.6 二叉树20062121第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现private Node getNode(int key) throws Exce
12、ptionNode 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
13、 二叉树20062222第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现树的结点删除的操作相对繁琐一些.1 021 3151 6如图,设我们将删除2这个结点.由于要删除的结点下有两棵子树 而父结点只能接收一棵子树,所以 有必要对其子树的结构做一些调 整.6.6 二叉树20062323第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6查询的第一步首先要掌握目标结点(被删除 结点)及其父结点.其过程与查询类似,但要注意保留其父结 点的引用.6.6 二叉树20062424第第6 6章章 数据结构和算法的数据结构和算法的JavaJa
14、va实现实现1 021 3151 6获得目标结点及其父结点后要判断目标结 点是其父结点的左子树还是右子树.现2是10的左子树.然后按照如下步骤进行.6.6 二叉树20062525第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6将目标结点的左子树添加到其父结点的左 子树中.6.6 二叉树20062626第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 3151 6将目标结点的右子树加入到其自己的左子 树中6.6 二叉树20062727第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 01
15、3151 6删除目标结点6.6 二叉树20062828第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 01 3151 6整理后为这是当目标结点为其父结点的左子树时的 操作.下面介绍,当目标结点为其父结点的右子树 时的操作6.6 二叉树20062929第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 311 21 6如图,设我们将删除13这个结点.查询等操作相同.以获得目标结 点及其父结点6.6 二叉树20063030第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 311 21 6现已知目标结点与其
16、父结点且目标结点为 其父结点的右子树6.6 二叉树20063131第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 311 21 6首先将目标结点的右子树添加到其父结点 的右子树中.6.6 二叉树20063232第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 021 311 21 6然后 将目标结点的左子树添加到其自身的 右子树中.6.6 二叉树20063333第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 0211 21 6最后 删除目标结点6.6 二叉树20063434第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现1 0211 21 6整理后为6.6 二叉树20063535第第6 6章章 数据结构和算法的数据结构和算法的JavaJava实现实现public void delete(int key) th
