Javascriptツリーでの順序どおりのトラバーサル

このトラバーサルメソッドでは、最初に左側のサブツリーにアクセスし、次にルートにアクセスし、次に右側のサブツリーにアクセスします。すべてのノードがサブツリー自体を表す場合があることを常に覚えておく必要があります。

二分木が順番にトラバースされる場合 、出力は昇順でソートされたキー値を生成します。

A、から始めます 順番にトラバーサルした後、左側のサブツリーBに移動します。 B また、順番にトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーの順序付けられたトラバーサルの出力は次のようになります-

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

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

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

クラスでどのように実装するかを見てみましょう。ユーザーが自分でrootを渡してほしくないので、クラスの外にヘルパー関数を作成します。

inOrder() {
inOrderHelper(this.root);
}

ヘルパー関数-

例

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

-

例

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.inOrder();

出力

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

3
5
7
10
12
15
50

要素はソートされた順序で印刷されていることに注意してください。これは、最初に左側のサブツリーを再帰的に探索するため、最初に最小値を取得するためです。これは最後まで続き、すべての要素が並べ替えられた順序で取得されます。