자료구조 시험문제인데 이거 답 뭔지 암?

[ㅇㅇㅇ(121.171)]

이거 빼고 다 풀었는데, 진짜 이건 도통 답이 뭔지 모르겠음.

 

<!--StartFragment-->

노드가 4개인 Binary Tree(이진 트리)에서 전위 순회 경로(Prefix 표현)가 {2, 1, 4, 5}가 되는 모든 가능한 트리 모양의 개수는? 트리를 직접 그릴 필요 없으며, 답에 대한 근거를 제시하시오.

[ddd(121.171)]

답 안나오는 거 보니 컴갤러들 의외로 멍청하네. 나도 가능성 있는듯.

[ㅊㄹ(1.252)]

근거로 다 그려버리면 점수 안 주겠지? ....

[ddd(121.171)]

해결이 안되니 손이 부들부들 떨림.

[아놔콘다(anwaconda)]

2개의 노드 a.b에 대해서 전위순서 [ab]를 만들 수 있는 트리는 2개 pre(2) = 2 라고 점화식 하나 만듬. 이번엔 3개의 노드에 대해서 전위식 [abc]를 만들 수인는 경우 pre(3) = pre(2) + pre(1) + pre(2) 가 됨.

[아놔콘다(anwaconda)]

노드 4개 abcd 인 경우 pre(4) = pre(3) + pre(2) + pre(2) + pre(3) 과같이.... a가 루트인경우 5가지, b가 루트인경우 2가지, c가 루트인 경우 2가지, d가 루트인 경우 5가지.... 카탈랑수..

[아놔콘다(anwaconda)]

아.. pre(1)부터 점화식 해야 하는구나... pre(1) =1, pre(2) = pre(1) + pre(1) = 2 .. 요러케...