开发者

3-element binary search trees

I'm working through a past exam paper for my advanced programming course and I've gotten stuck at this question

What property must the values in a binary search tree satisfy? How many different binary search trees are there containing the three values 1 2 3? Explain your answer.

开发者_高级运维

I can answer the first part easily enough but the second bit, about the number of possible trees has me stumped. My first instinct is to say that there is only a single tree possible, with 2 as the root because the definition says so, but this question is work 8 marks out of a total of 100 for the entire paper, so I can only assume that it's a trick question, and there's a more subtle explanation, but there's nothing in the lecture notes that explains this. Does anyone know who to answer this question?


The question doesn't say that the tree is balanced, so think about whether 1 or 3 can be at the root node.


Try to think about all possible binary trees with these three nodes. How many of those trees fulfill the property of binary search tree?


I think that a trick is that a tree can be a degenerate one (effectively, a linked list of elements):

1
 \
  2
   \
    3

And variations thereof.

Also, are these trees considered to be identical ?

  2        2
 / \      / \
3   1    1   3


If I remember correctly, the root of the tree does not have to be the "middle element". Thus there are a few more combinations of trees:

    2
1        3
or
1
    2
        3
or
1    
        3
    2
or
        3
    2
1
or
        3
1
    2

Maybe I forget a few, but I think you'll get the idea. Just for my notation: Newline meets get down in the tree, right and left of the upperline showes whether it is right or left of its parent node ;)

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