Preorder, Postorder 및 Inorder 이진 검색 트리 탐색 전략을 사용하는 경우

Preorder, Postorder 및 Inorder 이진 검색 트리 탐색 전략을 사용하는 경우

---

나는 최근에 내 인생에서 BST를 많이 사용했지만 Inorder traversal 이외의 것을 사용하는 것을 고려한 적이 없다는 것을 깨달았습니다 (사전 / 사후 주문 탐색을 사용하도록 프로그램을 조정하는 것이 얼마나 쉬운 지 알고 알고 있지만).

이것을 깨닫고 나는 오래된 데이터 구조 교과서를 뽑아서 선주문과 주문 후 순회의 유용성에 대한 추론을 찾았습니다.하지만 그들은 많이 말하지 않았습니다.

사전 주문 / 후 주문을 실제로 사용하는 경우의 몇 가지 예는 무엇입니까? 순서대로하는 것보다 언제 더 의미가 있습니까?

---

Pre-Order, In-Order 및 Post-Order Traversal 전략을 사용하는 경우

이진 트리에 대해 사전 주문, 순서 및 사후 주문을 사용하는 상황을 이해하기 전에 각 순회 전략이 어떻게 작동하는지 정확히 이해해야합니다. 다음 트리를 예로 사용하십시오.

트리의 루트는 7 , 가장 왼쪽 노드는 0 , 가장 오른쪽 노드는 10 입니다.

선주문 순회 :

요약 : 루트 ( 7 ) 에서 시작하여 맨 오른쪽 노드 ( 10 ) 에서 끝납니다.

순회 시퀀스 : 7, 1, 0, 3, 2, 5, 4, 6, 9, 8, 10

순회 순회 :

요약 : 맨 왼쪽 노드 ( 0 )에서 시작하여 맨 오른쪽 노드 ( 10 ) 에서 끝납니다.

순회 시퀀스 : 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

주문 후 순회 :

요약 : 가장 왼쪽 노드 ( 0 )에서 시작하여 루트 ( 7 )로 끝납니다.

순회 시퀀스 : 0, 2, 4, 6, 5, 3, 1, 8, 10, 9, 7

Pre-Order, In-order 또는 Post-Order는 언제 사용합니까?

프로그래머가 선택하는 순회 전략은 설계중인 알고리즘의 특정 요구 사항에 따라 다릅니다. 목표는 속도이므로 가장 빠르게 필요한 노드를 제공하는 전략을 선택하십시오.

1. 잎을 검사하기 전에 뿌리를 조사해야한다는 것을 알고 있다면 모든 잎 보다 먼저 모든 뿌리를 만나게되므로 사전 주문 을 선택 하십시오.

2. 노드보다 먼저 모든 잎을 탐색해야한다는 것을 알고 있다면 잎 을 찾기 위해 뿌리를 검사하는 데 시간을 낭비하지 않기 때문에 주문 후 를 선택 합니다.

3. 트리가 노드에 내재 된 시퀀스를 가지고 있다는 것을 알고 있고 트리를 원래 시퀀스로 다시 평평하게 하려면 순회 순회를 사용해야합니다. 나무는 만들어진 것과 같은 방식으로 평평 해집니다. 사전 주문 또는 사후 주문 순회는 트리를 생성하는 데 사용 된 시퀀스로 다시 풀리지 않을 수 있습니다.

선주문, In-order 및 Post-order를위한 재귀 알고리즘 (C ++) :

struct Node{
    int data;
    Node *left, *right;
};
void preOrderPrint(Node *root)
{
  print(root->name);                                  //record root
  if (root->left != NULL) preOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) preOrderPrint(root->right);//traverse right if exists
}

void inOrderPrint(Node *root)
{
  if (root.left != NULL) inOrderPrint(root->left);   //traverse left if exists
  print(root->name);                                 //record root
  if (root.right != NULL) inOrderPrint(root->right); //traverse right if exists
}

void postOrderPrint(Node *root)
{
  if (root->left != NULL) postOrderPrint(root->left);  //traverse left if exists
  if (root->right != NULL) postOrderPrint(root->right);//traverse right if exists
  print(root->name);                                   //record root
}

---

트리의 계층 적 형식을 선형 형식으로 간단히 인쇄하려면 사전 주문 순회를 사용합니다. 예를 들면 :

- ROOT
    - A
         - B
         - C
    - D
         - E
         - F
             - G

---

선주문 / 주문 / 주문 후 사용 : 간단한 단어

Pre-order: Used to create a copy of tree Example : If you want to create a replica of a tree and need node values in an array and when you insert those values from index 0 to end in a new tree, you get a replica

In-order: : To get values of node in non-increasing order

Post-order: : When you want to delete a tree from leaf to root

---

Pre- and post-order relate to top-down and bottom-up recursive algorithms, respectively. If you want to write a given recursive algorithm on binary trees in an iterative fashion, this is what you will essentially do.

Observe furthermore that pre- and post-order sequences together completely specify the tree at hand, yielding a compact encoding (for sparse trees a least).

---

There are tons of places you see this difference play a real role.

One great one I'll point out is in code generation for a compiler. Consider the statement:

x := y + 32

The way you would generate code for that is (naively, of course) to first generate code for loading y into a register, loading 32 into a register, and then generating an instruction to add the two. Because something has to be in a register before you manipulate it (let's assume, you can always do constant operands but whatever) you must do it this way.

일반적으로이 질문에 대해 얻을 수있는 답변은 기본적으로 다음과 같이 축소됩니다. 데이터 구조의 다른 부분을 처리하는 사이에 약간의 의존성이있을 때 차이가 실제로 중요합니다. 요소를 인쇄 할 때, 코드를 생성 할 때 (외부 상태가 차이를 만들 때, 물론 모나드 방식으로도 볼 수 있음) 또는 먼저 처리되는 하위 항목에 따라 계산을 포함하는 구조에 대해 다른 유형의 계산을 수행 할 때 이것을 볼 수 있습니다. .

참고 URL : https://stackoverflow.com/questions/9456937/when-to-use-preorder-postorder-and-inorder-binary-search-tree-traversal-strate