JavaScript 樹的前序遍歷

樹是一種層次資料結構，包含節點和連線它們的邊。樹中的邊充當連線兩個節點的連結。

前序樹遍歷是一種技術，其中首先遍歷根節點，然後遍歷左子樹，最後遍歷右子樹。

它將表示為

ROOT → LEFT → RIGHT

演算法

以下是執行前序樹遍歷的步驟：

  • 遍歷根節點。

  • 然後，遍歷左子樹。

  • 然後，遍歷右子樹。

為了更好地理解前序遍歷，請考慮以下二叉搜尋樹：

遍歷將從根節點A開始並列印它。從那裡它訪問其左子樹B並列印它。然後再次列印左子樹D。並再次列印H子樹。由於 H 沒有其他左子樹，因此列印H。然後它將訪問I，它是D的右子樹。它以相同的方式繼續遍歷，直到訪問每個節點。

The output of the above preorder tree traversal is –
A → B → D → H → I → E → C → F → G

帶有附加連結節點的二叉搜尋樹

讓我們以下面的樹為例，向其中新增新的節點。

上圖顯示了使用綠色箭頭表示的前序樹遍歷路徑。

The above mentioned binary tree will produce the following output −
A→ B → D → C → E → G → H → F

示例 1（使用遞迴）

以下程式碼提供了使用遞迴技術的 Pre-order 樹遍歷的描述。

<!DOCTYPE html>
<html>
   <title>Pre-Order traversal of a tree</title>
   <head>
      <p id = "para"> </p>
      <script>
         class Node {
            constructor(value) {
               this.key = value;
               this.left = null;
               this.right = null;
            }
         }
         function TreePreorder(node) {
            if (node == null)
            return;
            document.write(node.key + " → ");
            TreePreorder(node.left);
            TreePreorder(node.right);
         }
         root = new Node('A');
         root.left = new Node('B');
         root.right = new Node('C');
         root.left.left = new Node('D');
         root.left.right = new Node('E');
         root.left.left.left = new Node('H');
         root.left.left.right = new Node('I');
         root.right.left = new Node('F');
         root.right.right = new Node('G');
         document.getElementById("para").innerHTML = "Pre-order traversal of binary tree will be: " + TreePreorder(root);
      </script>
   </head>
</html>

輸出

上述指令碼的輸出將是：

Pre-order traversal of binary tree will be:
A → B → D → H → I → E → C → F → G →

示例 2（使用棧）

另一種使用前序技術遍歷樹的方法可以透過使用棧來實現。

<!DOCTYPE html>
<html>
   <head>
      <p id = "para"> </p>
      <script>
         class Node {
            constructor(Node_value) {
               this.data = Node_value;
               this.right = null;
               this.left = null;
            }
         }
         let root;
         function Stack_Preorder(node) {
            if (node == null) {
               return;
            }
            let node_Stack = [];
            node_Stack.push(root);
            while (node_Stack.length > 0) {
               let mynode = node_Stack[node_Stack.length - 1];
               document.write(mynode.data + " ");
               node_Stack.pop();
               if (mynode.right != null) {
                  node_Stack.push(mynode.right);
               }
               if (mynode.left != null) {
                  node_Stack.push(mynode.left);
               }
            }
         }
         // Putting values into the nodes of the tree
         root = new Node('A');
         root.left = new Node('B');
         root.right = new Node('C');
         root.left.left = new Node('D');
         root.left.right = new Node('E');
         root.right.left = new Node('H');
         root.right.right = new Node('I');
         root.left.left.right = new Node('G');
         root.left.left.left = new Node('F');
         Stack_Preorder(root);
      </script>
   </head>
</html>

輸出

上述指令碼的輸出將是：

A B D F G E C H I

更新於： 2022年11月18日

2K+ 瀏覽量

啟動您的 職業生涯

透過完成課程獲得認證

開始學習
廣告

© . All rights reserved.