二叉查找树

二叉树的介绍

普通树（多叉树）若不转化为二叉树，则运算很难实现。

为何要重点研究每结点最多只有两个 “叉” 的树？

• 二叉树的结构最简单，规律性最强；
• 可以证明，所有树都能转为唯一对应的二叉树，不失一般性

1. 二叉树的定义

二叉树是每个节点最多有两个子树的树结构。
基本特点:

• 结点的度小于等于2
• 有序树（子树有序，不能颠倒）
  

2. 二叉树的性质

性质1: 在二叉树的第i层上至多有个结点。

• 第i层上至少有1个结点

性质2：深度为k的二叉树至多有2^{k}-1个结点(k≥1)。

• 包含$$n$$个结点的二叉树的高度至少为$$log_2 (n+1)$$。
• 深度为k时至少有$$k$$个结点？

性质3：对于任何一棵二叉树，若2度的结点数有n2个，则叶子数n0必定为n2＋1 (即n_0=n_2+1)。

证明1：
二叉树中所有结点的度数均不大于2
结点总数(n)=”0度结点数(n0)” + “1度结点数(n1)” + “2度结点数(n2)

另一方面，0度结点没有孩子，1度结点有一个孩子，2度结点有两个孩子，故二叉树中孩子结点总数是：n1+2n2。此外，只有根不是任何结点的孩子。故二叉树中的结点总数又可表示为等式二。

证明2：

3. 特殊形态二叉树

满二叉树

定义：一棵深度为k 且有2k -1个结点的二叉树。
特点：每层都“充满”了结点

完全二叉树

定义：一棵二叉树中，只有最下面两层结点的度可以小于2，并且最下一层的叶结点集中在靠左的若干位置上。这样的二叉树称为完全二叉树。
特点：叶子结点只能出现在最下层和次下层，且最下层的叶子结点集中在树的左部。显然，一棵满二叉树必定是一棵完全二叉树，而完全二叉树未必是满二叉树。

性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子编号必为2i，其右孩子编号必为2i＋1；其双亲的编号必为i/2。

二叉查找树

定义：二叉查找树(Binary Search Tree)，又被称为二叉搜索树。设x为二叉查找树中的一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。

在二叉查找树中：

1. 若任意节点的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
2. 任意节点的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
3. 任意节点的左、右子树也分别为二叉查找树。
4. 没有键值相等的节点（no duplicate nodes）。