logo

TechCodeview

트리 순회 기술 – 데이터 구조 및 알고리즘 자습서

트리 순회 기술 트리의 모든 노드를 방문하는 다양한 방법을 포함합니다. 순회하는 논리적 방법이 하나만 있는 선형 데이터 구조(배열, 연결 목록, 큐, 스택 등)와 달리 트리는 다양한 방식으로 순회할 수 있습니다. 이 기사에서는 모든 트리 순회 기술과 그 사용법에 대해 논의합니다.



내용의 테이블

트리 순회 의미:

트리 순회 트리의 각 노드를 특정 순서에 따라 정확히 한 번씩 방문하거나 액세스하는 프로세스를 말합니다. 트리 순회 알고리즘은 트리의 모든 노드를 방문하고 처리하는 데 도움이 됩니다. 트리는 선형 데이터 구조가 아니기 때문에 특정 노드를 방문한 후 방문할 수 있는 노드가 여러 개 있습니다. 트리의 노드를 방문하는 순서를 결정하는 여러 가지 트리 탐색 기술이 있습니다.

트리 순회 기술:



트리 데이터 구조는 다음과 같은 방법으로 탐색할 수 있습니다.

  • 깊이 우선 검색 또는 DFS
    • 중위순회
    • 선주문 순회
    • 우편 주문 순회
  • 레벨 순서 순회 또는 너비 우선 검색 또는 BFS

중위순회 :

중위 순회는 다음 순서로 노드를 방문합니다. 왼쪽 -> 루트 -> 오른쪽




중위 순회 알고리즘:

중위(트리)

  • 왼쪽 하위 트리를 탐색합니다. 즉, Inorder(left->subtree)를 호출합니다.
  • 루트를 방문하십시오.
  • 오른쪽 하위 트리를 탐색합니다. 즉, Inorder(right->subtree)를 호출합니다.

중위 순회 사용:

  • BST(이진 검색 트리)의 경우 중위 순회는 노드를 감소하지 않는 순서로 제공합니다.
  • 비증가 순서로 BST의 노드를 얻으려면 중위 순회를 역순으로 하는 중위 순회 변형을 사용할 수 있습니다.
  • 중위 순회를 사용하여 표현식 트리에 저장된 산술 표현식을 평가할 수 있습니다.

중위 순회를 위한 코드 조각:

C++ 
// Given a binary tree, print its nodes in inorder void printInorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->왼쪽);  // 그런 다음 노드 cout의 데이터를 인쇄합니다.<< node->데이터<< ' ';  // Now recur on right child  printInorder(node->오른쪽); }>
씨 
// Given a binary tree, print its nodes in inorder void printInorder(struct node* node) {  if (node == NULL)  return;  // First recur on left child  printInorder(node->왼쪽);  // 그런 다음 노드의 데이터를 인쇄합니다. printf('%d ', node->data);  // 이제 오른쪽에서 반복됩니다. child printInorder(node->right); }>
자바 
void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  System.out.print(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
파이썬3 
# A function to do inorder tree traversal def printInorder(root): if root: # First recur on left child printInorder(root.left) # Then print the data of node print(root.val, end=' '), # Now recur on right child printInorder(root.right)>
씨# 
// Given a binary tree, print // its nodes in inorder void printInorder(Node node) {  if (node == null)  return;  // First recur on left child  printInorder(node.left);  // Then print the data of node  Console.Write(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
자바스크립트 
// Given a binary tree, print its nodes in inorder function printInorder(node) {  if (node == null)  return;  // First recur on left child */  printInorder(node.left);  // Then print the data of node  console.log(node.key + ' ');  // Now recur on right child  printInorder(node.right); }>
산출 
Inorder traversal of binary tree is 4 2 5 1 3>

시간 복잡도: 에)
보조 공간: 함수 호출을 위한 스택 크기를 고려하지 않으면 O(1), 그렇지 않으면 O(h)입니다. 여기서 h는 트리의 높이입니다.

선주문 순회 :

