二分木の事後走査
郵便注文のトラバース のタイプとして定義されます ツリートラバース これは、各ノードに対して次のような Left-Right-Root ポリシーに従います。
- 左側のサブツリーが最初に走査されます
- 次に、右側のサブツリーが走査されます
- 最後に、サブツリーのルート ノードが走査されます。
郵便注文のトラバース
バイナリ ツリーのポストオーダー トラバーサルのアルゴリズム:
ポストオーダートラバーサルのアルゴリズムは次のとおりです。
郵便注文 (ルート):
- root != NULLになるまでステップ2から4を実行します。
- 後順 (ルート -> 左)
- 事後順序 (ルート -> 右)
- ルート -> データの書き込み
- エンドループ
二分木のポストオーダートラバーサルはどのように機能しますか?
次のツリーを考えてみましょう。
二分木の例
このバイナリ ツリーで事後探索を実行すると、探索は次のようになります。
ステップ1： トラバーサルは 1 からその左のサブツリー (つまり 2) に進み、次に 2 からその左のサブツリー ルート (つまり 4) に進みます。現在、4 にはサブツリーがないため、そこが訪問されます。
ノード 4 が訪問されました
ステップ2： 2 の左側のサブツリーが完全に訪問されると、今度は 2 の右側のサブツリーをたどることになります。つまり、5 に移動します。5 のサブツリーがないため、それが訪問されます。
ノード 5 が訪問されました
ステップ 3: ここで、ノード 2 の左右のサブツリーの両方が訪問されます。次に、ノード 2 自体にアクセスします。
ノード 2 が訪問されました
ステップ 4: ノード 1 の左側のサブツリーがトラバースされると、右側のサブツリー ルート、つまり 3 に移動します。ノード 3 には左側のサブツリーがないため、右側のサブツリー、つまり 6 をトラバースします。ノード 6 にはサブツリーがなく、それで訪問されるのです。
ノード 6 が訪問されました
ステップ5: ノード 3 のすべてのサブツリーが走査されます。したがって、ノード 3 が訪問されます。
ノード 3 が訪問されました
ステップ6: ノード 1 のすべてのサブツリーが走査されると、今度はノード 1 を訪問する時間になり、その後ツリー全体が走査されるので走査は終了します。
完全なツリーを訪問する
したがって、ノードのトラバース順序は次のようになります。 4 -> 5 -> 2 -> 6 -> 3 -> 1 。
二分木のポストオーダートラバーサルを実装するプログラム
以下はポストオーダートラバーサルのコード実装です。
C++
// C++ program for postorder 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 postorder traversal> void> printPostorder(> struct> Node* node)> {> > if> (node == NULL)> > return> ;> > // First recur on left subtree> > printPostorder(node->左);>> // Now deal with the node> > cout ' '; } // Driver code int main() { struct Node* root = new Node(1); root->左 = 新しいノード(2); ルート->右 = 新しいノード(3); ルート->左->左 = 新しいノード(4); ルート->左->右 = 新しいノード(5); ルート->右->右 = 新しいノード(6); // 関数呼び出し cout < < 'Postorder traversal of binary tree is:
'; printPostorder(root); return 0; }> |
ジャワ
// Java program for postorder traversals> import> java.util.*;> // Structure of a Binary Tree Node> class> Node {> > int> data;> > Node left, right;> > Node(> int> v)> > {> > data = v;> > left = right => null> ;> > }> }> class> GFG {> > > // Function to print postorder traversal> > static> 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.data +> ' '> );> > }> > // Driver code> > public> static> void> main(String[] args)> > {> > 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> > System.out.println(> 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by prasad264> |
Python3
# Python program for postorder 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 postorder traversal> def> printPostorder(node):> > if> node> => => None> :> > return> > # First recur on left subtree> > printPostorder(node.left)> > # Then recur on right subtree> > printPostorder(node.right)> > # Now deal with the node> > print> (node.data, end> => ' '> )> # 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> (> 'Postorder traversal of binary tree is:'> )> > printPostorder(root)> |
C#
// C# program for postorder 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> ;> > }> }> public> class> GFG {> > // Function to print postorder traversal> > static> 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.data +> ' '> );> > }> > static> public> void> Main()> > {> > // Code> > 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(> > 'Postorder traversal of binary tree is: '> );> > printPostorder(root);> > }> }> // This code is contributed by karthik.> |
JavaScript
// Structure of a Binary Tree Node> class Node {> > constructor(v) {> > this> .data = v;> > this> .left => null> ;> > this> .right => null> ;> > }> }> // Function to print 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.data +> ' '> );> }> // Driver code> function> main() {> > let 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(> 'Postorder traversal of binary tree is:
'> );> > printPostorder(root);> }> main();> |
出力
Postorder traversal of binary tree is: 4 5 2 6 3 1
説明：
通信販売の横断の仕組み
複雑さの分析:
時間計算量: O(N) ここで、N はノードの総数です。すべてのノードを少なくとも 1 回通過するためです。
補助スペース: 再帰スタック領域が考慮されない場合は O(1)。それ以外の場合、O(h) (h は木の高さ)
- 最悪の場合、 h と同じにすることができます N （斜木の場合）
- 最良の場合、 h と同じにすることができます 落ち着いた (ツリーが完全なツリーの場合)
ポストオーダー トラバーサルの使用例:
ポストオーダートラバーサルの使用例には次のようなものがあります。
- これはツリーの削除に使用されます。
- 式ツリーから後置式を取得することも便利です。
関連記事：
- ツリートラバーサルの種類
- 反復ポストオーダー トラバーサル (2 つのスタックを使用)
- 反復的なポストオーダー トラバーサル (1 つのスタックを使用)
- 再帰なし、スタックなしのバイナリ ツリーの事後順序
- プリオーダートラバーサルからBSTのポストオーダートラバーサルを見つける
- 通販用モリス・トラバーサル
- preorer からの postorder トラバーサルと inorder トラバーサルを印刷します。
