logo

TechCodeview

ツリー トラバーサル手法 – データ構造とアルゴリズムのチュートリアル

ツリートラバーサル手法 ツリーのすべてのノードにアクセスするためのさまざまな方法が含まれています。走査するための論理的な方法が 1 つしかない線形データ構造 (配列、リンク リスト、キュー、スタックなど) とは異なり、ツリーはさまざまな方法で走査できます。この記事では、すべてのツリー トラバース手法とその使用法について説明します。



目次

ツリートラバーサルの意味:

ツリートラバーサル ツリーの各ノードを特定の順序で 1 回だけ訪問またはアクセスするプロセスを指します。ツリー トラバーサル アルゴリズムは、ツリーのすべてのノードにアクセスして処理するのに役立ちます。ツリーは線形データ構造ではないため、特定のノードを訪問した後に訪問できるノードが複数存在します。ツリーのノードを訪問する順序を決定する複数のツリー トラバーサル手法があります。

ツリートラバーサル手法:



ツリー データ構造は次の方法で横断できます。

  • 深さ優先検索または DFS
    • インオーダートラバーサル
    • 予約注文トラバーサル
    • 郵便為替トラバーサル
  • レベル順序トラバーサルまたは幅優先検索または BFS

インオーダートラバーサル :

インオーダートラバーサルは、次の順序でノードを訪問します。 左 -> 根元 -> 右




インオーダートラバーサルのアルゴリズム:

順序(木)

  • 左側のサブツリーを走査します。つまり、Inorder(left->subtree) を呼び出します。
  • ルートを訪問します。
  • 右のサブツリーをトラバースします。つまり、Inorder(right->subtree) を呼び出します。

インオーダートラバーサルの用途:

  • 二分探索ツリー (BST) の場合、Inorder traversal は非降順でノードを与えます。
  • BST のノードを非昇順で取得するには、Inorder トラバーサルを逆にした Inorder トラバーサルのバリエーションを使用できます。
  • インオーダートラバーサルを使用して、式ツリーに格納されている算術式を評価できます。

インオーダートラバーサルのコードスニペット:

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->右）; }>>
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->左）;  // 次に、ノードのデータを出力します printf('%d ', node->data);  // 右の子で再帰的に 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); }>
Python3 
# 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)>
C# 
// 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); }>
JavaScript 
// 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); }>>
C 
// 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); }>
Python3 
# 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)>
C# 
// 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); }>
JavaScript 
// 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->データ<< ' '; }>
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);  // ここでノードを処理します 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 + ' '); }>
Python3 
# 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=' '),>
C# 
// 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 + ' '); }>
JavaScript 
// 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 からノードをデキューし、そこにアクセスします
    • デキューされたノードの左側の子が存在する場合は、それをエンキューします。
    • デキューされたノードの右側の子が存在する場合は、それをエンキューします。

レベル順序の用途:

  • レベル オーダー トラバーサルは、主に幅優先検索として使用され、ノードをレベルごとに検索または処理します。
  • レベル順序トラバーサルは次の目的にも使用されます。 ツリーのシリアル化と逆シリアル化 。

レベル順序トラバーサルのコード スニペット:

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  queueq;  // ルートをキューに入れ、高さを初期化します。 q.push(root);  while (q.empty() == false) { // キューの先頭を出力し、キューから削除 Node* node = q.front();  コート<< node->データ<< ' ';  q.pop();  // Enqueue left child  if (node->left != NULL) q.push(node->left);  // 右の子をキューに入れる if (node->right != NULL) q.push(node->right);  } }>>
C 
// 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キュー = 新しいリンクリスト();  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);  } } }>>'Python3>
C# 
// Given a binary tree. Print // its nodes in level order using // array for implementing queue void printLevelOrder() {  Queueキュー = 新しいキュー();  キュー.エンキュー(ルート);  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);  } } }>>'JavaScript

その他のツリートラバーサル:

  1. 境界の横断
  2. 斜め移動

1. 境界の横断 :

境界の横断 ツリーには次のものが含まれます。

  • 左側の境界 (葉ノードを除く左側のノード)
  • 葉 (葉ノードのみで構成)
  • 右境界 (葉ノードを除く右側のノード)

境界越えのアルゴリズム:

境界通過(ツリー)

  • ルートが null でない場合:
    • ルートのデータを出力する
    • PrintLeftBoundary(root->left) // 左側の境界ノードを出力します。
    • PrintLeafNodes(root->left) // 左側のサブツリーのリーフ ノードを出力します。
    • PrintLeafNodes(root->right) // 右サブツリーのリーフ ノードを出力します。
    • PrintRightBoundary(root->right) // 右側の境界ノードを出力します。

