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

开启你的职业生涯

完成课程获得认证

开始学习
广告