最新常用的数据结构和算法PPT课件.ppt

常用的数据结构和算法常用的数据结构和算法第025课 算法及数据结构概述：二叉树的相关概念 二叉树的实现重点：难点：二叉树的实现 二叉树的实现第025课 算法及数据结构123456遍历:根据某种规则,对树中所有的结点全部访问一次称作一次遍历.例如:1,2,3,4,5,6 就是一次遍历.它是按照由高到低的顺序遍历的.或者称为广度优先遍历.层:树中从根开始计算的“辈分”.0126.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课 算法及数据结构102131516如图,该树便是一棵搜索二叉树.下面我们要讨论如何将7插入该树.首先我们要访问根结点,判断这个7应该放在其左子树还是右子树.710,所以 7 应该放在左子树中.6.3 二叉树的插入6 二叉树第025课 算法及数据结构102131516然后,对根的左子树进行检查.判断该子树是否为空,若空则将7加入.非空则继续判断在该子树中的位置.根的左子树非空且值为2,后判断27,则7应该在该子树的右子树中.6.3 二叉树的插入6 二叉树第025课 算法及数据结构102131516以次继续,直到判断到5后,7应该在5的右子树中,且5的右子树为空.于是将7加入5的右子树中76.3 二叉树的插入6 二叉树第025课 算法及数据结构private void insertNode(Node subtreeRoot,Node newNode)Node current=subtreeRoot;while(true)if(newNode.key右子树根 B)左子树右子树根 C)左子树根右子树 D)左子树右子树3、在树的插入中,我们使用的是非递归方法.考虑如何使用非递归方法实现小测验（单选题）：第025课 算法及数据结构1、树集成了哪两种结构的优点(BD)A)队列 B)有序数组 C)栈 D)链表2、搜索树的规则是(c)A)左子树右子树根 B)左子树右子树根 C)左子树根右子树 D)左子树右子树3、在树的插入中,我们使用的是非递归方法.考虑如何使用非递归方法实现小测验（单选题答案）：第025课 算法及数据结构 将树的建立 插入重新实现一次.注意插入操作的操作顺序.课后作业：第025课 算法及数据结构