2012-10-14 8 views
8

내가 어느 한 통과 (pre, post 또는 in-order), 또는 이들의 둘의 조합에서 Binary Search Tree 구축에 관한 다른 사이트에서 기사의 숫자에 의해 매우 혼란 오전 BST를 구성하는 것으로 알려져해야 . 예를 들어 this 페이지에서 in-order 탐색과 ​​함께 pre, post 또는 level 순회 순서를 사용하면 BST을 생성 할 수 있습니다. 그러나 herethere은 에서 BST을 구성하는 것으로 나타납니다. 또한 hereBST을 구성하는 방법을 보여줍니다. prepost-order 탐색이 제공됩니다. 다른 사이트에서 나는 트래버스에서만 BST을 구성하는 솔루션을 발견했습니다.얼마나 많은 순회은

이제는 inorderpre-order 탐색이 주어진다면 BST을 고유하게 형성 할 수 있다는 것을 알고 있습니다. 우리가 제공 한 첫 번째 링크에 대해서는 과 post-order에서 BST을 만들 수 없다고 말하지만 post-order 배열을 정렬하여 해당 inorder을 얻은 다음 해당 배열과 pre-order 배열을 사용하여 BST? 그것은 4 번째 링크의 솔루션과 동일 할 것인가, 아니면 다른 것입니까? 그리고 pre-order 만 주어진다면, 나는 in-order을 얻고, pre-order을 사용하여 BST을 얻을 수 있습니다. 다시 말하지만, 링크 2와 3의 솔루션과 다르게해야합니까?

구체적으로 BST을 고유하게 생성하려면 충분합니까? 고유화가 필요하지 않으면 간단히 정렬하여 in-order 트래 버럴을 얻고 N에서 BST 중 하나를 재귀 적으로 작성합니다.

답변

13

BST를 구성하려면 순회는 하나만 필요합니다.

일반적으로 이진 트리를 만들려면 예를 들어 순서와 선주문을 두 번 필요합니다. 그러나 BST의 특별한 경우 - 순서 탐색은 항상 요소가 포함 된 정렬 된 배열이므로 항상 미리 구성하고 알고리즘을 사용하여 선주문 및 순차 탐색에서 일반 트리를 재구성합니다.

따라서 트리가 BST 인 정보와 그 안에있는 요소 (순서가 지정되지 않은)는 순서 순회와 동일합니다.

보너스 : 일반 나무에 대해서는 하나의 순회가 충분하지 않은 이유는 무엇입니까 (BST라는 정보없이).
Answer : n 개의 별개 요소가 있다고 가정 해 봅시다. 이 요소에 대해 n! 개의 가능한 목록이 있지만 가능한 트리 수가 훨씬 큽니다 (2 * n! n 요소의 가능한 트리는 모든 노드에서 모두 node.right = null과 같은 모든 부식 된 트리이므로 트리가 실제로 목록입니다) 이 같은 나무는 n!이고 또 다른 n! 나무는 언제나 node.left = null입니다. 따라서 비둘기 구멍 원칙에서 - 2 개의 나무를 생성하는 목록이 하나 이상 있으므로 단일 탐색에서 나무를 재구성 할 수 없습니다. (QED)

+0

따라서 두 번째 및 세 번째 링크의 솔루션이 유일하게 가능한 'BST'를 생성합니까? – SexyBeast

+0

@Cupidvogel : 나는 그 코드를 따르지 않았다. 그러나 그것이 맞다면 그렇다. 선주문 순회마다 BST가 하나만 있습니다. – amit

+0

다음 기사를 참조하십시오 : http://www.geeksforgeeks.org/archives/6633. 그들은'pre'와'in-order' 순회로부터'BST'를 구성합니다. 그러나 트리가 '선주문'만으로 구성 될 수 있다는 점을 감안할 때이 코드에서 위치를 찾기 위해 필요한 이진 검색이 효율성을 떨어 뜨리게한다고 생각하지 않습니까? 'inorder'를 전혀 사용하지 않는 것이 효율적이지 않고 트리를 구성하기 위해'선주문 (pre-order) '을 사용하기 만합니까? 그러나 두 솔루션이 반드시 동일한 트리를 산출합니까? – SexyBeast

0

BST의 노드 값이 지정된 경우 나머지 데이터는 노드 값에 의해 제공되기 때문에 하나의 순회만으로 충분합니다.그러나 값을 알 수없는 경우 내 이해에 따라 단일 탐색에서 고유 BST를 생성하는 것은 불가능합니다. 그러나, 나는 제안에 개방적이다.