C++에서 주어진 Inorder 및 Preorder 순회로부터 트리 생성

이진 트리의 Inorder 및 Preorder 순회가 제공됩니다. 목표는 주어진 순회에서 트리를 구성하는 것입니다.

순차 순회 − 이러한 유형의 트리 탐색에서는 왼쪽 하위 트리를 먼저 방문한 다음 노드와 오른쪽 하위 트리를 마지막으로 방문합니다.

순차(트리 루트)

• 루트가 가리키는 노드의 왼쪽 하위 트리를 탐색하고 inorder( root→left )

  를 호출합니다.

• 루트 방문

• 루트가 가리키는 노드의 오른쪽 하위 트리를 탐색하고 inorder( root→right )

  를 호출합니다.

선주문 순회 − 이러한 유형의 트리 탐색에서는 노드가 먼저 방문하고 왼쪽 하위 트리와 오른쪽 하위 트리가 마지막으로 방문합니다.

선주문(트리 루트)

• 루트 방문
• 루트가 가리키는 노드의 왼쪽 하위 트리 탐색, inorder 호출( root→left )
• 루트가 가리키는 노드의 오른쪽 하위 트리 탐색, inorder 호출( root→right )

아래 트리의 inorder 및 preorder 순회는 다음과 같습니다. -

순서

2-3-4-5-6-8-10

선주문

4-3-2-5-8-6-10

이제 우리는 주어진 preorder와 inorder traversals에 대해 위의 트리를 다시 구성할 것입니다.

순서

2-3-4-5-6-8-10

선주문

5-3-2-4-8-6-10

• 사전 주문이 루트 노드를 먼저 방문하고 첫 번째 값은 항상 트리의 루트를 나타냅니다. 위의 시퀀스 5에서 트리의 루트입니다.

선주문

5 -3-2-4-8-6-10

• 위의 inorder traversal에서 우리는 노드의 왼쪽 하위 트리가 오른쪽 하위 트리가 뒤따르기 전에 탐색된다는 것을 알고 있습니다. 따라서 순서대로 5의 왼쪽에 있는 모든 값은 왼쪽 하위 트리에 속하고 오른쪽에 있는 모든 값은 오른쪽 하위 트리에 속합니다.

순서

2-3-4 ← 5 → 6-8-10

• 이제 왼쪽 하위 트리에 대해 위와 동일한 작업을 수행합니다.

왼쪽 하위 트리의 선주문 순회는 3 -2-4입니다. 따라서 3이 루트가 됩니다.

중위 순회는 2 ← 3 → 4

• 이제 오른쪽 하위 트리에 대해 위와 동일한 작업을 수행합니다.

오른쪽 하위 트리의 선주문 순회는 8 -6-10입니다. 따라서 8이 근이 됩니다.

중위 순회는 6 ← 8 → 10

그래서, 이런 식으로 우리는 주어진 preorder와 inorder traversals로부터 원래의 트리를 구성했습니다.