二叉排序树，二叉排序树的定义
1、构造平衡的二叉排序树 34二叉排序树，23，15，98，115，28以下是详细过程1 插入34， 这是第一个结点，是根结点2 插入23， 比34小，作为34的左分支 34 233 插入15， 比34和23都小，15作为23的左分支，结点34的平衡因子BF变成2左子树过高， 要右旋就是顺时针旋转，旋转后二叉排序树；二叉搜索树和二叉排序树是同一种数据结构，英文全称为“Binary Search Tree”BST其核心定义与特性如下定义与性质二叉搜索树二叉排序树满足以下条件若树非空，则根节点的值大于左子树所有节点的值，且小于右子树所有节点的值左右子树本身也必须是二叉搜索树这一递归性质确保二叉排序树了树中所有；采用边查找边插入的方式，类似重新建立一个一维数组时间复杂度＝On因为深度不平衡，所以会发展成单链的形状，就是一条线 n个点那么深二叉排序树是查找过程中，当树中不存在关键字等zhi于给定值的结点时再进行插入新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的。
2、在二叉排序树中插入新结点，要保证插入后的二叉树仍符合二叉排序树的定义插入过程若二叉排序树为空，则待插入结点*S作为根结点插入到空树中当非空时，将待插结点关键字Skey和树根关键字tkey进行比较，若skey = tkey，则无须插入，若skeylt tkey，则插入到根的左子树中。
3、二叉排序树Binary Sort Tree，首先它是一棵树，“二叉”这个描述已经很明显了，就是树上的一根树枝开两个叉，于是递归下来就是二叉树了下图所示，而这棵树上的节点是已经排好序的，具体的排序规则如下若左子树不空，则左子树上所有节点的值均小于它的根节点的值 若右子树不空，则右字数上；二叉排序树满足任意结点的左子树上的所有结点都小于它，而右子树上的所有结点都大于它因此这棵二叉排序树的层次遍历结果为5 3 9 1 4 6 2 7 8；二叉排序树Binary Search Tree，简称 BST是一种二叉树，它满足以下性质1 对于每个节点，其左子树中所有节点的值都小于该节点的值，右子树中所有节点的值都大于该节点的值2 没有重复的节点值根据上述性质，二叉排序树我们可以按照以下步骤来绘制二叉排序树1 首先，确定根节点的值在二叉排序树中，根节点的值是整个树中最大的值或最；二叉树和二叉排序树区别为子树结点不同键值相等不同子树树型不同一子树结点不同 1二叉树二叉树的左右子树上所有结点的值可以大于等于和小于它的根结点的值2二叉排序树二叉排序树若左右子树不空，则左右子树上所有结点的值均小于它的根结点的值二键值相等不同 1二叉树二叉树可以有键值相等的结点2；插入操作的基本步骤新节点颜色设定将新插入节点的颜色赋为红色这是因为若设为黑色，会导致根到叶子的路径上有一条路径多一个额外的黑节点，调整难度较大而设为红色节点后，虽可能导致两个连续红色节点的冲突，但可通过颜色调换和树旋转来调整，相对简单按二叉排序树规则插入以二叉排序树的插入。
4、1第一个数字50，作为根节点 所有数字都要先跟50比，大的放右侧，小的放左2第二个数字72和50比，大于50，分叉分到右侧 3第三个数字43跟50比 ，小于50，分叉分到左侧 485先跟50比，应该归到右侧，但是右侧已经有了一个72了，85位置跟72重复了，所以要把冲突的位置作为节点继续分叉；答案D 当二二叉排序树的叶子结点全部都在相邻的两层内时，深度最小理想情况是从第一层到倒数第二层为满二叉树类比完全二叉树，可得深度为log2n+1；含有4个元素各不相同的节点的二叉树，共有14种只要画出所有含有4个节点的二叉树，对每一个二叉树，对它进行中序遍历时，按4个元素值升序的序列进行填入，所得的二叉树，就是一种所求的二叉排序树，因为节点数较少，所以可以穷举画出，共有14种当元素个数为0，1，2，3，时相应的二叉排；n个结点的二叉排序树在最坏的情况下的平均查找长度为n+12二叉排序树每个结点的Ci为该结点的层次数最坏情况下，当先后插入的关键字有序时，构成的二叉排序树蜕变为单支树，树的深度为其平均查找长度n+12和顺序查找相同，最好的情况是二叉排序树的形态和折半查找的判定树；一用法不同 二叉判定树是用于描述解决问题的思路，比如可以使用判定树描述N个数的比较过程，正如你所提到的，它也可以用于描述折半查找的过程，从这个判定树分析算法的效率，二叉排序树是用于排序的，它是一种排序方法二性质 二叉排序树又称为二叉查找树，是一种特殊的二叉树二叉排序树他或者是一种空树；二叉排序树BST，二叉查找树定义二叉排序树是一种特殊的二叉树，其左子树上所有节点的值均小于根节点的值，右子树上所有节点的值均大于根节点的值特点查找时间复杂度为Oh，其中h是树的高度在最优情况下树完全平衡，查找效率接近Olog n但在最坏情况下树退化成链表，查找。
