방통대 자료구조 10강 이진 트리 개수

 

 

1.스택으로 상이한 이진 트리의 수를 구할 수 있는 이유

중위 순회는 왼쪽 서브트리 -> 부모 노드 -> 오른쪽 서브 트리 순으로 방문을 하는데, 스택은 가장 먼저 삽입된 자료를 가장 먼저 가져오므로 스택에서 push()는 빈 노드를 만들고 왼쪽 서브 트리를 가리키는 것을 의미한다.

또한 스택에서 pop()을 통해 top에 있는 자료를 꺼내는 것으로 부모 노드 방문을 나타낸다. 이때 pop() 이후로 push()한 자료는 부모 노드보다 나중에 방문해야 하므로 오른쪽 서브 트리를 가리킨다.

 

2.스택을 수열로

스택을 통해 상이한 이진 트리가 표현가능함을 알았다. 상이한 이진 트리는 결국 push()와 pop()의 조합으로 표현이 가능한데 이때 push()를 A, pop()을 B라 하자 그리고 스택에 특성 때문에 B는 앞서 등장한 A보다 많을 수 없다.(빈 스택을 팝하는건 불가하니까)

 

따라서 노드가 n개인 이진트리는 2n개 길이의 A와 B 문자열로 표현 가능하다.(노드의 개수 n개만큼 push()하고 또 n개만큼 pop()해야 하므로 2n)

 

ex) 노드가 3개인 경우

AAABBB = push(1) push(2) push(3) pop() pop() pop()

전위 순회 1 2 3, 중위 순회 3 2 1 (이진트리 : 1(부모) 2, 3(왼쪽 서브 트리), 2(부모), 3(왼쪽 서브  트리)

 

이때 노드가 n개일 때 가능한 push(), pop() 경우의 수를 구하는건 카탈란 수의 경우와 같으므로 아래 공식이 사용 가능

 

 

 

참고

카탈란 수(Catalan number) : 네이버 블로그 (naver.com)

카탈란 수(Catalan number)