この記事では、データ構造におけるポストオーダー トラバーサルについて説明します。
スタック、配列、キューなどの線形データ構造には、データを走査する方法が 1 つしかありません。しかし、次のような階層データ構造では、 木 、データを走査するには複数の方法があります。そこで、ここではツリー データ構造をトラバースする別の方法について説明します。 通信販売の横断 。ポストオーダートラバーサルは、ツリー内のノードを訪問するために使用されるトラバース手法の 1 つです。それは原則に従っています LRN (左右ノード) 。ポストオーダー トラバーサルは、ツリーの後置式を取得するために使用されます。
チランジーヴィ俳優
ポストオーダートラバーサルを実行するには、次の手順を使用します。
- postorder 関数を再帰的に呼び出して、左側のサブツリーを走査します。
- postorder 関数を再帰的に呼び出して、右のサブツリーを走査します。
- 現在のノードのデータ部分にアクセスします。
ポストオーダートラバーサル手法は次のとおりです。 左右のルート ポリシー。ここで、Left Right Root は、ルート ノードの左側のサブツリーが最初にトラバースされ、次に右側のサブツリーがトラバースされ、最後にルート ノードがトラバースされることを意味します。ここで、Postorder の名前自体は、ツリーのルート ノードが最終的に横断されることを示唆しています。
アルゴリズム
次に、ポストオーダートラバーサルのアルゴリズムを見てみましょう。
Step 1: Repeat Steps 2 to 4 while TREE != NULL Step 2: POSTORDER(TREE -> LEFT) Step 3: POSTORDER(TREE -> RIGHT) Step 4: Write TREE -> DATA [END OF LOOP] Step 5: END
通信販売の横断例
次に、ポストオーダートラバーサルの例を見てみましょう。例を使用すると、ポストオーダー トラバーサルのプロセスを理解しやすくなります。
黄色のノードはまだ訪問されていません。ここで、ポストオーダートラバーサルを使用して上記のツリーのノードをトラバースします。
- ここで、40 はルート ノードです。まず、40 の左側のサブツリー、つまり 30 にアクセスします。ノード 30 もポストオーダーでトラバースします。 25 は 30 の左側のサブツリーであるため、これも事後順序で走査されます。この場合、15 は 25 の左の部分木になります。しかし、15 には部分木がないので、 印刷15 そして 25 の右のサブツリーに向かって移動します。
- 28 は 25 の右側のサブツリーであり、子はありません。それで、 プリント28 。
- 今、 プリント25 、および事後走査 25 終わりました。
- 次に、30 の右のサブツリーに進みます。35 は 30 の右のサブツリーであり、子はありません。それで、 プリント 35 。
- その後、 印刷30 、および事後走査 30 終わりました。したがって、指定されたバイナリ ツリーの左側のサブツリーがトラバースされます。
- ここで、40 の右側のサブツリー (50) に向かって移動します。これもポストオーダーでトラバースします。 45 は 50 の左側のサブツリーであり、子はありません。それで、 プリント45 そして、50 の右のサブツリーに向かって移動します。
- 60 は 50 の右側のサブツリーであり、これも事後順序で走査されます。 55 は、子のない 60 の左側のサブツリーです。それで、 プリント55 。
- 今、 70を印刷し、 これは 60 の右側のサブツリーです。
- 今、 60を印刷し、 そして 60 のポストオーダートラバースが完了します。
- 今、 50を印刷し、 そして 50 のポストオーダートラバースが完了します。
- やっと、 40を印刷し、 これは、指定されたバイナリ ツリーのルート ノードであり、ノード 40 のポスト オーダー トラバーサルが完了します。
ポストオーダートラバーサル後に得られる最終出力は次のとおりです。
Cの配列内の文字列
{15、28、25、35、30、45、55、70、60、50、40}
通信販売の横断の複雑さ
ポストオーダートラバーサルの時間計算量は次のとおりです。 の上） ここで、「n」はバイナリ ツリーのサイズです。
一方、ポストオーダートラバーサルの空間複雑さは、 ○(1) 関数呼び出しのスタック サイズを考慮しない場合。それ以外の場合、ポストオーダートラバーサルの空間複雑さは次のようになります。 おお） 、「h」は木の高さです。
通信販売横断の実装
次に、さまざまなプログラミング言語でのポストオーダー トラバーサルの実装を見てみましょう。
プログラム： C 言語でポストオーダー トラバーサルを実装するプログラムを作成します。
#include #include struct node { s 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 postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); printf(' %d ', root->element); } 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 Postorder traversal of given binary tree is -
'); traversePostorder(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 postorder*/ void traversePostorder(struct node* root) { if (root == NULL) return; traversePostorder(root->left); traversePostorder(root->right); cout<<' '<element<left="createNode(28);" root->right = createNode(48); root->left->left = createNode(23); root->left->right = createNode(33); root->left->left->left = createNode(13); root->left->left->right = createNode(26); root->right->left = createNode(43); root->right->right = createNode(58); root->right->right->left = createNode(53); root->right->right->right = createNode(68); cout<<'
the postorder traversal of given binary tree is -
'; traversepostorder(root); return 0; } < pre> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/85/postorder-traversal-14.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder 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 traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); Console.Write(node.value + ' '); } void traversePostorder() { traversePostorder(root); } static void Main() { BinaryTree bt = new BinaryTree(); bt.root = new Node(37); bt.root.left = new Node(27); bt.root.right = new Node(47); bt.root.left.left = new Node(22); bt.root.left.right = new Node(32); bt.root.left.left.left = new Node(12); bt.root.left.left.right = new Node(25); bt.root.right.left = new Node(42); bt.root.right.right = new Node(57); bt.root.right.right.left = new Node(52); bt.root.right.right.right = new Node(67); Console.WriteLine('The Postorder traversal of given binary tree is - '); bt.traversePostorder(); } } </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/85/postorder-traversal-15.webp" alt="Postorder Traversal"> <p> <strong>Program:</strong> Write a program to implement postorder traversal in Java.</p> <pre> class Node { public int value; public Node left, right; public Node(int element) { value = element; left = right = null; } } class PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); 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/85/postorder-traversal-16.webp" alt="Postorder 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 PostorderTraversal { Node root; PostorderTraversal() { root = null; } void traversePostorder(Node node) { if (node == null) return; traversePostorder(node.left); traversePostorder(node.right); System.out.print(node.value + ' '); } void traversePostorder() { traversePostorder(root); } public static void main(String args[]) { PostorderTraversal pt = new PostorderTraversal(); pt.root = new Node(36); pt.root.left = new Node(26); pt.root.right = new Node(46); pt.root.left.left = new Node(21); pt.root.left.right = new Node(31); pt.root.left.left.left = new Node(11); pt.root.left.left.right = new Node(24); pt.root.right.left = new Node(41); pt.root.right.right = new Node(56); pt.root.right.right.left = new Node(51); pt.root.right.right.right = new Node(66); System.out.println(); System.out.println('The Postorder traversal of given binary tree is - '); pt.traversePostorder(); System.out.println(); } } 出力
上記のコードを実行すると、出力は次のようになります -
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。