資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究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（使用遞迴）
以下程式碼描述了使用遞迴技術的先序樹遍歷。
<!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+ 次瀏覽
廣告