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

开启你的职业生涯

完成课程获得认证

开始学习
广告