二叉排序树(二叉排序树的构造)

一、判断一棵树是否为二叉排序树

由于二叉排序树的中序遍历时得到的一定是个一个升序序列，我们可以根据这一性质，利用中序遍历进行判定。

算法：

1.设置全局变量max为无穷小。

2.若树为空，则返回true。

3.否则递归判断左子树是否为二叉排序树，并用flag1保存结果。

4.若flag1为假或者根节点关键字小于等于左子树的关键字，则返回false。

5.否则递归判断右子树是否为二叉排序树，并用flag2保存结果。

6.返回flag2。

二、二叉排序树的定义

首先二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。

二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索、插入、删除的时间复杂度等于树高，期望O(logn)，最坏O(n)（数列有序，树退化成线性表，如右斜树）。

二叉排序树性质：

1、就是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；

2、若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。

3、换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。

三、二叉排序树构造过程

二叉排序树的构造过程：按照给定序列，以此将结点插入二叉排序树中，在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义。

插入过程：若二叉排序树为空，则待插入结点*S作为根结点插入到空树中；

当非空时，将待插结点关键字S->key和树根关键字t->key进行比较，

若s->key=t->key,则无须插入，若s->key<t->key,则插入到根的左子树中，

若s->key>t->key,则插入到根的右子树中。而子树中的插入过程和在树中的插入过程相同，

如此进行下去，直到把结点*s作为一个新的树叶插入到二叉排序树中，或者直到发现树已有相同关键字的结点为止。

说明：

①每次插入的新结点都是二叉排序树上新的叶子结点。

②由不同顺序的关键字序列，会得到不同二叉排序树。

③对于一个任意的关键字序列构造一棵二叉排序树，其实质上对关键字进行排序。

查找的过程类似，从根结点开始进行比较，小于根结点的在左子树上，大于根结点的在右子树上，以此查找下去，直到查找成功或不成功（比较到叶子结点）。