이진 트리 순회

1. 이진 트리 순회
2. 이진 트리 순회 그림
3. 이진 트리 탐색 알고리즘
4. 이진 트리 탐색 구현
5. 이진 트리 탐색 알고리즘 복잡성

이진 트리는 비선형 데이터 구조입니다. 각 노드에는 최대 두 개의 자식이 있기 때문에 이진 트리라고합니다. 이 아이들을 왼쪽 아이들과 오른쪽 아이들이라고 부릅니다. 또한 최상위 노드를 루트라고하는 무 방향 그래프로 해석 될 수도 있습니다. 한 가지 방식으로 만 순회 할 수있는 선형 데이터 구조와 달리 트리는 다른 방식으로 순회 할 수 있습니다. 깊이 또는 폭을 따라 탐색하여 나무를 횡단 할 수 있습니다. 첫 번째 접근 방식은 Depth-First Traversal이라고하고 두 번째 접근 방식은 Breadth-First Traversal이라고합니다. 이 기사에서는 깊이 우선 순회에 대해 설명합니다.

깊이 우선 순회에는 순서, 사전 주문 및 후 순서의 3 가지 종류가 있습니다. 각각에 대해 하나씩 논의 할 것입니다.

이진 트리 순회

Inorder Traversal

이 순회에서는 먼저 왼쪽 하위 트리, 루트, 마지막으로 오른쪽 하위 트리를 차례로 방문합니다. 모든 노드는 하위 트리와 유사합니다. BST의 경우 inorder traversal은 모든 요소를 ​​오름차순으로 반환합니다.

순회 선주문

이 순회에서는 먼저 루트, 왼쪽 하위 트리, 마지막으로 오른쪽 하위 트리를 방문합니다. 모든 노드는 하위 트리와 유사합니다. 일반적으로 복제, 즉 트리 복사본을 만드는 데 사용됩니다. 접두사 순회는 식 트리에서 접두사 식을 생성하는데도 도움이됩니다.

주문 후 순회

이 순회에서는 먼저 왼쪽 하위 트리, 오른쪽 하위 트리, 마지막으로 루트를 방문합니다. 모든 노드는 하위 트리와 유사합니다. 효과적으로 나무를 삭제하는 데 사용됩니다. 또한 식 트리에서 접미사 식을 생성하는 데 도움이됩니다.

이진 트리 순회 그림

Inorder Traversal :(4, 2, 1, 5, 3, 6, 7, 8, 9)

루트 노드3에서 inorder traversal을 호출합니다. 재귀 적으로 왼쪽으로 이동하여 가장 왼쪽 노드 인4노드에 도달하고이를 출력에 포함합니다. 루트이고 왼쪽 노드가 없으므로 가장 오른쪽 노드2를 방문하여 순회에 포함합니다. 이런 식으로 전체 트리를 탐색하여 위의 순서를 출력으로 얻습니다.

선주문 순회 :(3, 1, 4, 2, 5, 7, 6, 9, 8)

루트 노드3에서 사전 주문 순회를 호출하고 출력에 포함합니다. 그런 다음 재귀 적으로 왼쪽으로 이동하여 다음 루트 노드1에 도달 한 다음4에 도달합니다. 4에는 왼쪽 자식이 없으므로 오른쪽 노드2를 방문합니다. 이제 루트 노드4아래의 하위 트리를 다루었 고 노드1로 다시 추적하여 노드5의 오른쪽으로 이동합니다. 이런 식으로 전체 트리를 탐색하여 위의 순서를 출력으로 얻습니다.

주문 후 순회 :(2, 4, 5, 1, 6, 8, 9, 7, 3)

루트 노드3에서 postorder traversal을 호출합니다. 노드4에 도달하기 위해 재귀 적으로 왼쪽으로 이동합니다. 순회에4를 포함하기 전에 올바른 노드2를 방문해야합니다. 출력에2를 포함시킨 다음4를 포함하고1로 다시 이동합니다. 그런 다음 루트 노드3으로 다시 추적하고 오른쪽 하위 트리를 탐색합니다. 이런 식으로 전체 트리를 탐색하여 위의 순서를 출력으로 얻습니다.

이진 트리 탐색 알고리즘

Inorder Traversal

순회 선주문

포스트 오더 순회

이진 트리 탐색 구현

#include <iostream>
using namespace std;

class Node {
 public:
  int key;
  Node *left, *right;
  Node(int x) {
    this->key = x;
    this->left = this->right = NULL;
  }
};

void inorder(Node* root) {
  if (root != NULL) {
    inorder(root->left);
    cout << root->key << " ";
    inorder(root->right);
  }
}
void preorder(Node* root) {
  if (root != NULL) {
    cout << root->key << " ";
    preorder(root->left);
    preorder(root->right);
  }
}

void postorder(Node* root) {
  if (root != NULL) {
    postorder(root->left);
    postorder(root->right);
    cout << root->key << " ";
  }
}

int main() {
  Node* root = new Node(3);
  root->left = new Node(1);
  root->right = new Node(7);
  root->left->left = new Node(4);
  root->left->right = new Node(5);
  root->left->left->right = new Node(2);
  root->right->left = new Node(6);
  root->right->right = new Node(9);
  root->right->right->left = new Node(8);
  cout << "The inorder traversal of the tree is : ";
  inorder(root);
  cout << endl;
  cout << "The preorder traversal of the tree is : ";
  preorder(root);
  cout << endl;
  cout << "The postorder traversal of the tree is : ";
  postorder(root);
  cout << endl;
}

이진 트리 탐색 알고리즘 복잡성

시간 복잡성

• 평균 사례

트리에는n노드가 있으며 모든3종류의 순회에서 각 노드를 방문해야합니다. n노드를 반복하기 때문에 순서는 다르지만 모든 3 개의 순회에 대한 시간 복잡도는O(n)의 순서입니다. 평균 케이스 시간 복잡도는O(n)입니다.

• 베스트 케이스

최상의 경우 시간 복잡도는O(n)입니다. 모든3순회에 대한 평균 케이스 시간 복잡도와 동일합니다.

• 최악의 경우

최악의 시간 복잡도는O(n)입니다. 모든3순회에 대한 최악의 시간 복잡도와 동일합니다.

공간 복잡성

알고리즘의 공간 복잡성은 재귀 호출에 필요한 추가 공간으로 인해O(n)입니다.