この記事では、データ構造におけるプリオーダー トラバーサルについて説明します。スタック、配列、キューなどの線形データ構造には、データを走査する方法が 1 つしかありません。しかし、次のような階層データ構造では、 木 、データを走査するには複数の方法があります。
事前順序トラバーサルでは、最初にルート ノードが訪問され、次に左のサブツリーが訪問され、その後、右のサブツリーが訪問されます。事前注文トラバーサルのプロセスは次のように表すことができます -
root → left → right
ルート ノードは、preorder トラバーサルでは常に最初にトラバースされますが、postorder トラバーサルでは最後の項目になります。プレオーダー トラバーサルは、ツリーのプレフィックス式を取得するために使用されます。
事前注文トラバーサルを実行する手順は次のとおりです。
- まず、ルート ノードにアクセスします。
- 次に、左側のサブツリーにアクセスします。
- 最後に、右のサブツリーにアクセスします。
プリオーダートラバーサル手法は次のとおりです。 ルート左右 ポリシー。 preorder という名前自体は、ルート ノードが最初に通過されることを示唆しています。
アルゴリズム
次に、プリオーダートラバーサルのアルゴリズムを見てみましょう。
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: Write TREE -> DATA Step 3: PREORDER(TREE -> LEFT) Step 4: PREORDER(TREE -> RIGHT) [END OF LOOP] Step 5: END
プリオーダートラバーサルの例
次に、事前注文トラバーサルの例を見てみましょう。例を使用すると、事前注文トラバーサルのプロセスを理解しやすくなります。
黄色のノードはまだ訪問されていません。ここで、事前順序走査を使用して上記のツリーのノードを走査します。
- ルートノード 40 から始めます。まず、 プリント40 次に、左側のサブツリーを再帰的に走査します。
- 次に、左側のサブツリーに移動します。左側のサブツリーのルート ノードは 30 です。 30 を印刷する 、30 の左側のサブツリーに向かって移動します。
- 30 の左側のサブツリーには要素 25 があるため、 プリント25 、25 の左側のサブツリーをトラバースします。
- 25 の左側のサブツリーには要素 15 がありますが、15 にはサブツリーがありません。それで、 印刷15 、25 の右のサブツリーに移動します。
- 25 の右側の部分木には 28 があり、28 には部分木がありません。それで、 プリント28 、30 の右のサブツリーに移動します。
- 30 の右側の部分木には、部分木を持たない 35 があります。それで プリント 35 、40 の右側のサブツリーをトラバースします。
- 40 の右側のサブツリーには 50 があります。 50を印刷する 、50 の左側のサブツリーをトラバースします。
- 50 の左側のサブツリーには、子を持たないものが 45 あります。それで、 プリント45 、50 の右側のサブツリーをトラバースします。
- 50 の右側のサブツリーには 60 があります。 プリント60 そして 60 の左側のサブツリーをトラバースします。
- 60 の左側のサブツリーには、子のない 55 があります。それで、 プリント55 60 の右のサブツリーに移動します。
- 60 の右側のサブツリーには、子を持たない 70 があります。それで、 印刷 70 そしてプロセスを停止します。
事前注文トラバーサルの完了後の最終出力は次のようになります -
40、30、25、15、28、35、50、45、60、55、70
プレオーダートラバーサルの複雑さ
プリオーダートラバーサルの時間計算量は次のとおりです。 の上） ここで、「n」はバイナリ ツリーのサイズです。
一方、プリオーダートラバーサルの空間複雑さは ○(1) 関数呼び出しのスタック サイズを考慮しない場合。それ以外の場合、事前順序トラバーサルの空間複雑さは次のようになります。 おお） 、「h」は木の高さです。
プレオーダートラバーサルの実装
次に、さまざまなプログラミング言語でのプリオーダー トラバーサルの実装を見てみましょう。
プログラム： C 言語でプリオーダー トラバーサルを実装するプログラムを作成します。
#include #include struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; printf(' %d ', root->element); traversePreorder(root->left); traversePreorder(root->right); } int main() { struct node* root = createNode(40); root->left = createNode(30); root->right = createNode(50); root->left->left = createNode(25); root->left->right = createNode(35); root->left->left->left = createNode(15); root->left->left->right = createNode(28); root->right->left = createNode(45); root->right->right = createNode(60); root->right->right->left = createNode(55); root->right->right->right = createNode(70); printf('
The Preorder traversal of given binary tree is -
'); traversePreorder(root); return 0; } 出力
上記のコードを実行すると、出力は次のようになります -
プログラム： C++ で事前順序トラバーサルを実装するプログラムを作成します。
#include using namespace std; struct node { int element; struct node* left; struct node* right; }; /*To create a new node*/ struct node* createNode(int val) { struct node* Node = (struct node*)malloc(sizeof(struct node)); Node->element = val; Node->left = NULL; Node->right = NULL; return (Node); } /*function to traverse the nodes of binary tree in preorder*/ void traversePreorder(struct node* root) { if (root == NULL) return; cout<<' '<element<left); traversepreorder(root->right); } int main() { struct node* root = createNode(39); root->left = createNode(29); root->right = createNode(49); root->left->left = createNode(24); root->left->right = createNode(34); root->left->left->left = createNode(14); root->left->left->right = createNode(27); root->right->left = createNode(44); root->right->right = createNode(59); root->right->right->left = createNode(54); root->right->right->right = createNode(69); cout<<'
the preorder traversal of given binary tree is -
'; traversepreorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-14.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in C#.</p> <pre> using System; class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class BinaryTree { Node root; BinaryTree() { root = null; } void traversePreorder(Node node) { if (node == null) return; Console.Write(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(38); bt.root.left = new Node(28); bt.root.right = new Node(48); bt.root.left.left = new Node(23); bt.root.left.right = new Node(33); bt.root.left.left.left = new Node(13); bt.root.left.left.right = new Node(26); bt.root.right.left = new Node(43); bt.root.right.right = new Node(58); bt.root.right.right.left = new Node(53); bt.root.right.right.right = new Node(68); Console.WriteLine('Preorder traversal of given binary tree is - '); bt.traversePreorder(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-15.webp" alt="Preorder Traversal"> <p> <strong>Program:</strong> Write a program to implement preorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } </pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/25/preorder-traversal-16.webp" alt="Preorder Traversal"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></'
></'> 出力
上記のコードを実行すると、出力は次のようになります -
プログラム： Java で事前順序トラバーサルを実装するプログラムを作成します。
class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PreorderTraversal { Node root; PreorderTraversal() { root = null; } void traversePreorder(Node node) { if (node == null) return; System.out.print(node.value + ' '); traversePreorder(node.left); traversePreorder(node.right); } void traversePreorder() { traversePreorder(root); } public static void main(String args[]) { PreorderTraversal pt = new PreorderTraversal(); pt.root = new Node(37); pt.root.left = new Node(27); pt.root.right = new Node(47); pt.root.left.left = new Node(22); pt.root.left.right = new Node(32); pt.root.left.left.left = new Node(12); pt.root.left.left.right = new Node(25); pt.root.right.left = new Node(42); pt.root.right.right = new Node(57); pt.root.right.right.left = new Node(52); pt.root.right.right.right = new Node(67); System.out.println(); System.out.println('Preorder traversal of given binary tree is - '); pt.traversePreorder(); System.out.println(); } } 出力
上記のコードを実行すると、出力は次のようになります -
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。