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

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
}