logo

TechCodeview

バイナリ ツリーの事前注文トラバーサル

事前注文トラバーサル のタイプとして定義されます ツリートラバース これは、Root-Left-Right ポリシーに従います。

  • サブツリーのルート ノードが最初にアクセスされます。
  • 次に、左側のサブツリーが走査されます。
  • 最後に、右側のサブツリーをたどります。
事前注文トラバーサル

事前注文トラバーサル

バイナリツリーのプリオーダートラバーサルアルゴリズム

プリオーダー トラバーサルのアルゴリズムは次のとおりです。



予約注文(ルート):

  1. root != NULLになるまでステップ2から4を実行します。
  2. ルート -> データの書き込み
  3. 予約注文 (ルート -> 左)
  4. 予約注文 (ルート -> 右)
  5. エンドループ

バイナリ ツリーの事前注文トラバーサルはどのように機能しますか?

次のツリーを考えてみましょう。

二分木の例

二分木の例

このバイナリ ツリーで事前順序走査を実行すると、走査は次のようになります。

ステップ1： 最初にルート、つまりノード 1 にアクセスします。

ノード 1 が訪問されました

ノード 1 が訪問されました

ステップ2： この後、左側のサブツリーをトラバースします。ここで、左側のサブツリーのルート、つまりノード 2 が訪問されます。

JavaコアJava
ノード 2 が訪問されました

ノード 2 が訪問されました

ステップ 3: 再び、ノード 2 の左側のサブツリーがたどられ、そのサブツリーのルート、つまりノード 4 が訪問されます。

ノード 4 が訪問されました

ノード 4 が訪問されました

ステップ 4: 4 のサブツリーは存在しないため、ノード 2 の左側のサブツリーが参照されます。したがって、ノード 2 の右のサブツリーがトラバースされ、そのサブツリーのルート、つまりノード 5 が訪問されます。

ノード 5 が訪問されました

ノード 5 が訪問されました

ステップ5: ノード 1 の左側のサブツリーが参照されます。したがって、ノード 1 の右側のサブツリーがトラバースされ、ルート ノード、つまりノード 3 が訪問されます。

ノード 3 が訪問されました

ノード 3 が訪問されました

ステップ6: ノード 3 には左側のサブツリーがありません。したがって、右のサブツリーをたどって、サブツリーのルート、つまりノード 6 にアクセスします。その後、まだ通過していないノードはありません。それで縦走は終了です。

完全なツリーを訪問する

完全なツリーを訪問する

したがって、ノードのトラバース順序は次のようになります。 1 -> 2 -> 4 -> 5 -> 3 -> 6 。

バイナリツリーのプリオーダートラバーサルを実装するプログラム

以下は、事前注文トラバーサルのコード実装です。

C++ 
// C++ program for preorder traversals #include  using namespace std; // Structure of a Binary Tree Node struct Node {  int data;  struct Node *left, *right;  Node(int v)  {  data = v;  left = right = NULL;  } }; // Function to print preorder traversal void printPreorder(struct Node* node) {  if (node == NULL)  return;  // Deal with the node  cout << node->データ<< ' ';  // Recur on left subtree  printPreorder(node->左）;  // 右のサブツリーで繰り返します printPreorder(node->right); } // ドライバー コード int main() { struct Node* root = new Node(1);  ルート->左 = 新しいノード(2);  ルート->右 = 新しいノード(3);  ルート->左->左 = 新しいノード(4);  ルート->左->右 = 新しいノード(5);  ルート->右->右 = 新しいノード(6);  // 関数呼び出し cout<< 'Preorder traversal of binary tree is: 
';  printPreorder(root);  return 0; }>
ジャワ 
// Java program for preorder traversals class Node {  int data;  Node left, right;  public Node(int item) {  data = item;  left = right = null;  } } class BinaryTree {  Node root;  BinaryTree() {  root = null;  }  // Function to print preorder traversal  void printPreorder(Node node) {  if (node == null)  return;  // Deal with the node  System.out.print(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void main(String[] args) {  BinaryTree tree = new BinaryTree();  // Constructing the binary tree  tree.root = new Node(1);  tree.root.left = new Node(2);  tree.root.right = new Node(3);  tree.root.left.left = new Node(4);  tree.root.left.right = new Node(5);  tree.root.right.right = new Node(6);  // Function call  System.out.println('Preorder traversal of binary tree is: ');  tree.printPreorder(tree.root);  } }>
Python3 
# Python program for preorder traversals # Structure of a Binary Tree Node class Node: def __init__(self, v): self.data = v self.left = None self.right = None # Function to print preorder traversal def printPreorder(node): if node is None: return # Deal with the node print(node.data, end=' ') # Recur on left subtree printPreorder(node.left) # Recur on right subtree printPreorder(node.right) # Driver code if __name__ == '__main__': root = Node(1) root.left = Node(2) root.right = Node(3) root.left.left = Node(4) root.left.right = Node(5) root.right.right = Node(6) # Function call print('Preorder traversal of binary tree is:') printPreorder(root)>
C# 
// C# program for preorder traversals using System; // Structure of a Binary Tree Node public class Node {  public int data;  public Node left, right;  public Node(int v)  {  data = v;  left = right = null;  } } // Class to print preorder traversal public class BinaryTree {  // Function to print preorder traversal  public static void printPreorder(Node node)  {  if (node == null)  return;  // Deal with the node  Console.Write(node.data + ' ');  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right);  }  // Driver code  public static void Main()  {  Node root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  Console.WriteLine(  'Preorder traversal of binary tree is: ');  printPreorder(root);  } } // This code is contributed by Susobhan Akhuli>
JavaScript 
// Structure of a Binary Tree Node class Node {  constructor(v) {  this.data = v;  this.left = null;  this.right = null;  } } // Function to print preorder traversal function printPreorder(node) {  if (node === null) {  return;  }  // Deal with the node  console.log(node.data);  // Recur on left subtree  printPreorder(node.left);  // Recur on right subtree  printPreorder(node.right); } // Driver code function main() {  const root = new Node(1);  root.left = new Node(2);  root.right = new Node(3);  root.left.left = new Node(4);  root.left.right = new Node(5);  root.right.right = new Node(6);  // Function call  console.log('Preorder traversal of binary tree is:');  printPreorder(root); } main();>
出力 
Preorder traversal of binary tree is: 1 2 4 5 3 6>

説明：

事前注文トラバーサルの仕組み

プリオーダートラバーサルの仕組み

複雑さの分析:

時間計算量: O(N) ここで、N はノードの総数です。すべてのノードを少なくとも 1 回通過するためです。
補助スペース:

  • ○(1) 再帰スタックスペースが考慮されていない場合。
  • さもないと、 おお） ここで、h は木の高さです
  • 最悪の場合、 h と同じにすることができます N （斜木の場合）
  • 最良の場合、 h と同じにすることができます 落ち着いた (ツリーが完全なツリーの場合)

事前注文トラバーサルの使用例:

事前注文トラバーサルの使用例には次のようなものがあります。

  • これは、ツリーのコピーを作成するためによく使用されます。
  • 式ツリーからプレフィックス式を取得することも便利です。

関連記事：

Androidで隠しアプリを開く方法
  • ツリートラバーサルの種類
  • 反復的な事前注文トラバーサル
  • 指定された配列が BST の事前順序トラバーサルを表現できるかどうかを確認する
  • 順および事後走査からの事前注文
  • 二分木の事前順序走査で n 番目のノードを見つける
  • N 分木の事前順序走査