Inorder와 Preorder/postorder traversals를 모두 사용하지 않고 트리를 구성 할 수 없다는 것을 알고 있습니다. 주어진 (Inorder/Preorder/postorder 만) 나무가 더 많이 생길 수 있습니다. 주어진 알고리즘 (Inorder/Preorder/postorder traversal 만)으로부터 고유 트리의 수를 계산할 수있는 알고리즘이나 메커니즘이 있습니까?Inorder/Preorder/Postorder traversal에서 Tree를 생성 할 수 없습니다.
Eg : a b c d e f g this is my Inorder traversal.
주어진 Inorder 순회로 구성 할 수있는 고유 한 트리의 수입니다.
내가 그들을 시도는 구글이지만 설명의 어떤 것도 명확하지
어떤 도움을 주시면 감사하겠습니다...
음 알고리즘은 다음과 같다 :
하자, P(N)이의 수를 나타냅니다 N 노드로 가능한 트리. 노드의 인덱스를 1,2,3,...
으로 변경하십시오. 이제 트리의 루트를 선택할 수 있습니다. 주어진 N 노드 중 하나가 루트가 될 수 있습니다. 노드 i이 루트로 선택되었습니다. 그런 다음 inorder 시퀀스의 i 왼쪽에있는 모든 요소는 left sub-tree에 있어야합니다. 마찬가지로, 오른쪽으로.
그래서, 총 가능성은 : P(i-1)*P(N-i)
i1 to N가 다르다 상기 식에서.
따라서 우리가
,P(N) = P(0)*P(N-1) + P(1)*P(N-2) + P(2)*P(N-3)....
베이스 케이스됩니다
P(0) = 1
P(1) = 1
Dynamic Programming을 사용하여 해결 될 수있다.
특정 트래버 설은 트리의 노드에 레이블을 지정하는 방법 일 뿐이므로 동일한 길이의 임의의 두 탐색에 대해 가능한 이진 트리의 수가 동일하다는 점에 유의하십시오. 노드가 n 인 이진 트리의 수는 n-1 st Catalan number입니다.