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+ 浏览量

启动您的 职业生涯

通过完成课程获得认证

开始学习
广告