解释BST不是二叉排序树

我觉得没关系。

二叉排序树

1. 二叉排序树的定义。

二叉排序树也称为二叉搜索树。 它被定义为：二叉排序树或空树，或满足以下属性的二叉树：

如果其左子树不为空，则左子树上所有节点的值都小于根节点的值。

如果其右子树不为空，则右子树上所有节点的值都大于根节点的值;

左子树和右子树本身都是一个二叉排序树。

上述属性称为二叉排序树属性（BST属性），因此二叉排序树实际上是满足BST属性的二叉树。

2.二叉排序树的特点。

从BST的性质来看：

1）对于二叉排序树中的任何节点x，左（右）子树中任何节点y（如果存在）的关键字必须小于x的关键字（大）。

2）在二叉排序树中，每个节点关键字都是唯一的。

注意：在实践中，不能保证搜索数据集中每个元素的关键字彼此不同，因此可以在二进制排序树定义中定义 bst 属性 （1）"小于"相反"小于或等于"，或者将在 （2） 中成为 BST。"大于"相反"大于或等于"，甚至两者兼而有之。

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是一种二叉排序树。

你是什么意思？二叉排序树

是的，下面有一个明确的解释，所以让我们自己看看。

二叉排序树也称为二叉搜索树和二叉搜索树。 二叉排序树是左子树上的节点小于根节点，右子树上的节点大于根节点，左右子树也是二叉排序树的二叉树。

实例。 当你要在二叉排序树中插入一个元素时，从根节点开始查找，首先取根节点作为当前节点，如果要插入的值小于当前节点的值，则判断当前节点的左子节点是否为空，如果为空， 要插入的值将是当前节点的左子节点，如果不为空，则当前节点的左子节点将继续搜索为当前节点;当待插入的值大于当前节点的值时，判断当前节点的右子节点是否为空，如果为空，则待插入的值将作为当前节点的右子节点，如果不为空，则当前节点的右子节点将继续作为当前节点进行搜索。

节点定义。 递归实现。

非递归实现。

对于中阶遍历，遍历结构只是按升序排列的数字序列。

递归写作。 非递归写作。

搜索二叉排序树时，从根节点开始搜索，将根节点作为当前节点，如果当前节点的值等于搜索的值，则搜索结束并返回成功。 如果当前节点的值小于搜索值，则判断当前节点的左子节点是否为空，如果为空，则搜索的值不在树中，搜索结束时返回失败，如果不为空，则以当前节点的左子节点为当前节点并继续搜索; 如果当前节点的值大于搜索值，则判断当前节点的右子树是否为空，如果为空，则搜索的值不在树中，搜索结束，返回失败，如果不为空，则使用当前节点的右子节点作为当前节点， 搜索仍在继续。

删除二叉排序树有三种基本方案。

您可以直接删除该节点。

将要删除的节点的子节点替换为当前节点。

在要删除的节点的右子树中找到最小的值，替换要删除的节点，删除最小的节点（也可以从左子树中找到最大的节点）。

细节。 算法实现：

二叉排序树的搜索时间与二叉树的高度有关，高度越高，需要的搜索时间就越多。

二叉排序树的高度有两种极端情况，一种是完整的二叉树，另一种是每层只有一个节点的情况，就变成了链表。

当它是一个完整的二叉树时：在这种情况下，时间复杂度是 o（log2n）。

当每层只有一个节点时，即当链表被制作时：在这种情况下，时间复杂度为 o（n）。

o（n）。

二叉排序树，又称二叉搜索树，又称二叉搜索树。 是一种数据结构。 通常，查询效率高于链表结构。

定义 1：空树或具有以下属性的二叉树：

1）如果左边的子树不为空，则左边子树上所有节点的值都小于其根节点的值;

2）如果右子树不为空，则右子树上所有节点的值大于其根节点的值;

3）左子树和右子树也分别是二元排序树。

4） 没有键值相等的节点。

定义 2：空树或具有以下属性的二叉树：

1）如果左边的子树不为空，则左边子树上所有节点的值都小于其根节点的值;

2）如果右子树不为空，则右子树上所有节点的值大于或等于其根节点的值;

3）左子树和右子树也分别是二元排序树。

定义 3：空树，或具有以下属性的二叉树：

1）如果左子树不为空，则左子树上所有节点的值小于或等于其根节点的值;

2）如果右子树不为空，则右子树上所有节点的值大于其根节点的值;

3）左子树和右子树也分别是二元排序树。

注：以上三个定义在不同的数据结构教材中定义不同，但都是正确的，在开发时需要根据不同的需求进行选择。

插入和删除：与次优二叉树相比，二叉排序树是一个动态树表。 其特点是：

