文档介绍：5 二叉树
1
二叉树的概念
二叉树的周游
二叉树的存储结构
二叉搜索树
堆与优先队列
Huffman树及其应用
二叉树知识点总结
主要内容
2
二叉搜索树
二叉搜索树
二叉搜索树的查找
二叉搜索树的插入操作
二叉搜索树的删除操作
3
二叉搜索树
一棵非空的二叉搜索树满足以下特征:
每个结点都有一个作为搜索依据的关键码,所有结点的关键码互不相同。
左子树(如果存在)上的所有结点的关键码均小于根结点的关键码。
右子树(如果存在)上的所有结点的关键码均大于根结点的关键码。
根结点的左右子树也都是二叉搜索树。
二叉搜索树又称为“二叉排序树”、“二叉查找树”、“二叉检索树”
4
二叉搜索树举例
L
N
P
E
M
C
Y
122
250
300
110
200
99
105
230
216
60
70
80
50
55
40
是二叉搜索树
是二叉搜索树
不是二叉搜索树
5
二叉搜索树的基本操作
查找
插入
删除
6
二叉搜索树查找操作
分割式查找法:
若根结点的关键码等于查找的关键码,成功。
否则,若小于根结点的关键码,查其左子树。大于根结点的关键码,查其右子树。
二叉搜索树的高效率在于继续检索时只需要查找两棵子树之一
7
13
8
5
23
18
37
如何查找元素 5 ?
5
5
5
查找成功!
二叉搜索树查找操作
8
二叉搜索树查找分析——平均情况分析
15
60
70
30
20
50
15
60
70
30
20
50
ASL=(1+2+2+3+3+3)/6=14/6
ASL=(1+2+3+4+5+6)/6=21/6
9
二叉搜索树插入操作
首先执行查找算法,找出被插结点的父亲结点。
判断被插结点是其父亲结点的左、右儿子。将被插结点作为叶子结点插入。
若二叉树为空。则首先单独生成根结点。
注意:新插入的结点总是叶子结点。
10