二叉树排序

1. 二叉树排序

二叉排序树就是中序遍历之后是有序的；
构造二叉排序树步骤如下；
插入法构造

第二个结点 4 比 6 来的小 所以插入在 6 的左子树；

第三个结点 8 比 6 来的大 所以插入在 6 的右子树；

第四个结点 5 比6 来得小 先进入左子树然后跟 4比较，
5 比4 大 所以插入在 4 的右子树；


以此类推 将要插入的结点先跟根结点比较， 比根结点大进入右子树 反之进入 左子树；
在跟进入的 左子树（右子树）的结点比较 方法同上；
直到没有结点了  在插入；  你给的排序最后的二叉排序树如下；



中序遍历结果是  ：  3 4 5 6 7 8 9 ；
先序遍历结果是 ： 6 4 3 5 8 7 9 ；

2. 二叉树的排序

1.答案：C
  分析：根据性质“深度为K的二叉树至多有2k -1个结点（k≥1）”可知，具有结点767是深度为10完全二叉树。前9层的结点有29-1=511个结点，在第10层的结点个数就为767-511=256，那么在第9层中具有两个子结点的结点数为256/2=128，则整个二叉树具有两个子结点的结点数为28 -1+128=384，又根据性质“对任何一棵二叉树，如果其叶子节点数为n0，具有两个子结点的结点数为n2，则 n0=n2+1”，叶子节点数为384+1=385.
2.答案：16
 分析：根据性质“在二叉树的第i层上至多有2i-1个结点”，深度为5的满二叉树的叶子结点数即为 第5层的结点数25-1=16.
3.答案：dgebhfca
分析：排列的概念问题，就不多说了。从前序排列可以得出，树的根节点为a，根节点的左节点为b，再根据中序排列中从根节点a的左右分开分别为左右子树的结点，左子树为dbge，右子树为chf，再根据前序排列c为右子树第一个即为根节点的右结点。再根据中序排列中右边根节点的左边为d，即d为b的左子树且可以看出d没有左右子树，又在根据前序排列中e紧跟在b后面得出e为b右子树，再根据根据中序排列中g在e前得出g为e的左子树。
根节点的右子树就不多做分析了，原理类似。最后得出如下二叉树，最后再进行后序排列。

3. 二叉排序树

 
该树是平衡二叉树

4. 二叉排序树

 二叉排序树也叫二叉搜索树、二叉查找树。二叉排序树树是一颗它的左子树上的节点都小于根节点，右子树上的节点都大于根节点的二叉树，且其左右子树也是二叉排序树。
   实例
                                           当要向二叉排序树中插入元素的时候，从根节点开始查找，先将根节点作为当前节点，如果要插入的值比当前节点的值小，则判断当前节点的左孩子是不是空，如果是空则将要插入的值作为当前节点的左孩子，不是空则将当前节点的左孩子作为当前节点继续查找；当要插入的值比当前节点的值大时，判断当前节点的右孩子是不是空，如果是空则将要插入的值作为当前节点的右孩子，不是空则把当前节点的右孩子作为当前节点继续查找   节点定义
   递归实现
   非递归实现
   使用中序遍历，遍历出来的结构刚好是一个升序排列的数列   递归写法
   非递归写法
   搜索二叉排序树的时候，从根节点开始搜索，将根节点作为当前节点，如果当前节点的值和搜索的值相等，则搜索结束，返回成功；如果当前节点的值小于搜索值，则判断当前节点的左孩子是不是空，如果是空，则搜索的值不在树中，搜索结束返回失败，如果不为空，则将当前节点的左孩子作为当前节点，继续搜索；如果当前节点的值大于搜索值，则判断当前节点的右子树是不是空，如果是空，则搜索的值不在树中，搜索结束，返回失败，如果不为空，则将当前节点的右孩子作为当前节点，继续搜索。
   二叉排序树的删除分为如下三种基本的情况
   直接删除节点即可
                                                                                   将要删除的节点的孩子节点替换当前节点即可
                                                                                   在要删除的节点的右子树中找一个最小的值来替换掉要删除的节点，同时将这个最小的节点删除掉（也可以从左子树中找一个最大的节点）   具体情况
                                                                                                                                                                                                                                                   算法实现：
   二叉排序树的查找时间与二叉树的高度有关，高度越高需要的查找时间就越多。   二叉排序树的高度有两种极端的情况，一种是完全二叉树，一种是每层只有一个节点的情况，变成了一个链表。
                                                                                   当是完全二叉树的时候：这种情况下的时间复杂为O(log2N)   当每一层只有一个节点时，也就是链表的时候：这种情况下的时间复杂度为O(n)   所以二叉排序树的搜索时间复杂度在：O(log2N) O(n)之间。它的插入，删除复杂度也在O(log2N) O(n)之间

5. 二叉树的插入排序是如何实现的？

采用边查找边插入的方式，类似重新建立一个一维数组时间复杂度＝O（n)因为深度不平衡，所以会发展成单链的形状,就是一条线 n个点那么深。
二叉排序树是查找过程中，当树中不存在关键字等zhi于给定值的结点时再进行插入。新插入的结点一定是一个新添加的叶子结点，并且是查找不成功时查找路径上访问的最后一个结点的左孩子或右结点。
因此二叉排序树插入时间复杂度最大为O(n)。若是二叉排序树比较平衡，其时间复杂度下降，最小的时间复杂度为O(logn)。

扩展资料：
①结点：包含一个数据元素及若干指向子树分支的信息。
②结点的度：一个结点拥有子树的数目称为结点的度。
③叶子结点：也称为终端结点，没有子树的结点或者度为零的结点。
④分支结点：也称为非终端结点，度不为零的结点称为非终端结点。
⑤树的度：树中所有结点的度的最大值。
参考资料来源：百度百科-二叉树

6. 简单说说二叉树（排序二叉树）

   树（tree）是一种抽象数据类型（ADT），用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点通过连接它们的边组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。
   如果不太明白可参考：    https://www.cnblogs.com/ysocean/p/8032642.html 
   
   
         插入操作：    
                                           
     首先要从根节点开始往下找到自己要插入的位置（即新节点的父节点）；具体流程是：新节点与当前节点比较，如果相同则表示已经存在且不能再重复插入；如果小于当前节   点，则到左子树中 寻找，如果左子树为空则当前节点为要找的父节点，新节点插入到当前节点的左子树即可；如果大于当前节点，则到右子树中寻找，如果右子树为空则当前节点为要找的父节点，新节点插入到当前节点的右子树即可。   ps:如果插入的元素已经存在，也就是重复元素，那么是不会重复插入的，因为违背了排序二叉树的原则。
    删除操作：    
                                           
        查询操作：   查找操作的主要流程为：先和根节点比较，如果相同就返回， 如果小于根节点则到左子树中归查找，如果大于根节点则到右子树中递归查找。因此在排序二叉树中可以很容易获取最大（最右最深子节点）和最小（最左最深子节点）值。

7. 二叉排序树的介绍

二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。

8. 构造一个二叉排序树

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