선주문 순회는 다음 순서로 노드를 방문합니다. 루트 -> 왼쪽 -> 오른쪽

선주문 탐색 알고리즘:

예약주문(트리)

마두발라
  • 루트를 방문하십시오.
  • 왼쪽 하위 트리를 탐색합니다. 즉, Preorder(left->subtree)를 호출합니다.
  • 오른쪽 하위 트리를 탐색합니다. 즉, Preorder(right->subtree)를 호출합니다.

선주문 순회 사용:

  • 선주문 순회는 트리의 복사본을 만드는 데 사용됩니다.
  • 선주문 순회는 표현식 트리에서 접두사 표현식을 가져오는 데에도 사용됩니다.

선주문 순회를 위한 코드 조각:

C++ 
// Given a binary tree, print its nodes in preorder void printPreorder(struct Node* node) {  if (node == NULL)  return;  // First print data of node  cout << node->데이터<< ' ';  // Then recur on left subtree  printPreorder(node->왼쪽);  // 이제 오른쪽 하위 트리에서 반복됩니다. printPreorder(node->right); }>
씨 
// Given a binary tree, print its nodes in preorder void printPreorder(struct node* node) {  if (node == NULL)  return;  // First print data of node  printf('%d ', node->데이터);  // 그런 다음 왼쪽 하위 트리에서 반복됩니다. printPreorder(node->left);  // 이제 오른쪽 하위 트리에서 반복됩니다. printPreorder(node->right); }>
자바 
// Given a binary tree, print its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  System.out.print(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
파이썬3 
# A function to do preorder tree traversal def printPreorder(root): if root: # First print the data of node print(root.val, end=' '), # Then recur on left child printPreorder(root.left) # Finally recur on right child printPreorder(root.right)>
씨# 
// Given a binary tree, print // its nodes in preorder void printPreorder(Node node) {  if (node == null)  return;  // First print data of node  Console.Write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
자바스크립트 
// Given a binary tree, print its nodes in preorder function printPreorder(node) {  if (node == null)  return;  // First print data of node  document.write(node.key + ' ');  // Then recur on left subtree  printPreorder(node.left);  // Now recur on right subtree  printPreorder(node.right); }>
산출 
Preorder traversal of binary tree is 1 2 4 5 3>

시간 복잡도: 에)
보조 공간: 함수 호출을 위한 스택 크기를 고려하지 않으면 O(1), 그렇지 않으면 O(h)입니다. 여기서 h는 트리의 높이입니다.

우편 주문 순회 :

후위 순회는 다음 순서로 노드를 방문합니다. 왼쪽 -> 오른쪽 -> 루트

후위 순회 알고리즘:

알고리즘 우편순서(트리)

  • 왼쪽 하위 트리를 탐색합니다. 즉, Postorder(left->subtree)를 호출합니다.
  • 오른쪽 하위 트리를 탐색합니다. 즉, Postorder(right->subtree)를 호출합니다.
  • 루트를 방문하세요

우편 주문 탐색의 사용:

  • 후위 순회는 트리를 삭제하는 데 사용됩니다. 보다 나무 삭제에 대한 질문 자세한 내용은.
  • 후위 순회는 표현식 트리의 후위 표현식을 얻는 데에도 유용합니다.
  • 후위 순회는 특히 수동 메모리 관리가 사용되는 시스템에서 가비지 수집 알고리즘에 도움이 될 수 있습니다.

우편 주문 탐색을 위한 코드 조각:

