9.3二叉排序树 1、蚌度瘫≯索方法中二分检索法具有最 高的查燚率树笆只题j顺孕酪结章越 缚臻朝的a]带界矩其定义为:二叉 排序树或者是空树,或者是满定如下性质的二叉树 ①若它的左子树非空,则左子树上所有结点的值均 小于根结点的值 ②若它的右子树非空,则右子树上所有结点的值均 大于根结点的值 ③左、右子树本身又各是棵二叉排序树。 上述性质简称二叉排序树性质(BST性质),故 二叉排序树实际上是满足BST性质的二叉树
9.3 二叉排序树 在线性表的三种检索方法中二分检索法具有最 高的查找效率，但是它只适合于顺序存储结构，这 给查找表中数据的增、删带来不便。 1、二叉排序树的定义 二叉排序树(Binary Sort Tree)又称二叉查找 (搜索)树(Binary Search Tree)。其定义为：二叉 排序树或者是空树，或者是满足如下性质的二叉树 ： ①若它的左子树非空，则左子树上所有结点的值均 小于根结点的值； ②若它的右子树非空，则右子树上所有结点的值均 大于根结点的值； ③左、右子树本身又各是一棵二叉排序树。 上述性质简称二叉排序树性质(BST性质)，故 二叉排序树实际上是满足BST性质的二叉树
2、二叉排序树的特点 由BST性质可得 (1)二叉排序树中任结点x,其左(右)子树中 任结点y(若存在)的关键字必小(大)于×的关键字。 (2)二叉排序树中,各结点关键字是惟一的。 注意 实际应用中,不能保证被查找的数据集中各元素 的关键字互不相同,所以可将二叉排序树定义中BST 性质(1)里的"小于"改为"大于等于",或将BST性质 (2)里的大于"改为"小于等于",甚至可同时修改这两 个性质。 (3)按中序遍历该树所得到的中序序列是一个 递增有序序列
2、二叉排序树的特点 由BST性质可得： （1） 二叉排序树中任一结点x，其左(右)子树中 任一结点y(若存在)的关键字必小(大)于x的关键字。 （2） 二叉排序树中，各结点关键字是惟一的。 注意： 实际应用中，不能保证被查找的数据集中各元素 的关键字互不相同，所以可将二叉排序树定义中BST 性质(1)里的"小于"改为"大于等于"，或将BST性质 (2)里的"大于"改为"小于等于"，甚至可同时修改这两 个性质。 （3） 按中序遍历该树所得到的中序序列是一个 递增有序序列
←例>两棵二叉排序树 退化成单 链表 60 30 80 40 30506898 58 36 60 (a) (b) 图93二叉排序树示例 对图93(a)所示的二叉排序树进行中序遍历得到 的结果是30,36,40,50,60,68,80,98;对图 9.3(b)所示的二叉排序树进行中序遍历的结果为30, 40,50,60
60 40 80 30 50 68 98 36 30 40 60 58 例 两棵二叉排序树 （a） （b） 图9.3二叉排序树示例 对图9.3（a）所示的二叉排序树进行中序遍历得到 的结果是30，36，40，50，60，68，80，98；对图 9.3（b）所示的二叉排序树进行中序遍历的结果为30， 40，50，60。 退化成单 链表
大大★大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大大 二叉排序树用的头文件 文件名: bstree. h 大大大大大大大大大大大大大大大大大大大大大大大大大大 二叉排序树存储结构 include<stdio h> 定义 includesstdlib. h> typedef int datatype typedef struct node /二叉排序树结点定义* i datatype key /结点值 struct node child,* rchild;/左、右孩子指针 snode pede bsnode *bstree
/**************************************/ /* 二叉排序树用的头文件 */ /* 文件名：bstree.h */ /**************************************/ #include<stdio.h> #include<stdlib.h> typedef int datatype; typedef struct node /*二叉排序树结点定义*/ { datatype key; /*结点值*/ struct node *lchild,*rchild; /*左、右孩子指针*/ }bsnode; typedef bsnode *bstree; 二叉排序树存储结构 定义
基于二叉排序树的查找运算 对于一棵给定的二叉排序树,树中的查找运算很 容易实现,其算法可描述如下 (1)当二叉树为空树时,检索失败; (2)如果二叉排序树根结点的关键字等于待检索的 关键字,则检索成功; (3)如果二叉排序树根结点的关键字小于待检索的 关键字,则用相同的方法继续在根结点的右子树中检 索 (4)如果二叉排序树根结点的关键字大于待检索的 关键字,则用相同的方法继续在根结点的左子树中检 索
一、基于二叉排序树的查找运算 对于一棵给定的二叉排序树，树中的查找运算很 容易实现，其算法可描述如下： （1）当二叉树为空树时，检索失败； （2）如果二叉排序树根结点的关键字等于待检索的 关键字，则检索成功； （3）如果二叉排序树根结点的关键字小于待检索的 关键字，则用相同的方法继续在根结点的右子树中检 索； （4）如果二叉排序树根结点的关键字大于待检索的 关键字，则用相同的方法继续在根结点的左子树中检 索