Javascriptツリーでの注文後のトラバーサル

このトラバーサルメソッドでは、ルートノードが最後にアクセスされるため、この名前が付けられています。最初に左側のサブツリーをトラバースし、次に右側のサブツリーをトラバースし、最後にルートノードをトラバースします。

A、から始めます 注文後のトラバーサルに続いて、最初に左側のサブツリーBにアクセスします。 B 注文後にトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーのポストオーダートラバーサルの出力は-

D → E → B → F → G → C → A

これは、実装するアルゴリズムです-

• 左のサブツリーを再帰的にトラバースします
• 右のサブツリーを再帰的にトラバースする
• ノードのデータを印刷する

クラスでどのように実装するかを見てみましょう。

postOrder() {
   postOrderHelper(this.root);
}

ヘルパー関数-

例

function postOrderHelper(root) {
   if (root !== null) {
      postOrderHelper(root.left);
      postOrderHelper(root.right);
      console.log(root.data);
   }
}

-

例

let BST = new BinarySearchTree();
BST.insertRec(10);
BST.insertRec(15);
BST.insertRec(5);
BST.insertRec(50);
BST.insertRec(3);
BST.insertRec(7);
BST.insertRec(12);
BST.postOrder();

出力

これにより、出力が得られます-

3
7
5
12
50
15
10