境界トラバーサルの用途:

  • 境界トラバーサルは、バイナリ ツリーの外部構造を視覚化するのに役立ち、その形状と境界についての洞察が得られます。
  • 境界トラバーサルは、これらのノードにアクセスして変更する方法を提供し、境界ノードの枝刈りや再配置などの操作を可能にします。

2. 斜め移動

ツリーの対角線トラバーサルでは、単一の対角線内のすべてのノードが 1 つずつ出力されます。

斜めトラバーサルのアルゴリズム:

DiagonalTraversal(ツリー):

  • ルートが null でない場合:
    • 空のマップを作成する
    • DiagonalTraversalUtil(root, 0, M) // 初期対角レベル 0 でヘルパー関数を呼び出します
    • M の各キーと値のペア (diagonalLevel、ノード) について:
      • ノード内の各ノードについて:
      • 印刷ノードのデータ

DiagonalTraversalUtil(ノード、斜めレベル、M):

  • ノードが null の場合:
  • 戻る
  • M にdiamondLevel が存在しない場合:
    • 対角レベルの M に新しいリストを作成します
  • ノードのデータを M[diagonalLevel] のリストに追加します
  • DiagonalTraversalUtil(node->left, DiagonalLevel + 1, M) // 増加した対角レベルで左の子をトラバースします
  • DiagonalTraversalUtil(node->right, DiagonalLevel, M) // 同じ対角レベルで右の子をトラバースします

斜めトラバーサルの用途:

  • 対角トラバーサルは、バイナリ ツリー、特にバイナリ サーチ ツリー (BST) やヒープ ツリーなどのツリーベースのデータ構造の階層構造を視覚化するのに役立ちます。
  • 対角線トラバーサルを利用して、バイナリ ツリーの対角線に沿ったパスの合計を計算できます。

ツリー トラバーサル手法に関するよくある質問 (FAQ):

1. ツリートラバーサル手法とは何ですか?

ツリー トラバーサル手法は、ツリー データ構造内のすべてのノードを訪問して処理するために使用される方法です。これにより、体系的な方法で各ノードに 1 回だけアクセスできるようになります。

2. 一般的なツリートラバーサルの種類は何ですか?

ツリー トラバーサルの一般的なタイプは次のとおりです。 インオーダー トラバーサル、プレオーダー トラバーサル、ポストオーダー トラバーサル、レベル順トラバーサル (幅優先検索)

キーボードに挿入する

3. インオーダートラバーサルとは何ですか?

インオーダートラバーサルは、左のサブツリー、現在のノード、右のサブツリーの順序でノードを訪問する深さ優先のトラバーサル方法です。

4. プレオーダートラバーサルとは何ですか?

プリオーダー トラバーサルは、現在のノード、左のサブツリー、右のサブツリーの順序でノードを訪問する深さ優先のトラバーサル方法です。

5. 郵便為替トラバーサルとは何ですか?

ポストオーダートラバーサルは、左のサブツリー、右のサブツリー、現在のノードの順序でノードを訪問する深さ優先のトラバーサル方法です。

6. レベル順序トラバーサルとは何ですか?

幅優先検索 (BFS) とも呼ばれるレベル順序トラバーサルは、ルートから開始して次のレベルに移動してから、より深くトラバースする前に、レベルごとにノードを訪問します。

7. 各トラバーサル手法はいつ使用する必要がありますか?

インオーダートラバーサルは、ソートされた順序でノードを取得するために二分探索ツリーによく使用されます。

事前注文トラバーサルは、ツリーのコピーを作成する場合に便利です。

ポストオーダー トラバーサルは、式を評価するために式ツリーで一般的に使用されます。

レベル順序トラバーサルは、ノード間の最短パスを見つけるのに役立ちます。

8. ツリートラバーサルアルゴリズムを実装するにはどうすればよいですか?

ツリー トラバーサル アルゴリズムは、特定の要件と使用されているプログラミング言語に応じて、再帰的または反復的に実装できます。

9. ツリートラバーサルアルゴリズムは他のツリー状構造にも適用できますか?

はい、ツリー トラバーサル アルゴリズムは、バイナリ ヒープ、n 分ツリー、ツリーとして表されるグラフなど、他のツリー状構造をトラバースするように適応できます。

10. トラバーサル手法を選択する際に、パフォーマンスに関する考慮事項はありますか?

パフォーマンスに関する考慮事項は、ツリーのサイズと形状、利用可能なメモリ、トラバーサル中に実行される特定の操作などの要因によって異なります。一般に、トラバーサル手法の選択は特定の操作の効率に影響を与える可能性があるため、特定のユースケースに最適な方法を選択することが重要です。

その他の重要なチュートリアル:

  • DSA チュートリアル
  • システム設計チュートリアル
  • ソフトウェア開発ロードマップ
  • プロダクトマネージャーになるためのロードマップ
  • SAP を学ぶ
  • SEOを学ぶ