JavaScript中的树遍历

Javascript Web开发前端技术

树是一种非线性的分层数据结构，它结合了**节点**和**边**。树中的节点存储值，这些节点通过**边**相互连接。树的最顶层节点没有任何父节点，被称为根节点。

下面的二叉搜索树用重要术语进行了标记。

基本术语

**节点** - 指向另一个节点的指针，并能够存储任何数据类型的数值。
**根** - 此节点位于树的最顶部，没有父节点。
**子节点** - 子节点是直接与其对应的父节点连接的节点。
**边** - 树的边是连接两个节点的链接。
**路径** - 沿着树的边的节点顺序称为其路径。
**父节点** - 父节点具有附加为子树的子节点。
**叶子节点** - 没有任何子节点附加到它的节点。
**子树** - 它是树的一个较小的部分，将内部节点视为其根，并将所有连接到它的路径视为子节点。
**遍历** - 以特定顺序遍历树中的每个节点。
**层级** - 从节点到其根节点的后代数量称为层级。
**树的高度** - 从根到叶子的路径。它被定义为子树的最大高度 + 1。

树遍历数据结构

一般来说，“遍历”这个词意味着“穿过（或穿过）”。树遍历是在我们访问树的每个节点的操作。

树中有多种类型的遍历技术：

**中序遍历** - 通过访问左子树、根节点，然后右子树（在BST中）递归遍历树的过程称为中序遍历。这种遍历也称为对称遍历。

左 → 根 → 右
**前序遍历** - 在这种遍历中 - 首先遍历根节点，然后递归遍历左子树和右子树的过程。前缀遍历也是用来描述这个过程的术语。

根 → 左 → 右
**后序遍历** - 递归地遍历左节点、右节点，然后根节点的过程。后缀遍历是这种遍历的另一个名称。

左 → 右 → 根

我们总是从根（头部）节点开始，因为所有节点都通过边（链接）连接。在其他情况下，我们无法随机访问树节点。

BST遍历的实现

在下面的脚本中，我们以独特的方式实现了所有三种遍历。

示例


<! DOCTYPE html>
<html>
   <head>
      <script>
         class Node {
            constructor(value) {
               this.value = value;
               this.left = null;
               this.right = null;
            }
         }
         class BinarySearchTree {
            constructor() {
               this.root = null;
            }

            inserting(value) {
               let node = new Node(value);
               if(this.root == null) {
                  this.root = node;
               }else {
                  this.insertNode(this.root, node);
               }
            }

            insertNode(root, newNode) {
               if(newNode.value < root.value) {
                  if(root.left == null) {
                     root.left = newNode;
                  } else {
                     this.insertNode(root.left, newNode);
                  }
               } else if(newNode.value > root.value) {
                  if(root.right == null) {
                     root.right = newNode;
                  } else {
                     this.insertNode(root.right, newNode);
                  }
               }
            }
            getRootNode() {
               return this.root;
            }

            /* implementation of individual operations of traversal in tree */

            preorderTrav(root) {
               if(root != null) {
                  document.write(root.value); // Traverse the root node
                  this.preorderTrav(root.left); /* Traverse the left subtree */
                  this.preorderTrav(root.right); /* Traverse the right subtree */
               }
            }

            inorderTrav(root) {
               if(root != null) {
                  this.inorderTrav(root.left); /* Traverse the left subtree */
                  document.write(root.value); // Traverse the root node
                  this.inorderTrav(root.right); /* Traverse the right subtree */
               }
            }

            postorderTrav(root) {
               if(root != null) {
                  this.postorderTrav(root.left); /* Traverse the left subtree */
                  this.postorderTrav(root.right); /* Traverse the right subtree */
                  document.write(root.value); // Traverse the root node
               }
            }
         }
         
         var bst = new BinarySearchTree();
         bst.inserting(30);
         bst.inserting(50);
         bst.inserting(20);
         bst.inserting(14);
         bst.inserting(44);
         bst.inserting(34);
         bst.inserting(26);
         bst.inserting(10);
         bst.inserting(19);
         bst.inserting(54);
         
         var root = bst.getRootNode();
         document.write("preorder traversal of the binary tree is <br>");
         bst.preorderTrav(root);
         document.write('<br>');
         document.write('inorder traversal of the binary tree is <br>');
         bst.inorderTrav(root);
         document.write('<br>');
         document.write('Postorder traversal of the binary tree is <br>');
         bst.postorderTrav(root);
         document.write('<br>');
      </script>
   </head>
   <body>
   </body>
</html>

输出

上述脚本的输出将是：

Pre-order traversal of the binary tree is
30 20 14 10 19 26 50 44 34 54

In-order traversal of the binary tree is
10 14 19 20 26 30 34 44 50 54

Post-order traversal of the binary tree is
10 19 14 26 20 34 44 54 50 30

Nikhilesh Aleti

更新于：2022年11月18日

2K+ 次浏览

启动您的职业生涯

通过完成课程获得认证

开始