二叉排序树定义

解释一下bst 不是二叉排序树~

百度上搜的 觉得还可以的
二叉排序树(Binary Sort Tree)
1、二叉排序树的定义
二叉排序树(Binary Sort Tree)又称二叉查找(搜索)树(Binary Search Tree)。其定义为：二叉排序树或者是空树，或者是满足如下性质的二叉树：
①若它的左子树非空，则左子树上所有结点的值均小于根结点的值；
②若它的右子树非空，则右子树上所有结点的值均大于根结点的值；
③左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质(BST性质)，故二叉排序树实际上是满足BST性质的二叉树。
2、二叉排序树的特点
由BST性质可得：
（1） 二叉排序树中任一结点x，其左(右)子树中任一结点y(若存在)的关键字必小(大)于x的关键字。
（2） 二叉排序树中，各结点关键字是惟一的。
注意：
实际应用中，不能保证被查找的数据集中各元素的关键字互不相同，所以可将二叉排序树定义中BST性质(1)里的"小于"改为"小于等于"，或将BST性质(2)里的"大于"改为"大于等于"，甚至可同时修改这两个性质。
（3） 按中序遍历该树所得到的中序序列是一个递增有序序列。
【例】下图所示的两棵树均是二叉排序树，它们的中序序列均为有序序列：2，3，4，5，7，8。
3、二叉排序树的存储结构
typedef int KeyType； //假定关键字类型为整数
typedef struct node { //结点类型
KeyType key； //关键字项
InfoType otherinfo； //其它数据域，InfoType视应用情况而定，下面不处理它
struct node *lchild，*rchild； //左右孩子指针
} BSTNode；
typedef BSTNode *BSTree； //BSTree是二叉排序树的类型

某个节点的平衡因子就是那个节点左子树的高度减去右子树的高度，你可以对照左边的图检查一下是不是这样
比如a节点的因子就是它左边的子树的高度，这里是3，减去右子树的高度，这里是2，所以=1
对于b节点，左子树高度为1，右边为2，所以1-2=-1就是b节点的平衡因子

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

二叉排序树性质：
1、就是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2、若它的右子树不空，则右子树上所有节点的值均大于其根节点的值。
3、换句话说就是：任何节点的键值一定大于其左子树中的每一个节点的键值，并小于其右子树中的每一个节点的键值。

二叉排序树（Binary Sort Tree），又称二叉查找树（Binary Search Tree），亦称二叉搜索树。是数据结构中的一类。在一般情况下，查询效率比链表结构要高。

定义一：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；
（4）没有键值相等的结点。

定义二：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值；
（3）左、右子树也分别为二叉排序树。

定义三：

一棵空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上所有结点的值均小于或等于它的根结点的值；
（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；
（3）左、右子树也分别为二叉排序树；

【注】：以上的三种定义在不同的数据结构教材中均有不同的定义方式 但是都是正确的 在开发时需要根据不 同的需求进行进行选择。

插入删除：
与次优二叉树相对，二叉排序树是一种动态树表。其特点是：树的结构通常不是一次生成的，而是在查找过程中，当树中不存在关键字等于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右孩子结点。

在 计算机科学中, 二叉搜索树(BST)，有时也被称为二叉排序树，是一种特殊类型的容器: 在内存中存储“项目”（例如数字，名称等）的数据结构。它们允许快速查找、添加和删除项目，并且可以用于实现动态项目集，或者允许通过其关键字查找项目的查找表(例如，通过名称查找人员的电话号码)。
二叉排序树有序保存它们的关键字，以便查找和其他操作可以使用 二分的原则:当在树中寻找关键字(或插入新关键字的位置)时，他们从根到叶遍历树，与存储在树结点中的关键字进行比较，并根据比较结果决定继续在左或右子树中搜索。平均而言，这意味着每次比较都允许操作跳过树的大约一半结点，因此每次查找、插入或删除都需要存储在树中的项目数的对数级别的时间复杂度。这比在(未排序的)数组中按关键字查找项目需要的线性时间复杂的好多了 ，但比哈希表上的相应操作要慢。
计算机科学出现了二叉排序树的几种变体；本文主要讨论基本类型，并在适当的时候引用更高级的类型。
二叉排序树是带根结点的二叉树，其内部结点各自存储一个关键字(以及可选的相关值),并且各自具有两个可区分的子树，通常表示为左和右。该树还拥有二分搜索的属性，该属性声明每个结点中的关键字必须大于或等于左子树中存储的任何关键字，并且小于或等于右子树中存储的任何关键字。[1] 树的叶子(最终结点)不包含关键字，也没有结构来区分它们。
通常，每个结点代表的信息是一条记录，而不是一个数据元素。 然而，出于排序的目的，结点是根据它们的关键字而不是它们相关记录的任何部分进行比较的。二叉排序树相对于其他数据结构的主要优势是在分类算法和 搜索算法比如有序遍历中非常有效；它们也很容易编码。
二叉搜索树是用于构造更抽象的数据结构（如集合，多集合和关联数组）的基础数据结构。.
当在二叉排序树中插入或搜索元素时，必须将每个被访问结点的关键字与要插入或找到的元素的关键字进行比较。
二叉排序树的形状完全取决于插入和删除的顺序，并且可能退化。
在长时间随机插入和删除的混合序列之后，树的预期高度接近关键字数量的平方根 √n，它的增长速度比 log n快得多。
已经有许多研究来防止树的退化，这种退化导致最坏情况下的时间复杂度 O(n) (有关详细信息，请参见部分)。

