트리 순회(중순, 선순, 후순)
사라 첸
⚡ 스마트 요약
트리 순회는 이진 트리의 모든 노드를 정해진 순서대로 방문하는 과정입니다. 이 자료에서는 너비 우선 탐색(레벨 우선 탐색)과 깊이 우선 탐색의 세 가지 방법인 중위 순회, 전위 순회, 후위 순회를 단계별 예제, 의사 코드, 그리고 완전한 구현을 통해 설명합니다. Python, C 및 C++.
트리 순회란 무엇입니까?
트리 데이터 구조에서 순회는 특정 방식으로 노드를 방문하는 것을 의미합니다. 순회에는 두 가지 유형이 있습니다. 일반적으로 이러한 순회는 이진 트리를 기반으로 합니다. 이진 트리는 각 노드가 최대 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도 방문하게 됩니다.
- The 연산 현재 노드를 노드 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) > 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
