Javascript樹的先序遍歷

樹是一種由節點和邊組成的資料結構。這些實體相互連線以形成樹形結構。

遍歷資料結構意味著訪問該結構中的每個節點並從中提取一系列值。有三種類型的遍歷，即先序遍歷 (L→ 根→R )、中序遍歷 (根→L→R) 和後序遍歷 (L→ R → 根)

中序遍歷

在中序遍歷中，首先訪問左子樹，然後訪問根節點，最後訪問右子樹。如果對二叉樹進行中序遍歷，則會按升序提供排序的鍵值。

它將表示為

LEFT → ROOT → RIGHT

考慮以下二叉搜尋樹：

遍歷從根節點A開始，並檢查根節點A是否有左子樹。由於存在，它移動到左子樹B。在B之後沒有子樹，將遍歷A（根節點）並轉到右子樹C以檢查其是否有左子樹。此過程將持續進行，直到遍歷所有節點。

上述中序樹遍歷的輸出將為：

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

演算法

中序遍歷 (樹)

  • 遍歷左子樹，樹中最左邊的節點將首先被列印 (左子樹)。

  • 返回根節點，列印根節點。

  • 遍歷右子樹，最右邊的節點將最後被列印 (右子樹)。

新增節點後的二叉搜尋樹

考慮一個新的場景，其中在樹中插入了更多節點。

上圖中的綠色箭頭指示中序遍歷的方向。

The end results of the presented binary tree are as follows:
D→ B→ E→ A→ H→ F→ I→ C→ G

示例 1（使用遞迴）

以下程式碼描述了使用遞迴技術的樹的中序遍歷。

<!DOCTYPE html>
<html>
   <head>
      <script>
         class Node {
            constructor(value) {
               this.key = value;
               this.left = null;
               this.right = null;
            }
         }
         var root = null;
         function TreeInorder(node) {
            if (node == null)
            return;
            TreeInorder(node.left);
            document.write(node.key + "→");
            TreeInorder(node.right);
         }
         root = new Node('A');
         root.left = new Node('B');
         root.right = new Node('C');
         root.right.left = new Node('D');
         root.right.right = new Node('E');
         root.right.right.left = new Node('F');
         root.right.right.right = new Node('G');
         document.write("<br/>Inorder traversal of the tree is<br/>");
         TreeInorder(root);
      </script>
   </head>
</html>

輸出

上述指令碼的輸出將為：

Inorder traversal of the tree is
B → A → D → C → F → E → G →

示例 2（使用棧）

另一種使用中序技術遍歷樹的方法可以使用棧。

<!DOCTYPE html>
<html>
   <head>
      <script>
         class Node {
            constructor(stack) {
               this.data = stack;
               this.left = this.right = null;
            }
         }
         var root_Node;
         function inorderUsingStack() {
            if (root_Node == null)
            return;
            let stack = [];
            let current_Node = root_Node;

            while (current_Node != null || stack.length > 0) {
               while (current_Node != null) {
                  stack.push(current_Node);
                  current_Node = current_Node.left;
               }
               current_Node = stack.pop();
               document.write(current_Node.data + "→");
               current_Node = current_Node.right;
            }
         }
         root_Node = new Node('A');
         root_Node.left = new Node('B');
         root_Node.right = new Node('C');
         root_Node.right.left = new Node('D');
         root_Node.right.right = new Node('E');
         root_Node.right.right.left = new Node('F');
         root_Node.right.right.right = new Node('G');
         inorderUsingStack();
      </script>
   </head>
</html>

輸出

上述指令碼的輸出將為：

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

更新於：2022年11月18日

2K+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告
© . All rights reserved.