一、定义

二叉排序树，又叫二叉查找树，它或者是一棵空树；或者是具有以下性质的二叉树：
1. 若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；
2. 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；
3. 它的左右子树也分别为二叉排序树。

二叉搜索树（BST）又称二叉查找树或二叉排序树。一棵二叉搜索树是以二叉树来组织的，可以使用一个链表数据结构来表示，其中每一个结点就是一个对象。一般地，除了key和卫星数据之外，每个结点还包含属性lchild、rchild和parent，分别指向结点的左孩子、右孩子和双亲（父结点）。如果某个孩子结点或父结点不存在，则相应属性的值为空（NIL）。根结点是树中唯一父指针为NIL的结点，而叶子结点的孩子结点指针也为NIL。

---

晴隆县13955271509： 二叉排序树 - 搜狗百科？
符纪玉屏： 二叉排序树(Binary Sort Tree)又称二叉查找树. 它或者是一棵空树;或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树 http://baike.baidu.com/view/647462.htm

晴隆县13955271509： 二叉排序树的类型定义如下: - ？
符纪玉屏： 二叉排序树或者是一棵空树,或者是具有下列性质的二叉树: (1)若左子树不空,则左子树上所有结点的值均小于它的根结点的值; (2)若右子树不空,则右子树上所有结点的值均大于它的根结点的值; (3)左、右子树也分别为二叉排序树; (4)没有键值相等的节点.

晴隆县13955271509： 二叉排序树的定义,平衡二叉树和某接点的平衡因子的定义 - ？
符纪玉屏： 某个节点的平衡因子就是那个节点左子树的高度减去右子树的高度,你可以对照左边的图检查一下是不是这样 比如a节点的因子就是它左边的子树的高度,这里是3,减去右子树的高度,这里是2,所以=1 对于b节点,左子树高度为1,右边为2,所以1-2=-1就是b节点的平衡因子

晴隆县13955271509： 什么是二叉排序树?？
符纪玉屏： 它是c语言程序编程的一个结构!

晴隆县13955271509： 二叉排序树的构造与查找 - ？
符纪玉屏： 一样的,折半查找树是二叉判定树,跟二叉排序树是不同的

晴隆县13955271509： 计算机c语言中什么是“二叉树”? - ？
符纪玉屏： 在计算机科学中,二叉树是每个结点最多有两个子树的有序树.通常子树的根被称作“左子树”(left subtree)和“右子树”(right subtree).二叉树常被用作二叉查找树和二叉堆或是二叉排序树. 二叉树的每个结点至多只有二棵子树(不存在度大...

晴隆县13955271509： 二叉排序树的构造和查找方法 - ？
符纪玉屏： 二叉排序树的构造过程:按照给定序列,以此将结点插入二叉排序树中,在二叉排序树中插入新结点,要保证插入后的二叉树仍符合二叉排序树的定义. 插入过程:若二叉排序树为空,则待插入结点*S作为根结点插入到空树中; 当非空时,...

晴隆县13955271509： 平衡二叉树是不是二叉排序树? - ？
符纪玉屏： 平衡二叉树不一定是二叉排序树(平衡二叉树的定义只涉及到了左子树与右子树,而无关关键字的定义),而二叉排序树一定是平衡二叉树. 常见的符合平衡树的有,B树(多路平衡搜索树)、AVL树(二叉平衡搜索树)等.平衡树可以完成集...

晴隆县13955271509： 什么是完全二叉树,平衡二叉树,二叉排序树 - ？
符纪玉屏： 首先平衡二叉树是特殊的二叉排序树,他的结点元素间存在着偏序关系. 其次相对于一般的二叉排序树,平衡二叉树的左右子树的深度差也有不超过1层的约束. 这样使得平衡树是同种元素序列情况下的深度最小的二叉排序树.这可以减少二叉树元素查找的深度,从而提升平均查找效率.