선주문, 주문 및 주문서 순회

Question

선주문 : ABAB, 주문 주문 : BABA, 주문 중 : AABB 주문 전 선적 주문과 주문 후 선적, 특히 이 혼란 스럽습니다. .

루트가 Pre와 Post의 첫 번째 요소와 마지막 요소라는 것을 알고 있지만 바이너리 트리 생성을 완료하는 방법을 이해하지 못했습니다.

Answer 1

귀하의 게시물은 모호하며별로 의미가 없지만, 사전, 사후 주문 및 2 진 트리 구성에 대해 설명하겠습니다.

질문에 이해가되지 않는 이유 중 하나는 주문에서 설명하는 요소에 순서를 설정하지 않았다는 것입니다. ABAB BABA와 AABB는 각 요소의 위치를 ​​올바르게 표시하는 트리가없는 것을 의미합니다 (각 요소는 하나의 문자입니까? 왜 중복됩니까?)

질문이 의미가없는 또 다른 이유는 pre, pos 및 order가 이진 트리를 만드는 것과 관련이 있다고 생각하는 것입니다. 하지마.

Pre ordering, In Ordering 및 Post Ordering는 tree traversalDepth First Search위한 알고리즘의 모든 유형이다. 즉, 나무를 탐색하지 않고 탐색하는 방법입니다. 이 알고리즘을 사용하여 요소를 찾거나 트리의 모든 내용을 간단히 인쇄 할 수 있습니다.이 노드는 노드가 pointers (예 : array based binary heap)과 연결된 경우에만 유용합니다.

는 다음과 같은 이진 트리 (모든 예제에 대해 동일)

 A 
    B C 
    D E F G 

사전 주문 탐색이 항상 먼저 가장 왼쪽 길을 갈 수 트리 탐색 알고리즘의 유형을 상상해보십시오. 더 이상 갈 수 없을 때, 다음으로 가장 왼쪽 경로를 취하고 다음 노드에서 같은 작업을 반복적으로 수행합니다. 위의 예제 트리에서 선주문 탐색은 루트에서 시작하고 (A) 왼쪽으로 (A, B) 다시 왼쪽으로 (D)가 왼쪽으로 갈 수 없으므로 오른쪽으로 이동하고 (E) 결국에는 A B D E C F G

트래 버설은 선주문 순회와 비슷하지만 각 단계마다 표시하는 대신 탐색 가능한 가장 깊은 왼쪽으로 이동 한 다음 표시 할 수 있습니다. 더 이상 깊이 갈 수 없으며, 다시 올라가서 (따라서 '순서대로') 표시하고, 완료 될 때까지 같은 것을 다시 반복적으로 시도합니다. 트리 예제에서 우리는 실제로 D를 먼저 인쇄하고 B로 돌아가서 B를 인쇄 한 다음 E를 기록한 다음 A로 다시 인쇄하므로 최종 출력은 D B E A F G C이됩니다. 참고 위키 피 디아 예제는 더 복잡하므로 더 이해할 수 있습니다.

포스트에서, 우리는 기본적으로 아래쪽부터 인쇄합니다. 가장 왼쪽 노드에있는 가장 깊은 노드를 찾고, 끝날 때까지 재귀 적으로 가장 깊은 노드를 인쇄합니다. 오른쪽 하위 트리로 이동하여 마지막으로 루트를 인쇄합니다. 예 : : D E B F G C A. 이 예제는 위키 백과에서 더 복잡한 나무가 있기 때문에 더 이해하기 쉽습니다.

트리를 구성하려는 경우 다양한 방법이 있지만 원하는 정렬 구조의 종류에 따라 다릅니다. 바이너리 구조 또는 n- 구조 구조를 원하십니까? 어떤 요소가 맨 위에 있는지 신경 쓰냐, 아니면 최소/최대 (pairing heap 또는 바이너리 힙 priority queue) 만 원합니까? 나무의 각 부분의 뿌리가 자녀 또는 부모와 관련하여 더 크거나 작거나/다른 조건이어야하는 것과 같은 검색 조건이 있습니까?(예 : binary search tree)

This post도 충분하지 않은 경우 트래 버설을 설명하는 것이 좋으며, 올바른 연결을 사용하여 노드 시퀀스에서 트리를 구성하기 위해 여러 가지 유형의 순서가 필요한 이유를 설명합니다 (원래 의도는 이진 트리 구조를 복사하는 것이 었습니다)