6
inorder 및 preorder 순회가 문자열로 주어 졌을 때 이진 트리를 재구성 할 수 있지만 가능한 경우에만 후행 및/또는 전치 트래버 설을 찾을 수 있음을 알고 있습니다. inorder traversal이 주어진다면?하나의 순회 만 주어진 경우 이진 트리의 다른 두 순회 찾기
A
답변
3
아니요, 인 오더 트래버 설에서만 가져온 엽서/예약 상품은 검색 할 수 없습니다. 그렇다면 inorder 순회만으로 이진 트리를 재구성하는 것이 가능합니다. 하나의 순회 순회가 여러 가지 가능한 재구성 된 이진 트리를 제공 할 수 있기 때문에 불가능합니다.
1
입력 내용은 어떻게 보이고 트리의 목적은 무엇입니까?
완전한 괄호 안에 순서가 지정된 표현식이있는 경우 유니크 트리가 있고 트리를 구성한 다음 트리에서 사전 및 사후 주문 용어를 구성하여 사전 및 사후 순서를 얻습니다.
표현식이 완전히 괄호로 묶이지 않은 경우 사용자의 순서와 일치하는 다른 트리간에 차이가 없다는 것을 나타냅니다. 예 : 산술 표현을 나타내는 트리 인 경우 x+y+z은 (x+y)+z 및 x+(y+z)과 같습니다. 그러나 이는 사용하는 사전 주문 또는 후원 주문에 상관없이 ++xyz과 +x+yz이 동일하다는 것을 의미합니다.
이제는 별 문제가되지 않는다면, 주문에 대한 몇 가지 가능성있는 표현에 대해 걱정할 필요가 없습니다. 표현 중 하나를 선택하고이 트리로 유도 된 전후 순서를 계산하십시오.
"inorder"순회 만 받으면 많은 다른 이진 트리를 구성 할 수 있습니다. 즉, "inorder"만 사용하여 "고유 한"트리를 설명 할 수 없습니다. – Aziz