二叉排序树定义
百度上搜的 觉得还可以的
二叉排序树(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。
二叉排序树的类型定义如下:
答：二叉排序树（Binary Sort Tree），首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了（下图所示），而这棵树上的节点是已经排好序的，具体的排序规则如下：若左子树不空，则左子树上所有节点的值均小于它的根节点的值 若右子树不空，则右字数上...
编写算法:已知二叉排序树按二叉链表形式存储,树中结点各不相同,欲得...
答：首先看下二叉排序树的定义：二叉排序树（Binary Sort Tree）又称二叉查找树，亦称二叉搜索树。 它或者是一棵空树；或者是具有下列性质的二叉树： （1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； （2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； （3）左、...
二叉排序树定义
答：首先二叉排序树也是一棵二叉树，所谓二叉树，就是“任何节点最多只允许两个子节点”，这两个子节点称为左右子节点。二叉排序树通常采用二叉链表作为存储结构。中序遍历二叉排序树可得到一个依据关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即是对无序序列...
中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。这句话对吗...
答：对的，中序遍历一棵二叉排序树的结点就可得到排好序的结点序列这句话是没有错误的，因为二叉排序树的根节点大于左子树，小于右子树，然后使用中序遍历算法，中序遍历算法先遍历左子树，然后是根节点，然后是右子树。根据遍历的特性，所有的先遍历的结点，一定是小于后边遍历的结点，所以说中序遍历一棵...
已知下面二叉排序树的各结点的值依次为1-9,请标出各结点的值
答：1、二叉排序树的定义就是左边的子树都比根小，右边的子树都比根大，所以此图的根（也就是最上面这个肯定是5，左边的肯定是1-4，右边的肯定是6-9 2、先看左子树的根。它只有右子树，根据定义，所有的都要比它大，从1-4里面可以肯定是1，因为2、3、4都比它大，所以，左子树的根是1，这样还剩...
二叉排序树
答：二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。实例 当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节点的...
二叉树的定义
答：二叉树（binary tree）是指树中节点的度不大于2的有序树，它是一种最简单且最重要的树。二叉树的递归定义为：二叉树是一棵空树，或者是一棵由一个根节点和两棵互不相交的，分别称作根的左子树和右子树组成的非空树；左子树和右子树又同样都是二叉树。二叉树是树形结构的一个重要类型。许多实际...
给定序列 6 8 5 7 9 3构建二叉排序树 并画出先序索二叉树
答：二叉排序树就是中序遍历之后是有序的；构造二叉排序树步骤如下；插入法构造 第二个结点 4 比 6 来的小 所以插入在 6 的左子树；第三个结点 8 比 6 来的大 所以插入在 6 的右子树；第四个结点 5 比6 来得小 先进入左子树然后跟 4比较，5 比4 大 所以插入在 4 的右子树；以此类推 ...
逐点插入法是如何建立对应的二叉排序树的?
答：1、第一个数字50，作为根节点 （所有数字都要先跟50比，大的放右侧，小的放左）2、第二个数字72和50比，大于50，分叉分到右侧 3、第三个数字43跟50比 ，小于50，分叉分到左侧 4、85先跟50比，应该归到右侧，但是右侧已经有了一个72了，85位置跟72重复了，所以要把冲突的位置作为节点继续分叉...
平衡二叉树定义
答：所谓平衡二叉树是指树中任一结点的左、右子树高度大致相同。平衡二叉树有很多种最著名的是由前苏联数学家Adelse—Velskil和Landis在1962年提出的，称为AVL树。平衡二叉树(AVL树)定义如下：平衡二叉树或者是一棵空树，或者是具有以下性质的二叉排序树：(1)它的左子树和右子树的高度之差绝对值不超过1...
