二叉搜索树

或者是一棵空树

或者是具有下列性质的二叉树

1,每个结点都有一个作为搜索依据的关键码(KEY),所有结点的关键码互不相同.

2.左子树上所有结点的关键码都小于根结点的关键码.

3.右子树上所有结点的关键码都大于根结点的关键码.

4.左子树和右子树也是二叉搜索树.

AD:乙醇气体检测仪、探测器、报警器

二叉搜索树类定义

二叉搜索树上的搜索

在二叉搜索树上的搜索

二叉搜索树的插入

二叉搜索树的删除

与二叉搜索树相关的中序游标类

最优二叉搜索树

扩充二叉搜索树

最优二叉搜索树

AVL树:又称为高度平衡的二叉搜索树

是1962年由两位俄罗斯数学家G.M.Adel'son_Vel'sky 和 E.M.Landis提出的.

引入它的目的,是为了提高二叉搜索树的效率,减少树的平均搜索长度.

在把N个不同的元素划分为若干等价类时,一种解决方案是先把每一个对象看作是一个单元素集合,然后按一定顺序将属于同一等价类的元素所在的集合合并.

在此过程中将反复地使用一个搜索运算,确定一个元素在哪一个集合中.

UFSETS(S)构造函数,将并查集(用UFSETS命名)中S个元素初始化为S个只有一个单元素的子集合.根结点的PARENT值等于-1.

树的存储表示

树的存储表示

森林与二叉树的转换

树的遍历

二叉树的计数

霍夫曼树

路径长度

霍夫曼树

霍夫曼编码

树的存储表示

广义表表示

双亲表示

森林转化为二叉树的表示

二叉树转换为森林的规则

深度优先遍历

广度优先遍历

广义表表示:

树结点,根结点,除根结点外的其它非叶结点(分支结点)

原子结点(ATOM),表头结点(HEAD),子表结点(LST)

指示前驱和后继的指针叫做线索.

中序:指向该结点中序下的前驱结点

前序与后序线索化

前几章我们介绍了数组,顺序表,单链表,栈,队列和优先队列等数据结构,这些结构都是线性结构,结构中的对象都是同一类型的数据元素.

本节我们将放宽对表中元素的限制,允许表中元素自身具有某种结构,这就引入了广义表的概念.