C++ 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct Node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->왼쪽);  // 그런 다음 오른쪽 하위 트리에서 반복됩니다. printPostorder(node->right);  // 이제 노드 cout을 처리합니다.<< node->데이터<< ' '; }>
씨 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(struct node* node) {  if (node == NULL)  return;  // First recur on left subtree  printPostorder(node->왼쪽);  // 그런 다음 오른쪽 하위 트리에서 반복됩니다. printPostorder(node->right);  // 이제 노드를 처리합니다. printf('%d ', node->data); }>
자바 
// Given a binary tree, print its nodes according to the // 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  System.out.print(node.key + ' '); }>
파이썬3 
# A function to do postorder tree traversal def printPostorder(root): if root: # First recur on left child printPostorder(root.left) # The recur on right child printPostorder(root.right) # Now print the data of node print(root.val, end=' '),>
씨# 
// Given a binary tree, print its nodes according to // the 'bottom-up' postorder traversal. void printPostorder(Node node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  Console.Write(node.key + ' '); }>
자바스크립트 
// Given a binary tree, print its nodes according  // to the 'bottom-up' postorder traversal function printPostorder(node) {  if (node == null)  return;  // First recur on left subtree  printPostorder(node.left);  // Then recur on right subtree  printPostorder(node.right);  // Now deal with the node  console.log(node.key + ' '); }>
산출 
Postorder traversal of binary tree is 4 5 2 3 1>

레벨 순서 순회 :

레벨 순서 순회 다음 레벨을 방문하기 전에 동일한 레벨에 있는 모든 노드를 완전히 방문합니다.

자바 문자열 형식 긴

레벨 순서 순회 알고리즘:

LevelOrder(트리)

  • 빈 큐 생성 Q
  • 트리의 루트 노드를 Q에 대기열에 넣습니다.
  • Q가 비어 있지 않은 동안 반복
    • Q에서 노드를 대기열에서 빼고 방문합니다.
    • 대기열에서 제거된 노드의 왼쪽 자식이 존재하는 경우 대기열에 넣습니다.
    • 대기열에서 제거된 노드가 존재하는 경우 해당 노드의 오른쪽 자식을 대기열에 넣습니다.

레벨 순서의 사용:

  • Level Order Traversal은 주로 노드를 레벨별로 검색하거나 처리하기 위한 Breadth First Search로 사용됩니다.
  • 레벨 순서 순회는 다음 용도로도 사용됩니다. 트리 직렬화 및 역직렬화 .

레벨 순서 순회를 위한 코드 조각:

C++ 
// Iterative method to find height of Binary Tree void printLevelOrder(Node* root) {  // Base Case  if (root == NULL)  return;  // Create an empty queue for level order traversal  queue큐;  // 루트를 대기열에 넣고 높이를 초기화합니다. q.push(root);  while (q.empty() == false) { // 대기열의 앞부분을 인쇄하고 대기열에서 제거합니다. Node* node = q.front();  시합<< node->데이터<< ' ';  q.pop();  // Enqueue left child  if (node->왼쪽 != NULL) q.push(node->left);  // 오른쪽 자식을 대기열에 넣습니다. if (node->right != NULL) q.push(node->right);  } }>
씨 
// Given a binary tree, print its nodes in level order // using array for implementing queue void printLevelOrder(struct node* root) {  int rear, front;  struct node** queue = createQueue(&front, &rear);  struct node* temp_node = root;  while (temp_node) {  printf('%d ', temp_node->데이터);  // 왼쪽 자식을 대기열에 넣습니다. if (temp_node->left) enQueue(queue, &rear, temp_node->left);  // 오른쪽 자식을 대기열에 추가합니다. if (temp_node->right) enQueue(queue, &rear, temp_node->right);  // 노드를 대기열에서 빼고 temp_node로 만듭니다. temp_node = deQueue(queue, &front);  } }>
자바 
// Given a binary tree. Print // its nodes in level order // using array for implementing queue void printLevelOrder() {  Queue대기열 = 새로운 LinkedList();  queue.add(루트);  while (!queue.isEmpty()) { // poll()은 현재 헤드를 제거합니다.  노드 tempNode = queue.poll();  System.out.print(tempNode.data + ' ');  // 왼쪽 자식을 대기열에 넣습니다. if (tempNode.left != null) { queue.add(tempNode.left);  } // 오른쪽 자식을 큐에 넣습니다. if (tempNode.right != null) { queue.add(tempNode.right);  } } }>
파이썬3 
# Iterative Method to print the # height of a binary tree def printLevelOrder(root): # Base Case if root is None: return # Create an empty queue # for level order traversal queue = [] # Enqueue Root and initialize height queue.append(root) while(len(queue)>0): # 대기열의 앞 부분을 인쇄하고 # 대기열에서 제거합니다. print(queue[0].data, end=' ') node = queue.pop(0) # node.left가 None이 아닌 경우 왼쪽 자식을 대기열에 넣습니다. queue.append(node.left) # node.right가 None이 아닌 경우 오른쪽 자식을 대기열에 넣습니다. queue.append(node.right)>
씨# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queue대기열 = 새 대기열();  queue.Enqueue(루트);  while (queue.Count != 0) { 노드 tempNode = queue.Dequeue();  Console.Write(tempNode.data + ' ');  // 왼쪽 자식을 대기열에 넣습니다. if (tempNode.left != null) { queue.Enqueue(tempNode.left);  } // 오른쪽 자식을 큐에 넣습니다. if (tempNode.right != null) { queue.Enqueue(tempNode.right);  } } }>
자바스크립트 
// Function to perform level order traversal of a binary tree function printLevelOrder(root) {  // Create a deque to store nodes for traversal  const queue = new Deque();  // Add the root node to the queue  queue.enqueue(root);  // Continue traversal until the queue is empty  while (!queue.isEmpty()) {  // Remove and get the first node from the queue  const tempNode = queue.dequeue();  // Print the data of the current node  console.log(tempNode.data + ' ');  // Enqueue the left child if it exists  if (tempNode.left !== null) {  queue.enqueue(tempNode.left);  }  // Enqueue the right child if it exists  if (tempNode.right !== null) {  queue.enqueue(tempNode.right);  }  } }>

기타 트리 순회:

  1. 경계 순회
  2. 대각선 횡단

1. 경계 순회 :

경계 순회 트리에는 다음이 포함됩니다.

  • 왼쪽 경계(리프 노드를 제외한 왼쪽 노드)
  • 나뭇잎(잎 노드로만 구성됨)
  • 오른쪽 경계(리프 노드를 제외한 오른쪽 노드)

경계 순회 알고리즘:

경계 탐색(나무)

  • 루트가 null이 아닌 경우:
    • 루트의 데이터 인쇄
    • PrintLeftBoundary(root->left) // 왼쪽 경계 노드를 인쇄합니다.
    • PrintLeafNodes(root->left) // 왼쪽 하위 트리의 리프 노드를 인쇄합니다.
    • PrintLeafNodes(root->right) // 오른쪽 하위 트리의 리프 노드를 인쇄합니다.
    • PrintRightBoundary(root->right) // 오른쪽 경계 노드를 인쇄합니다.

경계 순회 사용:

  • 경계 순회는 이진 트리의 외부 구조를 시각화하여 모양과 경계에 대한 통찰력을 제공합니다.
  • 경계 순회는 이러한 노드에 액세스하고 수정하는 방법을 제공하여 경계 노드의 가지치기 또는 위치 변경과 같은 작업을 가능하게 합니다.

2. 대각선 횡단

트리의 대각선 순회에서는 단일 대각선의 모든 노드가 하나씩 인쇄됩니다.

대각선 횡단 알고리즘:

대각선 횡단(나무):

  • 루트가 null이 아닌 경우:
    • 빈 지도 만들기
    • DiagonalTraversalUtil(root, 0, M) // 초기 대각선 레벨 0으로 도우미 함수 호출
    • M의 각 키-값 쌍(diagonalLevel, 노드)에 대해:
      • 노드의 각 노드에 대해 다음을 수행합니다.
      • 노드의 데이터 인쇄

DiagonalTraversalUtil(노드, 대각선레벨, M):

  • 노드가 null인 경우:
  • 반품
  • 대각선 레벨이 M에 존재하지 않는 경우:
    • 대각선 레벨에 대해 M에서 새 목록을 만듭니다.
  • M[diagonalLevel]의 목록에 노드의 데이터를 추가합니다.
  • DiagonalTraversalUtil(node->left, 대각선 레벨 + 1, M) // 증가된 대각선 레벨로 왼쪽 자식 트래버스
  • DiagonalTraversalUtil(node->right, 대각선 레벨, M) // 동일한 대각선 레벨로 오른쪽 하위 항목을 트래버스합니다.

대각선 횡단의 사용:

  • 대각선 순회는 특히 BST(이진 검색 트리) 및 힙 트리와 같은 트리 기반 데이터 구조에서 이진 트리의 계층 구조를 시각화하는 데 도움이 됩니다.
  • 대각선 순회는 이진 트리의 대각선을 따라 경로 합을 계산하는 데 활용될 수 있습니다.

트리 순회 기술에 대한 자주 묻는 질문(FAQ):

1. 트리 순회 기술이란 무엇입니까?

트리 순회 기술은 트리 데이터 구조의 모든 노드를 방문하고 처리하는 데 사용되는 방법입니다. 이를 통해 체계적인 방식으로 각 노드에 정확히 한 번만 액세스할 수 있습니다.

2. 일반적인 트리 순회 유형은 무엇입니까?

일반적인 트리 순회 유형은 다음과 같습니다: 중위 순회, 선순 순회, 후순 순회, 수준 순회(너비 우선 검색)

자바 이진 트리

3. 중위 순회란 무엇입니까?

중위 순회는 왼쪽 하위 트리, 현재 노드, 오른쪽 하위 트리 순서로 노드를 방문하는 깊이 우선 순회 방법입니다.

4. 선주문 순회란 무엇인가요?

선순서 순회는 현재 노드, 왼쪽 하위 트리, 오른쪽 하위 트리 순서로 노드를 방문하는 깊이 우선 순회 방법입니다.

5. 우편주문 순회란 무엇입니까?

후위 순회는 왼쪽 하위 트리, 오른쪽 하위 트리, 현재 노드의 순서로 노드를 방문하는 깊이 우선 순회 방법입니다.

6. 레벨 오더 순회란 무엇입니까?

BFS(Breadth-First Search)라고도 하는 레벨 순서 탐색은 루트에서 시작하여 다음 레벨로 이동한 후 더 깊이 탐색하는 방식으로 노드 레벨을 방문합니다.

7. 각 순회 기술은 언제 사용해야 합니까?

중위 순회는 이진 검색 트리에 정렬된 순서로 노드를 가져오는 데 자주 사용됩니다.

선주문 순회는 트리 복사본을 만드는 데 유용합니다.

후위 순회는 일반적으로 표현식 트리에서 표현식을 평가하는 데 사용됩니다.

레벨 순서 순회는 노드 간 최단 경로를 찾는 데 유용합니다.

8. 트리 순회 알고리즘을 어떻게 구현합니까?

트리 탐색 알고리즘은 사용되는 특정 요구 사항 및 프로그래밍 언어에 따라 재귀적으로 또는 반복적으로 구현될 수 있습니다.

9. 트리 순회 알고리즘을 다른 트리형 구조에 적용할 수 있습니까?

예, 트리 순회 알고리즘은 이진 힙, n-ary 트리 및 트리로 표시되는 그래프와 같은 다른 트리형 구조를 순회하도록 조정할 수 있습니다.

10. 순회 기술을 선택할 때 성능 고려 사항이 있습니까?

성능 고려 사항은 트리의 크기와 모양, 사용 가능한 메모리, 순회 중에 수행되는 특정 작업과 같은 요소에 따라 달라집니다. 일반적으로 순회 기술의 선택은 특정 작업의 효율성에 영향을 미칠 수 있으므로 특정 사용 사례에 가장 적합한 방법을 선택하는 것이 중요합니다.

기타 중요한 튜토리얼:

  • DSA 튜토리얼
  • 시스템 설계 튜토리얼
  • 소프트웨어 개발 로드맵
  • 제품 관리자가 되기 위한 로드맵
  • SAP 알아보기
  • SEO 배우기