예제가 포함된 트리 순회(중위, 사전 순서 및 사후 순서)

작성자 : 사라 첸 사라 첸
Hours 업데이트

트리 순회란 무엇입니까?

트리 데이터 구조에서 순회는 특정 방식으로 노드를 방문하는 것을 의미합니다. 노드2가지 유형의 순회가 있습니다. 일반적으로 이러한 종류의 순회는 이진 트리를 기반으로 합니다. 이진 트리는 각 노드가 최대 2개의 노드를 가질 수 있음을 의미합니다.

이진 트리는 잘 알려진 데이터 구조입니다. BST(이진 검색 트리)도 있습니다. 이러한 유형의 순회는 다양한 목적으로 사용됩니다. 레벨 순서 탐색은 두 노드 사이의 깊이를 계산하는 데 사용됩니다. 노드의 높이를 계산하는 데 필요한 "AVL"이라는 또 다른 종류의 트리가 있습니다. 배열에서 이진 트리를 나타낼 수 있지만 메모리 최적화를 위해 다음 노드를 참조하기 위해 구조와 포인터를 사용합니다.

트리 순회 유형

우리가 논의한 것처럼 이진 트리이제 개별 유형의 순회에 대해 논의합니다. 유형에 따라 두 가지 유형의 순회가 있습니다. 이전에 우리는 레벨 순서 또는 너비 우선 탐색의 필요성을 언급했습니다. 지금 깊이 우선 순회 예를 들어, 포스트 순서는 노드를 삭제할 때 사용되고(나중에 설명하겠습니다), 전위 순서는 이진 트리를 복사할 때 사용되고, "중위 순서"는 감소하지 않는 방식으로 트리를 탐색합니다.

  • 폭 우선 순회
  • 깊이 우선 순회
  • 선주문 순회
  • 사후 순회
  • 순회 순회

폭 우선 순회

레벨 순서 순회라고도 합니다. 레벨 순서 순회를 보여주기 위해 다음 트리를 고려해 보겠습니다.

폭 우선 순회

따라서 루트 노드 "1"부터 시작하겠습니다. 레벨 1로 표시됩니다. 그런 다음 알고리즘은 현재 노드의 모든 하위 항목으로 이동합니다. 이제 노드 2와 3을 방문하겠습니다. 레벨 2로 표시됩니다.

그 후에는 레벨 2에 2개의 노드가 있으므로 해당 노드의 자식도 방문합니다. 따라서 우리는 5,6,8,7을 방문하여 레벨 3으로 표시하겠습니다. 여기에 언급되지 않은 것이 있습니다.

노드 수준 = 상위 노드 수준 + 1

레벨 1 : 1

레벨 2: 2 3

레벨 3: 5 6 8 7

BFS에도 유사한 알고리즘이 사용됩니다(너비 우선 검색).

레벨 순서 탐색을 위한 의사 코드는 다음과 같습니다.

level_order(node)
Q → Queue()
Q.push(node)
while !Q.empty():
    current_node = Q.pop()
    print current_node.value
# Checking if the current node have any child or not
if current_node.left is not NULL:
    Q.push(current_node.left)
if current_node.right is not NULL:
    Q.push(current_node.right)

중위 순회 이안리 트리

이전과 같은 예를 들어보겠습니다. 이러한 유형의 순회에서는 먼저 왼쪽 하위 트리를 방문한 다음 루트, 그 다음 오른쪽 하위 트리를 방문합니다. 기억하기 쉽도록 순서는 왼쪽-루트-오른쪽과 같다고 말할 수 있습니다.

중위 순회 이안리 트리

전체 트리에 대해 루트가 1이라고 가정해 보겠습니다. 이제 알고리즘은 다음과 같습니다.

  • 노드 1의 왼쪽 하위 트리를 방문합니다.
  • 현재 노드는 2입니다(1의 왼쪽 하위 트리이므로).

중위 순회 이안리 트리

  • 2의 왼쪽 하위 트리를 방문합니다. 이번에는 현재 노드가 5가 됩니다.
  • 5로 이동하면 자식이 없으므로 노드 5는 방문한 것으로 표시됩니다. 상위 노드로 돌아갑니다. 2입니다.
  • 2의 왼쪽 하위 트리를 방문했으므로 이제 2도 방문하게 됩니다.
  • 이 어플리케이션에는 XNUMXµm 및 XNUMXµm 파장에서 최대 XNUMXW의 평균 출력을 제공하는 연산 현재 노드를 노드 2의 오른쪽 하위 트리인 노드 6으로 이동합니다. 노드 6을 방문한 후 상위 노드 2로 이동합니다.
  • 노드 2를 방문하면 이제 2의 부모를 방문합니다. 이는 노드 1입니다.
  • 그런 다음 오른쪽 하위 트리를 방문합니다.

