依次输入如下序列3，37，100，45，12，53，24，61，90，构造一棵二叉排序树，画出该树的结构图。

1. 依次输入如下序列3，37，100，45，12，53，24，61，90，构造一棵二叉排序树，画出该树的结构图。

结构图： 37
          /       \
       24        53
     /    \        /     \
  3       37   45  90                           
                        /      \
                     61        100
主要是要进行扭转操作，即当左右子树深度相差2的时候，则判断其失衡，需要进行旋转操作，使其恢复平衡

2. 假设二叉树的每个结点值为单个字符,采用顺序存储结构存储,设计一个算法,求二叉树叶子结点个数 （谢）

如图

3. 依次输入序列(23,15,9,17,26,18,24),请构造一个二叉排序树,并画出构造过程

1、23为根结点
2、15<23,所以15为23左孩子
3、9<23,9<15,9为15的左孩子
4、1715，17为15的右孩子
5、26>23,26为23的右孩子
6、1815,18>17,18为17的右孩子
7、24>23,24<26,24为26的左孩子
二叉排序树如下图
                                23
                         /             \
                       15            26
                    /        \      /      
                   9       17   24
                                \
                                18

4. 依次输入元素：10，8，16，5，20，7，12，19，试生成一棵二叉排序树。(1) 画出建立的二叉排序树

你是要算法还是本题答案？
本题答案为
               10
      8                   16
  5                  12         20
      7                       19
算法为：
步骤：若根结点的关键字值等于查找的关键字，成功。
否则，若小于根结点的关键字值，递归查左子树。
若大于根结点的关键字值，递归查右子树。
若子树为空，查找不成功。
平均情况分析（在成功查找两种的情况下）
在一般情况下，设 P（n，i）且它的左子树的结点个数为 i 时的平均查找长度。如图的结点个数为 n = 6 且 i = 3; 则 P（n,i）= P（6, 3） = [ 1+ ( P(3) + 1) * 3 + ( P(2) + 1) * 2 ] / 6
= [ 1+ ( 5/3 + 1) * 3 + ( 3/2 + 1) * 2 ] / 6
注意：这里 P(3)、P(2) 是具有 3 个结点、2 个结点的二叉分类树的平均查找长度。 在一般情况，P（i）为具有 i 个结点二叉分类树的平均查找长度。 P(3) = （1+2+2）/ 3 = 5/3
P(2) = （1+2）/ 2 = 3/2
∴ P（n,i）= [ 1+ ( P(i) + 1) * i + ( P(n-i-1) + 1) * (n-i-1) ] / n
n

二叉树
-1
∴ P（n）= ∑ P（n,i）/ n <= 2(1+I/n)lnn
i=0
因为 2(1+I/n)lnn≈1.38logn 故P(n)=O(logn)

5. 依次输入元素：10，8，16，5，20，7，12，19，试生成一棵二叉排序树。(1) 画出建立的二叉排序树

只需记住：第一个元素是根，以后所有的都和这个根做比较，小的在左，大的在右。如果位子上有元素占住了，就和这个占住位置的元素比大小，小的在左，大的在右。如此循环就ok了。
以题目为例：
1、根30
2、插入15，比30小，所以在左子叶
------------30-------
-----------/----\------
---------15-----------
3、插入28，比30小，所以在左子叶，但左子叶已有元素15了，那就继续和15比，比15大，长在其右子叶：
------------30-------
-----------/----\------
---------15----------
-------/----\----------
------------28-------
4、插入20，如第三步所属，比30小，比15大，比28小，所以是28
的左子叶
------------30-------
-----------/----\------
---------15----------
-------/----\...
------------30-------
-----------/，长在其右子叶、插入20。
以题目为例，但左子叶已有元素15了只需记住;-------
---------20-----------
5;---\、重复以上过程一直到最后。如此循环就ok了，就和这个占住位置的元素比大小;----\，比30小，比28小、根30
2;----------
------------28-------
4：第一个元素是根，那就继续和15比，比15大，比30小，所以在左子叶;----\，小的在左、插入15，所以是28
的左子叶
------------30-------
-----------/，大的在右，所以在左子叶
------------30-------
-----------/----\、插入28，比30小。如果位子上有元素占住了，以后所有的都和这个根做比较;----\------
---------15----------
-------/，比15大;----\：
1，小的在左;------
---------15-----------
3，如第三步所属;------
---------15----------
-------/，大的在右。;----------
------------28-------
-----------/。

6. 数据结构 一棵含有10个结点的完全二叉树，按照从上到下，从左到右的顺序依次编号，则编号为3的结点的

你好！
1，根据完全二叉树规律即可判断2*3<10，则左孩子编号为2*3=6
2，双亲节点的求法为a=（log3），底数默认为2，取不大于a的最大值，则双亲节点的编号为1,
纯手打，望采纳，谢谢！

7. 以{45,53,12,37,24,100,3,61,90,78}构造二叉排序树。

【摘要】
以{45,53,12,37,24,100,3,61,90,78}构造二叉排序树。【提问】
【回答】
对（278,109,63,930, 589,184,505,269,8,83）用基数排序方法进行排序，写出每一趟排序过程。【提问】
对（278,109,63,930, 589,184,505,269,8,83）用基数排序方法进行排序，写出每一趟排序过程。【提问】
【回答】

8. 用序列37,69,31,33,53,29建立一个二叉排序树。

二叉排序树为：
         37
      /       \
  31        69
  /  \         /
29   33  53
平均查找长度：(1+2*2 + 3*3 ) / 6 = 2.33
另外，形态均匀的排序树平均查找长度为log2N