当前位置：Gxlcms > JavaScript > js_前中后序二叉树遍历的三种算法_简单二叉树的实现

js_前中后序二叉树遍历的三种算法_简单二叉树的实现

时间：2021-07-01 10:21:17 帮助过：22人阅读

关于二叉树的建立和遍历，本文中做出了详细的介绍，以及前序二叉树遍历、中序二叉树遍历、后序二叉树遍历的算法也做出了解释，并引用了代码，是为了让大家看的更清晰。本文的介绍还是先从二叉树和二叉查找树开始吧，便于理解。apache php mysql

二叉树and二叉查找树

1.png

关于树的相关术语：

节点： 树中的每个元素称为一个节点，

根节点： 位于整棵树顶点的节点，它没有父节点， 如上图 5

子节点： 其他节点的后代

叶子节点: 没有子节点的元素称为叶子节点， 如上图 3 8 24

二叉树：二叉树就是一种数据结构， 它的组织关系就像是自然界中的树一样。官方语言的定义是：是一个有限元素的集合,该集合或者为空、或者由一个称为根的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成。

二叉查找树：
二叉查找树也叫二叉搜索树（BST）,它只允许我们在左节点存储比父节点更小的值，右节点存储比父节点更大的值，上图展示的就是一颗二叉查找树。

代码实现

首先创建一个类来表示二叉查找树，它的内部应该有一个Node类，用来创建节点

  1.     function BinarySearchTree () {
  2.         var Node = function(key) {
  3.             this.key = key,
  4.             this.left = null,
  5.             this.right = null
  6.         }
  7.         var root = null
  8.     }

它还应该有一些方法：

  • insert(key) 插入一个新的键

  • inOrderTraverse() 对树进行中序遍历，并打印结果

  • preOrderTraverse() 对树进行先序遍历，并打印结果

  • postOrderTraverse() 对树进行后序遍历，并打印结果

  • search(key) 查找树中的键，如果存在返回true,不存在返回fasle

  • findMin() 返回树中的最小值

  • findMax() 返回树中的最大值

  • remove(key) 删除树中的某个键

向树中插入一个键

向树中插入一个新的键，首页应该创建一个用来表示新节点的Node类实例，因此需要new一下Node类并传入需要插入的key值，它会自动初始化为左右节点为null的一个新节点

然后，需要做一些判断，先判断树是否为空，若为空，新插入的节点就作为根节点，如不为空，调用一个辅助方法insertNode()方法，将根节点和新节点传入

  1.     this.insert = function(key) {
  2.         var newNode = new Node(key)
  3.         if(root === null) {
  4.             root = newNode
  5.         } else {
  6.             insertNode(root, newNode)
  7.         }
  8.     }

定义一下insertNode() 方法，这个方法会通过递归得调用自身，来找到新添加节点的合适位置

  1.     var insertNode = function(node, newNode) {
  2.         if (newNode.key <= node.key) {
  3.             if (node.left === null) {
  4.                 node.left = newNode
  5.             }else {
  6.                 insertNode(node.left, newNode)
  7.             }
  8.         }else {
  9.             if (node.right === null) {
  10.                 node.right = newNode
  11.             }else {
  12.                 insertNode(node.right, newNode)
  13.             }
  14.         }
  15.     }

完成中序遍历方法

要实现中序遍历，我们需要一个inOrderTraverseNode(node)方法，它可以递归调用自身来遍历每个节点

  1.     this.inOrderTraverse = function() {
  2.         inOrderTraverseNode(root)
  3.     }

这个方法会打印每个节点的key值，它需要一个递归终止条件————检查传入的node是否为null，如果不为空，就继续递归调用自身检查node的left、right节点
实现起来也很简单:

  1.     var inOrderTraverseNode = function(node) {
  2.         if (node !== null) {
  3.             inOrderTraverseNode(node.left)
  4.             console.log(node.key)
  5.             inOrderTraverseNode(node.right)
  6.         }
  7.     }

先序遍历、后序遍历

有了中序遍历的方法，只需要稍作改动，就可以实现先序遍历和后序遍历了
上代码：