따라서 최종 순회는 다음과 같습니다.

순서: 5 → 2 → 6 → 1 → 8 → 3 → 7

순차 순회를 위한 의사 코드는 다음과 같습니다.

InOrder(node):
  if node is not null:
    InOrder(node.left)
  print node.value
    InOrder(node.right)

이는 중위 순회를 위한 재귀 알고리즘입니다. 에 대한 이진 검색 트리(BST), 중위 순회는 정렬된 값 배열을 제공합니다.

관련 기사

사후 순회

이 순회에서는 가장 왼쪽 하위 트리를 먼저 순회한 다음 루트 다음으로 가장 오른쪽 하위 트리를 순회합니다. 모든 순회는 사후 순서로 이루어집니다. 예를 들어 보겠습니다.

사후 순회

여기서는 루트 = 1입니다.

  • 먼저 왼쪽 하위 트리로 이동하겠습니다. 그러면 루트는 2가 됩니다.
  • 그런 다음 2가 하위 트리를 떠났으므로 노드 5로 이동합니다. 이제 루트는 5입니다.
  • 왼쪽 하위 트리도 없고 오른쪽 하위 트리도 없습니다. 이제 노드 5를 방문한 것으로 표시하고 해당 상위 노드로 이동합니다.

사후 순회

  • 이제 루트는 2이고 왼쪽 하위 트리를 완전히 방문했습니다. 이제 오른쪽 하위 트리로 이동하겠습니다. 따라서 루트는 6이 됩니다.
  • 노드 6에는 왼쪽 및 오른쪽 하위 트리가 없으므로 노드 6을 방문한 것으로 표시하고 상위 노드 2로 이동합니다.
  • 이제 노드 2에 대해 왼쪽 및 오른쪽 하위 트리가 모두 방문됩니다. 이 노드도 방문한 것으로 표시됩니다.
  • 노드 2의 상위 노드인 노드 1로 이동하겠습니다.
  • 루트 1에 대해 왼쪽 하위 트리를 방문합니다. 이제 마찬가지로 오른쪽 하위 트리를 방문합니다.

사후 순회

표시된 원은 오른쪽 하위 트리입니다. 이제 왼쪽 하위 트리를 방문했던 것처럼 오른쪽 하위 트리도 방문하겠습니다. 그 후 노드를 방문하겠습니다. 따라서 최종 순회는 다음과 같습니다.

포스트 오더: 5 → 6 → 2 → 8 → 7 → 3 → 1

다음은 사후 순회를 위한 의사 코드입니다.

PostOrder(node):
    if node is not null:
       PostOrder(node.left)
       PostOrder(node.right)
       print node.value

순회 선주문

선주문 탐색의 경우 알고리즘은 루트 노드를 먼저 방문한 후 각각 왼쪽 및 오른쪽 하위 트리로 이동합니다. 이해를 돕기 위해 다음과 같은 선주문 순회 방문을 생각할 수 있습니다. 루트 → 왼쪽 오른쪽.

순회 선주문

따라서 노드 1을 루트로 선택해 보겠습니다.

  • 알고리즘에 따라 루트가 먼저 발견되고 그 다음 왼쪽, 오른쪽 하위 트리가 검색됩니다.
  • 따라서 루트 1을 방문하겠습니다. 그런 다음 왼쪽 하위 트리로 이동합니다. 루트는 2가 됩니다.
  • 노드 2를 방문하여 왼쪽 하위 트리로 이동합니다. 따라서 루트는 3이 됩니다.
  • 노드 3을 방문한 다음 상위 노드로 이동합니다. 이제 노드 2와 왼쪽 하위 트리를 방문합니다. 올바른 하위 트리를 방문할 시간입니다.
  • 오른쪽 하위 트리로 이동하면 루트는 4가 됩니다. 4를 방문하겠습니다. 4에는 하위 노드가 없으므로 상위로 이동합니다.
  • 이제 루트는 2이고 왼쪽 및 오른쪽 하위 트리와 함께 방문됩니다. 따라서 상위 노드로 이동하겠습니다. 이제 루트는 1이 됩니다.
  • 마찬가지로 오른쪽 하위 트리를 방문합니다.

