常用的数据结构和算法(6).ppt
深入Java编程,专业教程,理论讲解部分,Ver3.1,第025课 算法及数据结构,概述：,二叉树的相关概念 二叉树的实现,重点：,难点：,二叉树的实现,二叉树的实现,6 二叉树,第025课 算法及数据结构,二叉树综合了有序数组与链表得优点.,有序数组具有较快得查找速度,链表具有非常好得插入删除效率.,树结合了两者得有点,使得它具有很高得插入 删除及查找得效率.,它得实现与其结构密切相关,下面我们来看看它的结构.,第025课 算法及数据结构,1,2,3,4,5,6,7,8,这是一棵很简单的树.,树主要是由结点及结点之间得关系组成的,下面给出一些相关得概念,6 二叉树,第025课 算法及数据结构,二叉树或者是一棵 空树，或者是一棵由一个 根结 点和两棵互不相交的分别称根的 左子树 和 右子树 所组成的 非空树，左子树和右子树又同样都是一棵二叉树.右图为一棵二叉树,6.1 树的相关概念,二叉树:,1,2,3,4,5,6,6 二叉树,第025课 算法及数据结构,路径:,顺着连接节点的边从一个节点走到另一个节点，所经过的节点的顺序排列就称为“路径”。,1,2,3,4,5,6,其中橙色得线就代表一条路径,6.1 树的相关概念,6 二叉树,第025课 算法及数据结构,根:,树得顶端称为根.每棵树只有一个根.,1,2,3,4,5,6,右图中 1 为根,父结点与子结点:,除根结点外,其余结点都有另外一个结点指向它.那么指向其它结点的结点称为父结点.被指向的结点称为子结点.,右图中3为6的父结点,6为3的子结点,6.1 树的相关概念,6 二叉树,第025课 算法及数据结构,1,2,3,4,5,6,叶结点:,没有子结点的结点称为叶结点.,图中4,5,6均为叶结点.,子树:,每一个结点都可以看作是其子孙结点的根.这样将其与其子孙结点的集合称为子树,图中2,4,5可以看作是一棵子树.,6.1 树的相关概念,6 二叉树,第025课 算法及数据结构,1,2,3,4,5,6,遍历:,根据某种规则,对树中所有的结点全部访问一次称作一次遍历.,例如:1,2,3,4,5,6 就是一次遍历.它是按照由高到低的顺序遍历的.或者称为广度优先遍历.,层:,树中从根开始计算的“辈分”.,0,1,2,6.1 树的相关概念,6 二叉树,第025课 算法及数据结构,6.2 二叉树的建立,实现二叉树首先就要实现它的结点.,它的每一个结点除了要保存相应的数据之外,还要保存其子结点的引用.,其数据需要两个域,一个保存键值,另一个保存该键值所对应的数据.,private class Nodeint key;int value;Node left;Node right;,6 二叉树,第025课 算法及数据结构,当我们拥有了结点以后,就可以着手创建我们的树了.,一颗数最特殊的结点就是它的根结点,当拥有了根结点就意味着你拥有了整棵树.,所以我们要用一个变量来保存这个非常重要的根.,private Node root;,6.2 二叉树的建立,6 二叉树,第025课 算法及数据结构,二叉树的初始化非常的简单.只需要有个根就可以了,而且树是空的.所以甚至连根的初始化都可以省略.,public MyTree()super();root=null;,这里唯一的一句root=null;都可以省略.因为对象在初始化时,其成员变量自动是空.为了清晰,还是把它加上.,6.2 二叉树的建立,6 二叉树,第025课 算法及数据结构,6.3 二叉树的插入,二叉树的插入是保证起有序性的重要环节.如果随意的插入则无法保证其有序性.,二叉树的顺序,一棵有序的二叉树叫搜索二叉树.其定义是根要大于左子树所有结点,小于右子树所有结点.其子树仍然遵循这个规律.,我们要建立的便是一棵这样的搜索二叉树.,6 二叉树,第025课 算法及数据结构,10,2,13,1,5,16,如图,该树便是一棵搜索二叉树.,下面我们要讨论如何将7插入该树.,首先我们要访问根结点,判断这个7应该放在其左子树还是右子树.,710,所以 7 应该放在左子树中.,6.3 二叉树的插入,6 二叉树,第025课 算法及数据结构,10,2,13,1,5,16,然后,对根的左子树进行检查.判断该子树是否为空,若空则将7加入.非空则继续判断在该子树中的位置.,根的左子树非空且值为2,后判断27,则7应该在该子树的右子树中.,6.3 二叉树的插入,6 二叉树,第025课 算法及数据结构,10,2,13,1,5,16,以次继续,直到判断到5后,7应该在5的右子树中,且5的右子树为空.,于是将7加入5的右子树中,7,6.3 二叉树的插入,6 二叉树,第025课 算法及数据结构,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.3 二叉树的插入,6 二叉树,第025课 算法及数据结构,此时,我们可以通过使用结点Node来建立一棵树.,并且,可以按照搜索树的要求调用插入insertNode()函数来使树成长.,下节课介绍树的删除 查询 及遍历,6 二叉树,小结：,树的相关概念 树的建立 插入结点,第025课 算法及数据结构,1、树集成了哪两种结构的优点()A)队列 B)有序数组 C)栈 D)链表2、搜索树的规则是()A)左子树右子树根 B)左子树右子树3、在树的插入中,我们使用的是非递归方法.考虑如何使用非递归方法实现,小测验（单选题）：,第025课 算法及数据结构,1、树集成了哪两种结构的优点(BD)A)队列 B)有序数组 C)栈 D)链表2、搜索树的规则是(c)A)左子树右子树根 B)左子树右子树3、在树的插入中,我们使用的是非递归方法.考虑如何使用非递归方法实现,小测验（单选题答案）：,第025课 算法及数据结构,将树的建立 插入重新实现一次.注意插入操作的操作顺序.,课后作业：,第025课 算法及数据结构,