这样就可以对整棵树进行中序遍历了

  1.     // 实现先序遍历
  2.     this.preOrderTraverse = function() {
  3.         preOrderTraverseNode(root)
  4.     }
  5.     var preOrderTraverseNode = function(node) {
  6.         if (node !== null) {
  7.             console.log(node.key)
  8.             preOrderTraverseNode(node.left)
  9.             preOrderTraverseNode(node.right)
  10.         }
  11.     }
  12.     // 实现后序遍历
  13.     this.postOrderTraverse = function() {
  14.         postOrderTraverseNode(root)
  15.     }
  16.     var postOrderTraverseNode = function(node) {
  17.         if (node !== null) {
  18.             postOrderTraverseNode(node.left)
  19.             postOrderTraverseNode(node.right)
  20.             console.log(node.key)
  21.         }
  22.     }

发现了吧，其实就是内部语句更换了前后位置，这也刚好符合三种遍历规则：先序遍历（根-左-右）、中序遍历（左-根-右）、中序遍历（左-右-根）

先来做个测试吧

现在的完整代码如下：

  1.     function BinarySearchTree () {
  2.         var Node = function(key) {
  3.             this.key = key,
  4.             this.left = null,
  5.             this.right = null
  6.         }
  7.         var root = null
  8.         
  9.         //插入节点
  10.         this.insert = function(key) {
  11.             var newNode = new Node(key)
  12.             if(root === null) {
  13.                 root = newNode
  14.             } else {
  15.                 insertNode(root, newNode)
  16.             }
  17.         }
  18.         var insertNode = function(node, newNode) {
  19.             if (newNode.key <= node.key) {
  20.                 if (node.left === null) {
  21.                     node.left = newNode
  22.                 }else {
  23.                     insertNode(node.left, newNode)
  24.                 }
  25.             }else {
  26.                 if (node.right === null) {
  27.                     node.right = newNode
  28.                 }else {
  29.                     insertNode(node.right, newNode)
  30.                 }
  31.             }
  32.         } 
  33.         
  34.         //实现中序遍历
  35.         this.inOrderTraverse = function() {
  36.             inOrderTraverseNode(root)
  37.         }
  38.         var inOrderTraverseNode = function(node) {
  39.             if (node !== null) {
  40.                 inOrderTraverseNode(node.left)
  41.                 console.log(node.key)
  42.                 inOrderTraverseNode(node.right)
  43.             }
  44.         }
  45.         // 实现先序遍历
  46.         this.preOrderTraverse = function() {
  47.             preOrderTraverseNode(root)
  48.         }
  49.         var preOrderTraverseNode = function(node) {
  50.             if (node !== null) {
  51.                 console.log(node.key)
  52.                 preOrderTraverseNode(node.left)
  53.                 preOrderTraverseNode(node.right)
  54.             }
  55.         }
  56.         // 实现后序遍历
  57.         this.postOrderTraverse = function() {
  58.             postOrderTraverseNode(root)
  59.         }
  60.         var postOrderTraverseNode = function(node) {
  61.             if (node !== null) {
  62.                 postOrderTraverseNode(node.left)
  63.                 postOrderTraverseNode(node.right)
  64.                 console.log(node.key)
  65.             }
  66.         }
  67.     }

竟然已经完成了添加新节点和遍历的方式，我们来测试一下吧：

定义一个数组，里面有一些元素

  1. var arr = [9,6,3,8,12,15]

我们将arr中的每个元素依此插入到二叉搜索树中，然后打印结果

  1.     var tree = new BinarySearchTree()
  2.     arr.map(item => {
  3.         tree.insert(item)
  4.     })
  5.     tree.inOrderTraverse()
  6.     tree.preOrderTraverse()
  7.     tree.postOrderTraverse()

运行代码后，我们先来看看插入节点后整颗树的情况：

1.png

输出结果

中序遍历：
3
6
8
9
12
15

先序遍历：
9
6
3
8
12
15

后序遍历：
3
8
6
15
12
9

很明显，结果是符合预期的，所以，我们用上面的JavaScript代码，实现了对树的节点插入，和三种遍历方法，同时，很明显可以看到，在二叉查找树树种，最左侧的节点的值是最小的，而最右侧的节点的值是最大的，所以二叉查找树可以很方便的拿到其中的最大值和最小值

查找最小、最大值

怎么做呢？其实只需要将根节点传入minNode/或maxNode方法，然后通过循环判断node为左侧(minNode)/右侧(maxNode)的节点为null

