请教两个数据结构的问题。求大神 给出答案和解释~ 同时也希望能找到一起学习的伙伴~

He2toN

1.一棵BST存放的数据分别为A B C D E F G ，以下（）不是查找序列。
A . A B C D E F G     B. G F E D
C. D B C F   D.  D G E F
2.100个结点的AVL树最高为（）层。（根是第一层）
A.9 B 10
C.11 D.12

jun

补充：
第一题：因为C选项中的查找DBCF  ,即D为根，然后到B为D的左子树的根，然后再到B的右子树C，而F为比D大不可能出现在D的左子树（即B为根的左子树）中

第二题：设AVL树的最高层为N,则N-2层必定为满的，那么由2^(10-2)<100<2^(10-2+1)(即2的（10-2+1）次方)；得出N为10，故选B

jun

个人觉得第一题选：C  ,第二题选：B

He2toN

jun 发表于 2012-10-5 22:30

                               
登录/注册后可看大图

补充：
第一题：因为C选项中的查找DBCF  ,即D为根，然后到B为D的左子树的根，然后再到B的右子树C，而F为比 ...

第二个题书上的答案是A。 我百度了一下是这么说的  当节点数为N 时，高度h 最多为logN + 2。 但是原因我现在还是没完全明白。 大神可以留下QQ方便交流吗？

jun

He2toN 发表于 2012-10-6 20:40

                               
登录/注册后可看大图

第二个题书上的答案是A。 我百度了一下是这么说的  当节点数为N 时，高度h 最多为logN + 2。 但是原因我现 ...

我写的那个答案是当时二逼了一下，所以算错了，不过方法没错: 我当时写的是2^(10-2)(即2的8次方)<100<2^(10-2+1)(即2的9次方)，应该是2^(8-2)==64<100<2^(8-2+1)==128，所以呢，h==8，这个是从根从第0层开始算起的，而你的根是从第1层算起的所以你的是9层呗，QQ群：55439369

补充内容 (2012-10-7 12:58):
维基百科的解析你看看吧：http://zh.wikipedia.org/wiki/AVL%E6%A0%91