Javascriptツリーでトラバーサルを事前注文する
このトラバーサルメソッドでは、最初にルートノードにアクセスし、次に左側のサブツリーにアクセスし、最後に右側のサブツリーにアクセスします。
A、から始めます 事前注文トラバーサルに続いて、最初に Aにアクセスします それ自体を選択してから、左側のサブツリーBに移動します。 B プレオーダーもトラバースされます。このプロセスは、すべてのノードにアクセスするまで続きます。このツリーのプレオーダートラバーサルの出力は次のようになります-
A → B → D → E → C → F → G
これは、実装するアルゴリズムです:
- ノードのデータを印刷する
- 左のサブツリーを再帰的にトラバースします
- 右のサブツリーを再帰的にトラバースする
クラスでどのように実装するかを見てみましょう。
preOrder() { preOrderHelper(this.root); }
ヘルパー関数:
例
function preOrderHelper(root) { if (root !== null) { console.log(root.data); preOrderHelper(root.left); preOrderHelper(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.preOrder();
出力
これにより、出力が得られます-
10 5 3 7 15 12 50
-
データ構造におけるプレオーダーツリートラバーサル
このセクションでは、二分探索木のための事前順序トラバーサル手法(再帰的)について説明します。 このようなツリーが1つあるとします- トラバーサルシーケンスは次のようになります:10、5、8、16、15、20、23 アルゴリズム preorderTraverse(root): Begin if root is not empty, then print the value of root preorderTraversal(left of root)
-
データ構造におけるレベル順序ツリートラバーサル
このセクションでは、二分探索木のレベル順トラバーサル手法について説明します。 このようなツリーが1つあるとします- トラバーサルシーケンスは次のようになります:10、5、16、8、15、20、23 アルゴリズム levelOrderTraverse(root): Begin define queue que to store nodes insert root into the que. while que is not empty, do item := ite