一道经典的数据结构（面试）题目

数据结构：
以下有个2叉树：
                     15
                 .
               9         23
                   11              (点代表连接符)

1， 请把以下几个号码插进上面的二叉树中：4，12，25，31然后划出加了新号码的二叉树形状。
2， 请把新的二叉树里的号码，按顺序在二叉树上以指针和箭头划出你走过的路线：
a.从小到大的循环 b.从大到小的循环
3，从新的二叉树抽掉9号，然后再划出新的二叉树的形状：
4，对二叉树的复杂性的分析（请用0()的公式）：（这里只需要写答案，但如果能用数学推论的方式，写出如何从二叉树倒O（）结论的步骤加20分）
4a.在二叉树里寻找一个新号码复杂性（经过多少次计算），请写出最好的，最坏的和平均值。
4b.在二叉树里插入一个新号码的复杂性，请写出最好的，最坏的和平均值。
4c.在二叉树里抽掉一个号码的复杂性，请写出最好的，最坏和平均值。
5，请列出你学过的和经常用的数据结构的名称：

这是本人遇到的一个面试题  前三道好答，第4道不会，不知道是否有固定的公式 大家一起来和我研究下

我承认我没看懂题目。。。

题目中的二叉树应该改成 二叉查找树。

题目中的二叉树应该改成 二叉查找树。

不错，合格的程序员应该能回答个89不离十。
数据结构很重要。

晕得慌

看来大家都对这块不是很熟悉了

B*树，树的父节点比他的子节点大
左边子节点比右边子节点小

这样主要是为了实现二分查找，使用树的后序遍历就能得到一个升序的序列
数据库里的索引就是这么设计的，后面插入数据，按照规则加就可以了

重要的是平衡索引的算法比较麻烦

B树-B*，B+树，都是二叉查找（或是搜索）树的自然推广，也有red-black树的思想，都是多叉树，比这个题目复杂了去了。

1.
             15
         9         23
      4     11         25
               12          31
2.
   a. 15->9->4->12->23->25->31
   b. 15->23->25->31->9->12->4

3.          
                  15
            11       23
          4    12       25
                             31
4.
    a. 查找已存在数据，并且等概率下
        最好：该树平衡，属完全二叉树：2^0/n+2^1/n+2^2/n+2^3/n+……
        最坏：退化为线性结构 ：1/n+2/n+3/n+4/n+……+1