예약주문 : 1개 → 2개 → 3개 → 4개 → 5개 → 6개 → 7개

다음은 사후 순회를 위한 의사 코드입니다.

PreOrder(node):
   if node is not null:
     print node.value
         PreOrder(node.left)
         PreOrder(node.right)

에서 구현 Python

class Node:
    def __init__(self, item):
    self.left = None
self.right = None
self.val = item
# creating a tree data structure
def inorder(root):
#checking if the root is null or not
if root:
    inorder(root.left)
# recursively calling left subtree
print(str(root.val) + " ", end = '')
inorder(root.right)
# recursively calling right subtree
def postorder(root):
    if root:
    postorder(root.left)
postorder(root.right)
print(str(root.val) + " ", end = '')
def preorder(root):
    if root:
    print(str(root.val) + " ", end = '')
preorder(root.left)
preorder(root.right)
def levelOrder(root):
    queue = list()
queue.append(root)
while len(queue) & gt;
0:
    current = queue[0]
queue = queue[1: ]
print(str(current.val) + " ", end = "")
if current.left:
    queue.append(current.left)
if current.right:
   queue.append(current.right)
root = Node(1)
root.left = Node(2)
root.right = Node(3)
root.left.left = Node(4)
root.left.right = Node(5)
root.right.left = Node(6)
root.right.right = Node(7)
print("\nLevelOrder traversal:\t", end = " ")
levelOrder(root)
print("\nInorder traversal:\t", end = " ")
inorder(root)
print("\nPreorder traversal:\t", end = " ")
preorder(root)
print("\nPostorder traversal:\t", end = " ")
postorder(root)

출력: 

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

C로 구현

#include <stdio.h>
#include <stdlib.h>
struct node {
   int value;
   struct node* left;
   struct node* right;
};
// Inorder traversal
void InOrder(struct node* root) {
   if (root == NULL) return;
   InOrder(root->left);
   printf("%d ", root->value);
   InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = malloc(sizeof(struct node));
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Inorder traversal:\t");
  InOrder(root);
  printf("\PreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

산출:

Inorder traversal: 4 2 5 1 6 3 7
Preorder traversal: 1 2 4 5 3 6 7
Postorder traversal: 4 5 2 6 7 3 1

구현 C++ (레벨 순서를 위해 std:queue 사용)

#include <stdio.h>
#include <stdlib.h>
#include<queue>
typedef struct node {
  int value;
  struct node* left;
  struct node* right;
}node;
// Inorder traversal
void InOrder(struct node* root) {
  if (root == NULL) return;
  InOrder(root->left);
  printf("%d ", root->value);
  InOrder(root->right);
}
// PreOrder traversal
void PreOrder(struct node* root) {
  if (root == NULL) return;
  printf("%d ", root->value);
  PreOrder(root->left);
  PreOrder(root->right);
}
// PostOrder traversal
void PostOrder(struct node* root) {
  if (root == NULL) return;
  PostOrder(root->left);
  PostOrder(root->right);
  printf("%d ", root->value);
}
void LevelOrder(struct node* root){
   std::queue<struct node*> Q;
   Q.push(root);
   while(!Q.empty()){
   struct node* current = Q.front();
   Q.pop();
   printf("%d ",current->value);
 if(current->left)
   Q.push(current->left);
 if(current->right)
   Q.push(current->right);
  }
}
// Create a new Node
struct node* createNode(int value) {
  struct node* newNode = new node();
  newNode->value = value;
  newNode->left = NULL;
  newNode->right = NULL;
  return newNode;
}
int main() {
  struct node* root = createNode(1);
  root->left = createNode(2);
  root->right = createNode(3);
  root->left->left = createNode(4);
  root->left->right = createNode(5);
  root->right->left = createNode(6);
  root->right->right = createNode(7);
  printf("Level Order traversal:\t");
  LevelOrder(root);
  printf("\nInorder traversal:\t");
  InOrder(root);
  printf("\nPreOrder traversal:\t");
  PreOrder(root);
  printf("\nPostOrder traversal:\t");
  PostOrder(root);
}

LevelOrder traversal:  1 2 3 4 5 6 7
Inorder traversal:     4 2 5 1 6 3 7
Preorder traversal:    1 2 4 5 3 6 7
Postorder traversal:   4 5 2 6 7 3 1

당신은 좋아할 것입니다 :