JavaScript 中的树遍历

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

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


基本术语

  • 节点 - 具有指向另一个节点的指针以及存储任何数据类型值的能力。

  • 根 - 此节点位于树的最顶端，没有父节点。

  • 子节点 - 子节点是直接与其对应的父节点连接的节点。

  • 边 - 树的边是连接两个节点的链接。

  • 路径 - 沿着树的边的节点顺序称为其路径。

  • 父节点 - 父节点具有作为子树附加的子节点。

  • 叶子节点 - 没有任何子节点附加到它的节点。

  • 子树 - 它是树的一个较小部分，将内部节点视为其根节点，并将连接到它的所有路径视为子节点。

  • 遍历 - 以特定顺序遍历树中的每个节点。

  • 层级 - 从节点到其根节点的后代数量称为层级。

  • 树的高度 - 从根到叶子的路径。它定义为子树的最大高度 + 1。

树遍历数据结构

通常，traverse 这个词的意思是“穿过（或穿过）”。树遍历是访问树中每个节点的操作。

树中有各种类型的遍历技术 -

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

    左 → 根 → 右

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

    根 → 左 → 右

  • 后序遍历 - 递归遍历左节点、右节点然后根节点的过程。后缀遍历是此遍历的另一个名称。

    左 → 右 → 根

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

BST 遍历的实现

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

示例

Open Compiler
<! 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

更新于: 2022-11-18

2K+ 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告