n 노드를 가진 가능한 모든 이진 탐색 트리를 나열하는 방법은 무엇입니까?

Question

가능한 모든 이진 검색 트리를 나열하고 싶습니다. 나는 그 숫자가 카탈로니아의 숫자라는 것을 안다. 그러나 나는 또한 그들을리스트하고 싶다.

의이

아래와 같이 나는 다음 N 노드에있는 모든 나무를 나열 할 이진 검색 트리의 각 위치에 문자를 할당한다고 가정 해 봅시다. N이 1 인 경우 n이 2이면, 유일하게 가능한 트리는 가능한 나무 가능한 나무가

A B 
A C 

N이 3 인 경우이다

A 

이다

A B D 
A B E 
A B C 
A C F 
A C G 

N이 4 인 경우 가능한 나무는 다음과 같습니다.

A B D H 
A B D I 
... should be 12 more 

Do 누구든지 가능한 모든 나무를 나열하는 좋은 알고리즘을 알고 있습니까?

Answer 1

간단한 (순진한) 접근법은 재귀로 구성됩니다. n 개의 노드가있는 2 진 트리는 루트이고, k<n 개의 노드와 n-1-k 노드가있는 다른 2 진 트리가있는 2 진 트리입니다.

내 접근 방식에 해당하는 파이썬 코드입니다. 필요한 경우 출력을 쉽게 정렬 할 수 있습니다.

def binary_trees(n, i=0): 
    if not n: 
     return [[]] 
    else: 
     ll=[] 
     for k in range(n): 
      l1 = binary_trees(k, 2*i+1) 
      l2 = binary_trees(n-1-k, 2*i+2) 
      for j in l1: 
       for l in l2: 
        ll.append([i]+j+l) 
     return ll 

def numbers_to_letters(l): 
    return [chr(i+ord('A')) for i in l] 

print [numbers_to_letters(l) for l in binary_trees(4)] 

개선점은 아마 DP 통해 수행 할 수 있습니다 : 다음 크기 1, 2, 다음 3의 나무를 계산 ... 그리고 매번 사람들을 다시 계산하는 대신 재사용을 위해 메모리에 보관하십시오.