8.2动态查找表 ●动态查找表的特点:表结构本身是在查找过程中动态地生成 的,即对于给定值key,若表中存在其关键字等于key的记 录,则查找成功返回,否则插入关键字等于key的记录。 二叉树排序树及其查找过程 1、什么是二叉排序树? ●二叉排序树或是一棵空树;或是具有下列性质的二叉树: (1)若它的左子树不空,则左子树上所有结点的值均 小于它的根结点的值; ●(2)若它的右子树不空,则右子树上所有结点的值均 大于或等于它的根结点的值; (3)它的左、右子树也分别为二叉排序树。 北京邮电大学自动化学院 16
北京邮电大学自动化学院 16 8.2 动态查找表 ⚫ 动态查找表的特点：表结构本身是在查找过程中动态地生成 的，即对于给定值key，若表中存在其关键字等于key的记 录，则查找成功返回，否则插入关键字等于key的记录。 ⚫ 一、二叉树排序树及其查找过程 ⚫ 1、什么是二叉排序树？ ⚫ 二叉排序树或是一棵空树；或是具有下列性质的二叉树： ⚫ （1）若它的左子树不空，则左子树上所有结点的值均 小于它的根结点的值； ⚫ （2）若它的右子树不空，则右子树上所有结点的值均 大于或等于它的根结点的值； ⚫ （3）它的左、右子树也分别为二叉排序树
二叉树排序树及其查找过程 5 例如右图所示为二叉排序树。 3)③7 2、查找过程 若二叉排序树为空,则查找不成功;否则 。(1)若给定值等于根结点的关键字,则查找8 成功; (2)若给定值小于根结点的关键字,则继续在左子 树上进行查找; (3)若给定值大于根结点的关键字,则继续在右子树上 进行查找。 北京邮电大学自动化学院
北京邮电大学自动化学院 17 一、二叉树排序树及其查找过程 ⚫ 2、查找过程 90 78 24 100 61 3 37 12 53 45 ⚫ 例如右图所示为二叉排序树。 ⚫ 若二叉排序树为空，则查找不成功；否则 ⚫ （1）若给定值等于根结点的关键字，则查找 成功； ⚫ （2）若给定值小于根结点的关键字，则继续在左子 树上进行查找； ⚫ （3）若给定值大于根结点的关键字，则继续在右子树上 进行查找
叉树排序树及其查找过程 45 53 3 查找过程举例:100、40 北京邮电大学自动化学院
北京邮电大学自动化学院 18 查找过程举例：100、40 90 78 24 100 61 3 37 12 53 45 一、二叉树排序树及其查找过程
二叉排序树的插入与删除 1、二叉排序树的插入 二叉排序树是一种动态树表。其特点是:树的结构通常不是 次生成的,而是在查找过程中,当树中不存在关键字等于 给定值的结点时再进行插入。新插入的结点一定是一个新添 加的叶子结点,并且是查找不成功时,查找路径上访问的最 后一个结点的左孩子或右孩子结点。 ●举例:若从空树出发,经过一系列的查找插入操作之后,可 生成一棵二叉树。设查找的关键字序列为45,24,53, 45,12,24,90},则生成的二叉排序树如图所示。二叉排 序树生成:从空树出发,经过一系列的查找、插入操作之 后,可生成一棵二叉排序树。 北京邮电大学自动化学院 19
北京邮电大学自动化学院 19 二、二叉排序树的插入与删除 ⚫ 1、二叉排序树的插入 ⚫ 二叉排序树是一种动态树表。其特点是：树的结构通常不是 一次生成的，而是在查找过程中，当树中不存在关键字等于 给定值的结点时再进行插入。新插入的结点一定是一个新添 加的叶子结点，并且是查找不成功时，查找路径上访问的最 后一个结点的左孩子或右孩子结点。 ⚫ 举例：若从空树出发，经过一系列的查找插入操作之后，可 生成一棵二叉树。设查找的关键字序列为{45，24，53， 45，12，24，90}，则生成的二叉排序树如图所示。二叉排 序树生成：从空树出发，经过一系列的查找、插入操作之 后，可生成一棵二叉排序树
1、二叉排序树的插入 容易看出,中序遍历二叉树可得到 45 个关键字的有序序列。这就是 说,一个无序序列可以通过构造 24 53 棵二叉排序树而变成一个有序序 列,构造树的过程即为对无序序列(12 90 进行排序的过程。 从上面的插入过程还可以看到,每次插入的新的结点都是二叉 排序树上新的叶子结点,则在进行插入操作时,不必移动其它 记录,仅需要改动某个结点的指针,由空变为非空即可。这就 相当于在一个有序序列上插入一个记录而不需要移动其它记 录。它表明,二叉排序树既拥有类似折半查找的特性,又采用 了链表作存储结构,因此是动态查找表的一种适宜表示。 北京邮电大学自动化学院
北京邮电大学自动化学院 20 ⚫ 容易看出，中序遍历二叉树可得到 一个关键字的有序序列。这就是 说，一个无序序列可以通过构造一 棵二叉排序树而变成一个有序序 列，构造树的过程即为对无序序列 进行排序的过程。 ⚫ 从上面的插入过程还可以看到，每次插入的新的结点都是二叉 排序树上新的叶子结点，则在进行插入操作时，不必移动其它 记录，仅需要改动某个结点的指针，由空变为非空即可。这就 相当于在一个有序序列上插入一个记录而不需要移动其它记 录。它表明，二叉排序树既拥有类似折半查找的特性，又采用 了链表作存储结构，因此是动态查找表的一种适宜表示。 24 45 53 12 90 1、二叉排序树的插入