ツリー トラバーサル (順序、事前順序、事後順序) と例

ツリートラバーサルとは何ですか?

ツリー データ構造では、トラバーサルとは、何らかの特定の方法でノードを訪問することを意味します。 ノード 2 タイプのトラバーサルがあります。 一般に、この種の走査はバイナリ ツリーに基づいています。 バイナリ ツリーは、各ノードが最大 2 つのノードを持つことができることを意味します。

二分木はよく知られたデータ構造です。 二分探索ツリー (BST) もあります。 このタイプのトラバーサルはさまざまな目的に使用されます。 レベル順序トラバーサル。XNUMX つのノード間の深さを計算するために使用されます。 「AVL」と呼ばれる別の種類のツリーがあり、ノードの高さを計算する必要があります。 配列でバイナリ ツリーを表すことができますが、メモリの最適化のために、次のノードを参照するために構造体とポインタを使用します。

ツリートラバーサルの種類

我々が議論したように 二分木, 次に、トラバーサルの個々のタイプについて説明します。 種類に応じて、トラバースには XNUMX つのタイプがあります。 以前、レベル順序または幅優先トラバーサルの必要性について述べました。 今 深さ優先トラバーサル post order はノードの削除に使用され (後ほど説明します)、preorder はバイナリ ツリーのコピーに使用され、inorder はツリーを非減少方式でトラバースします。

• 幅優先探索
• 深さ優先トラバーサル
• 事前注文トラバーサル
• 注文後のトラバーサル
• 順序どおりの走査

幅優先探索

これはレベル順トラバーサルとも呼ばれます。レベル順トラバーサルを示すために、次のツリーを考えてみましょう。

したがって、ルートノード「1」から開始します。 これはレベル 1 としてマークされます。その後、アルゴリズムは現在のノードのすべての子に適用されます。 ここでノード 2 と 3 を参照します。 これらはレベル 2 としてマークされます。

その後、レベル 2 に 2 つのノードがあるので、その子も訪問します。 したがって、5,6,8,7、3、XNUMX、XNUMX を訪問し、それらをレベル XNUMX としてマークします。ここで言及していないことがあります。

ノードのレベル = 親ノードのレベル + 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 も訪問されます。
• その アルゴリズム 現在のノードをノード 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）, インオーダートラバーサルでは、ソートされた値の配列が得られます。

注文後のトラバーサル

この走査では、まず左端のサブツリーを走査し、次にルートに続いて右端のサブツリーを走査します。 すべての走査は事後順序で行われます。 例を示してみましょう。

ここで root = 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) & gt;
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