实现代码：

  1.     // 查找最小值
  2.     this.findMin = function() {
  3.         return minNode(root)
  4.     }
  5.     var minNode = function(node) {
  6.         if (node) {
  7.             while (node && node.left !== null) {
  8.                 node = node.left
  9.             }
  10.             return node.key
  11.         }
  12.         return null
  13.     }
  14.     
  15.     // 查找最大值
  16.     this.findMax = function() {
  17.         return maxNode(root)
  18.     }
  19.     var maxNode = function (node) {
  20.         if(node) {
  21.             while (node && node.right !== null) {
  22.                 node =node.right
  23.             }
  24.             return node.key
  25.         }
  26.         return null
  27.     }

所搜特定值

  1. this.search = function(key) {
  2.     return searchNode(root, key)
  3. }

同样，实现它需要定义一个辅助方法,这个方法首先会检验node的合法性，如果为null，直接退出，并返回fasle。如果传入的key比当前传入node的key值小，它会继续递归查找node的左侧节点，反之，查找右侧节点。如果找到相等节点，直接退出，并返回true

  1.     var searchNode = function(node, key) {
  2.         if (node === null) {
  3.             return false
  4.         }
  5.         if (key < node.key) {
  6.             return searchNode(node.left, key)
  7.         }else if (key > node.key) {
  8.             return searchNode(node.right, key)
  9.         }else {
  10.             return true
  11.         }
  12.     }

移除节点

移除节点的实现情况比较复杂，它会有三种不同的情况：


    • 需要移除的节点是一个叶子节点

    • 需要移除的节点包含一个子节点

    • 需要移除的节点包含两个子节点

    和实现搜索指定节点一元，要移除某个节点，必须先找到它所在的位置，因此移除方法的实现中部分代码和上面相同：

    1.     // 移除节点
    2.     this.remove = function(key) {
    3.         removeNode(root,key)
    4.     }
    5.     var removeNode = function(node, key) {
    6.         if (node === null) {
    7.             return null
    8.         }
    9.         if (key < node.key) {
    10.             node.left = removeNode(node.left, key)
    11.             return node
    12.         }else if(key > node.key) {
    13.             node.right = removeNode(node.right,key)
    14.             return node
    15.         }else{
    16.             //需要移除的节点是一个叶子节点
    17.             if (node.left === null && node.right === null) {
    18.                 node = null
    19.                 return node
    20.             }
    21.             //需要移除的节点包含一个子节点
    22.             if (node.letf === null) {
    23.                 node = node.right
    24.                 return node
    25.             }else if (node.right === null) {
    26.                 node = node.left
    27.                 return node
    28.             }
    29.             //需要移除的节点包含两个子节点
    30.             var aux = findMinNode(node.right)
    31.             node.key = aux.key
    32.             node.right = removeNode(node.right, axu.key)
    33.             return node
    34.         }
    35.     }
    36.     var findMinNode = function(node) {
    37.         if (node) {
    38.             while (node && node.left !== null) {
    39.                 node = node.left
    40.             }
    41.             return node
    42.         }
    43.         return null
    44.     }

    其中，移除包含两个子节点的节点是最复杂的情况，它包含左侧节点和右侧节点，对它进行移除主要需要三个步骤：

    1. 需要找到它右侧子树中的最小节点来代替它的位置

    2. 将它右侧子树中的最小节点移除

    3. 将更新后的节点的引用指向原节点的父节点

    有点绕儿，但必须这样，因为删除元素后的二叉搜索树必须保持它的排序性质

    测试删除节点

    1. tree.remove(8)
    2. tree.inOrderTraverse()

    打印结果：

    3
    6
    9
    12
    15

    8 这个节点被成功删除了，但是对二叉查找树进行中序遍历依然是保持排序性质的

    到这里，一个简单的二叉查找树就基本上完成了，我们为它实现了，添加、查找、删除以及先中后三种遍历方法

    存在的问题

    但是实际上这样的二叉查找树是存在一些问题的，当我们不断的添加更大/更小的元素的时候，会出现如下情况：

    1. tree.insert(16)
    2. tree.insert(17)
    3. tree.insert(18)

    来看看现在整颗树的情况：

    1.png

    看图片容易得出它是不平衡的，这又会引出平衡树的概念，要解决这个问题，还需要更复杂的实现，例如：AVL树，红黑树 哎，之后再慢慢去学习吧

    相关文章：

    二叉树遍历算法-php的示例

    二叉树的中序遍历,该怎么解决

以上就是js_前中后序二叉树遍历的三种算法_简单二叉树的实现的详细内容，更多请关注Gxl网其它相关文章！

人气教程排行

本站所有资源全部来源于网络，若本站发布的内容侵害到您的隐私或者利益，请联系我们删除！