数据结构 例:查38 索表 224886 1713 3456 89101112131415161718 2212138920334244382448605874578653 找到
数据结构 tjm 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 22 12 13 8 9 20 33 42 44 38 24 48 60 58 74 57 86 53 22 48 86 1 7 13 例：查38 索引表 找到
数据结构 查找方法比较 顺序查找折半查找分块查找 ASL 最大 最小两者之间 表结构有序表、无序表有序表 分块有序表 存储结构顺序存储结构顺序存储结构顺序存储结构 线性链表 线性链表
数据结构 tjm ASL 最大 最小 两者之间 表结构 有序表、无序表 有序表 分块有序表 存储结构 顺序存储结构 线性链表 顺序存储结构 顺序存储结构 线性链表 查找方法比较 顺序查找 折半查找 分块查找
数据结构 9.2动态查找表 特点:表结构本身在查找中动态生成。 二叉排序时和平衡二叉树 1、二叉排序树(或二叉查找树) (1)二又排序树定义 又排序树( Binary Sort Tree)或者是一棵 空树;或者是具有下列性质的二叉树 1)若左子树不空,则左子树上所有结点的值均 小于根结点的值;若右子树不空,则右子树上所有 结点的值均大于等于根结点的值。 2)左右子树也都是二叉排序树
数据结构 tjm 9.2 动态查找表 特点：表结构本身在查找中动态生成。 一、二叉排序树和平衡二叉树 1、二叉排序树（或二叉查找树） （1）二叉排序树定义 二叉排序树（Binary Sort Tree）或者是一棵 空树；或者是具有下列性质的二叉树： 1)若左子树不空，则左子树上所有结点的值均 小于根结点的值；若右子树不空，则右子树上所有 结点的值均大于等于根结点的值。 2)左右子树也都是二叉排序树
数据结构 63 55 90 42(8(70(98二叉排序数示例 10)(45)67(83 (2)二叉排序树查找过程: 二叉排序树的查找思想:若二叉排树为空,则查找 失败,否则,先拿根结点值与待查值进行比较,若 相等,则查找成功,若根结点值大于待查值,则进 入左子树重复此步骤,否则,进入右子树重复此步 骤,若在查找过程中遇到二叉排序树的叶子结点时 还没有找到待找结点,则查找不成功
数据结构 tjm （2）二叉排序树查找过程： 二叉排序树的查找思想：若二叉排树为空，则查找 失败，否则，先拿根结点值与待查值进行比较，若 相等，则查找成功，若根结点值大于待查值，则进 入左子树重复此步骤，否则，进入右子树重复此步 骤，若在查找过程中遇到二叉排序树的叶子结点时， 还没有找到待找结点，则查找不成功。 42 58 70 98 90 63 45 55 10 67 83 二叉排序数示例
数据结构 (3)二叉排序树插入操作和构造 例:{10,18,3,8,12,2,7,3} 10 3a83a8 82 38 08 (2(82((812 (2(812 二叉排序树生成:从空树出发,经过一系列的 查找、插入操作之后,可生成一棵二叉排序树。 特点:中序遍历可得一有序序列
数据结构 tjm （3）二叉排序树插入操作和构造 例： {10， 18， 3， 8， 12， 2， 7， 3} 10 10 18 10 3 18 10 3 18 8 10 3 18 8 12 10 3 18 2 8 12 10 3 18 2 8 12 7 10 3 18 2 8 12 7 3 二叉排序树生成：从空树出发，经过一系列的 查找、插入操作之后，可生成一棵二叉排序树。 特点：中序遍历可得一有序序列