树的结构通常不是一次性生成的，而是在查找过程中插入的，当树中没有关键字等于给定值的节点时。 新插入的节点必须是新添加的叶节点，并且是查找不成功时查找路径上最后一个访问节点的左子节点或右子节点。

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

二进制排序树通常使用二进制链表作为存储结构。 通过中阶遍历二叉排序树可以得到有序序列，通过构造二叉排序树可以将有序序列变成有序序列，构建树的过程就是对无序序列进行排序的过程。 每次插入一个新节点，都是二叉排序树上的新叶节点，插入操作时不需要移动其他节点，只需要将一个节点的指针从空改为非空即可。

二叉排序树属性：

1.如果其左子树不为空，则左子树上所有节点的值小于其根节点的值;

2. 如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值。

3. 换句话说，任何节点的键值都必须大于其左子树中每个节点的键值，并且小于其右子树中每个节点的键值。

1. 定义。 二叉排序树，又称二叉查找树，它要么是空树; 或具有以下属性的二叉树：

1.如果其左子树不为空，则左子树上所有节点的值小于其根节点的值;

2.如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值;

3.它的左子树和右子树也分别是二元排序树。

二叉搜索树 （BST） 也称为二叉搜索树或二叉排序树。 二叉搜索树组织为二叉树，可以由链表数据结构表示，其中每个节点都是一个对象。 通常，除了键和卫星数据外，每个节点还包含属性 lchild、rchild 和 parent，它们分别指向节点的左子节点、右子节点和父节点（父节点）。

如果子节点或父节点不存在，则相应属性的值为 null （nil）。 根节点是树中唯一父指针为nil的节点，叶节点的子节点指针也是nil。

在计算机科学中，二叉搜索树（BST），有时也称为二叉排序树，是一种特殊类型的容器：一种将“项目”（例如，数字、名称等）存储在内存中的数据结构。 它们允许快速查找、添加和删除项目，并可用于实现动态项目集，或允许按关键字查找项目的查找表（例如，按姓名查找某人的 ** 编号）。

二进制排序树以有序的方式保存它们的关键字，以便查找和其他操作可以使用二分法原理：当在树中查找关键字（或在哪里插入新关键字）时，它们从根到叶遍历树，将它们与存储在树节点中的关键字进行比较，并根据比较结果决定继续在左子树或右子树中搜索。 平均而言，这意味着每次比较都允许操作跳过树中大约一半的节点，因此每次查找、插入或删除都需要树中存储的项目数的对数时间复杂度。

这比在（未排序的）数组中按关键字查找项目所需的线性时间要复杂得多，但比哈希表上的相应操作要慢。

计算机科学中出现了二叉排序树的几种变体; 本文主要讨论基本类型，并在适当的情况下引用更高级的类型。

二叉排序树是具有根节点的二叉树，内部节点每个节点存储一个关键字（以及可选的相关值），每个节点有两个可区分的子树，通常表示为左和右。 该树还具有二叉搜索属性，它声明每个节点中的关键字必须大于或等于存储在左侧子树中的任何关键字，并且小于或等于存储在右侧子树中的任何关键字。 [1] 树的叶子（最终节点）不包含关键字，也没有区分它们的结构。

通常，每个节点表示一条信息记录，而不是一个数据元素。 但是，出于排序目的，会根据节点的关键字而不是其相关记录的任何部分来比较节点。 与其他数据结构相比，二叉排序树的主要优点是它们在分类算法和搜索算法（如有序遍历）中非常有效; 它们也很容易编码。

二进制排序树的形状完全取决于其插入和删除的顺序，并且可以退化。

经过长时间的随机插入和删除混合序列后，树的预期高度接近关键字数的平方根 n，并且它的增长速度比 log n 快得多。

已经有许多研究来防止树木退化，这会导致最坏情况下的时间复杂度为o（n）（有关详细信息，请参阅部分）。

二元排序树在中阶遍历后排序;

构建二叉排序树的步骤如下;

插入方法构造。

第二个节点 4 小于 6，因此在 6 处插入左子树;

第三个节点 8 大于 6，因此在 6 处插入右侧子树;

第四个节点小于 6，先进入左边的子树，然后与 4 进行比较，5 大于 4，所以在 4 处插入右边的子树;

以此类推，首先将要插入的节点与根节点进行比较，根节点大于根节点并进入右侧子树，反之亦然。

与比较输入的左子树（右子树）的节点相同;

直到插入中没有更多的节点; 您给出的最后一个排序的二叉排序树如下;

中间遍历的结果是：3 4 5 6 7 8 9 ;

预购遍历的结果是：6 4 3 5 8 7 9 ;