내가 어느 한 통과 (pre
, post
또는 in-order
), 또는 이들의 둘의 조합에서 Binary Search Tree
구축에 관한 다른 사이트에서 기사의 숫자에 의해 매우 혼란 오전 BST를 구성하는 것으로 알려져해야 . 예를 들어 this 페이지에서 in-order
탐색과 함께 pre
, post
또는 level
순회 순서를 사용하면 BST
을 생성 할 수 있습니다. 그러나 here과 there은 에서 BST
을 구성하는 것으로 나타납니다. 또한 here은 BST
을 구성하는 방법을 보여줍니다. pre
및 post-order
탐색이 제공됩니다. 다른 사이트에서 나는 트래버스에서만 BST
을 구성하는 솔루션을 발견했습니다.얼마나 많은 순회은
이제는 inorder
및 pre-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
중 하나를 재귀 적으로 작성합니다.
따라서 두 번째 및 세 번째 링크의 솔루션이 유일하게 가능한 'BST'를 생성합니까? – SexyBeast
@Cupidvogel : 나는 그 코드를 따르지 않았다. 그러나 그것이 맞다면 그렇다. 선주문 순회마다 BST가 하나만 있습니다. – amit
다음 기사를 참조하십시오 : http://www.geeksforgeeks.org/archives/6633. 그들은'pre'와'in-order' 순회로부터'BST'를 구성합니다. 그러나 트리가 '선주문'만으로 구성 될 수 있다는 점을 감안할 때이 코드에서 위치를 찾기 위해 필요한 이진 검색이 효율성을 떨어 뜨리게한다고 생각하지 않습니까? 'inorder'를 전혀 사용하지 않는 것이 효율적이지 않고 트리를 구성하기 위해'선주문 (pre-order) '을 사용하기 만합니까? 그러나 두 솔루션이 반드시 동일한 트리를 산출합니까? – SexyBeast