企业官网建设流程全解析

二叉排序树(Binary Sort Tree)

二叉排序树又称为二叉查找(搜索)树(BST)

它或者是一颗空树，或者是具有如下性质的二叉树：

1) 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值

2) 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值

3) 它左右子树分别为二叉排序树。

BST的特点

（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。

（2） 二叉排序树中，各结点关键字是惟一的。实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的"小于"改为"大于等于"，或将BST性质(2)里的"大于"改为"小于等于"，甚至可同时修改这两个性质。

（3） 按中序遍历该树所得到的中序序列是一个递增有序序列。

构造二叉树

已知先序序列和中序序列可以确定出二叉树；

已知中序序列和后序序列也可以确定出二叉树；

但，已知先序序列和后序序列却不可以确定出二叉树；为什么？举个3个结点的反例。

例如：已知结点的先序序列为ABCDEFG，中序序列为CBEDAFG。构造出二叉树。过程见下图：

普通树转换成二叉树

由于二叉树是有序的，而且操作和应用更广泛，所以在实际使用时，我们经常把普通树转换成二叉树进行操作。如何转换呢？一般方法如下：

​ 1．将树中每个结点除了最左边的一个分支保留外，其余分支都去掉；

​ 2．从最左边结点开始画一条线，把同一层上的兄弟结点都连起来；

​ 3．以整棵树的根结点为轴心，将整棵树顺时针大致旋转45度。

图A所示的普通树转换成二叉树的过程如图B所示：

森林转化为二叉树

森林，指的是由 n（n>=2）棵互不相交的树组成的集合，如图 1 所示。

在某些实际场景中，为了便于操作具有森林结构的数据，往往需要将森林转化为一整棵二叉树。

我们知道，任意一棵普通树都可以转化为二叉树，而森林是由多棵普通树构成的，因此自然也可以转化为二叉树，其转化方法是：

1. 首先将森林中所有的普通树各自转化为二叉树；
2. 将森林中第一棵树的树根作为整个森林的树根，其他树的根节点看作是第一棵树根节点的兄弟节点，采用孩子兄弟表示法将所有树进行连接；

（补充孩子兄弟表示法：左指针：始终指向节点的第一个孩子；右指针：始终指向节点的下一个兄弟）

如图 2 所示，先将森林包含的所有普通树各自转化为二叉树，然后将其他树的根节点看作为第一棵二叉树的兄弟节点，采用孩子兄弟表示法进行连接。

森林转化为二叉树，更多的是为了对森林中的节点做遍历操作。前面讲过，遍历二叉树有 4 种方法，分别是层次遍历、先序遍历、中序遍历和后序遍历。转化前的森林与转化后的二叉树相比，其层次遍历和后序遍历的访问节点顺序不同，而前序遍历和中序遍历访问节点的顺序是相同的。

以图 1 中的森林为例，其转化后的二叉树为图 2c)，两者比较，其先序遍历访问节点的顺序都是A B C D E F G H I J；同样，中序遍历访问节点的顺序也相同，都是B C D A F E H J I G。而后序遍历和层次遍历访问节点的顺序是不同的。

提示，由二叉树转化为森林的过程也就是森林转化二叉树的逆过程，也就是图 2 中由 c) 到 b) 再到 a) 的过程。

二叉树计数问题

具有n个结点的不同形态的二叉树有多少棵？具有n个结点的不同形态的树有多少棵？首先了解两个概念，“相似二叉树”是指两者都为空树或者两者均不为空树，且它们的左右子树分别相似。“等价二叉树”是指两者不仅相似，而且所有对应结点上的数据元素均相同。二叉树的计数问题就是讨论具有n个结点、互不相似的二叉树的数目。

​ 在 n 很小时，很容易得出，（下图）。

一般情况，一棵具有 n(n>1) 个结点的二叉树可以看成是由一个根结点、一棵具有 i 个结点的左子树和一棵具有 n-i-1 个结点的右子树组成，其中 0<=i<=n-1 ,由此不难得出下列递归公式：

我们可以利用生成函数讨论这个递归公式，得出

注意：

类推到具有 n 个结点、互不相似的多叉树的数目

由于树可以转换成二叉树且转换之后的根节点没有右儿子，所以，可以推出：。

B树

它是一种平衡的多叉树，称为 B 树；与平衡二叉树类似，只是他是多叉的。

可以想象，假如每一层的分叉达到上千个，在这个树里做查找，近乎于顺序查找。

相比平衡二叉树所对应的二分查找，效率要低很多，那么这样的数据结构，有什么用处呢？

实际上是因为对于很多存储设备来说，顺序读的速度经常是随机读的数十倍，比如我们的机械硬盘，在这种设备上，用二叉的方式来做查询，时间将全部花在寻道上。这时 B-Tree 的优势就体现出来了。