JavaScript 中怎么实现一个二叉树算法

这篇文章将为大家详细讲解有关JavaScript 中怎么实现一个二叉树算法，文章内容质量较高，因此小编分享给大家做个参考，希望大家阅读完这篇文章后对相关知识有一定的了解。

二叉树和二叉搜索树介绍

二叉树中的节点最多只能有2个子节点，一个是左侧子节点，一个是右侧子节点，这样定义的好处是有利于我们写出更高效的插入，查找，删除节点的算法。二叉搜索树是二叉树的一种，但是它只允许你在左侧子节点存储比父节点小的值，但在右侧节点存储比父节点大的值。接下来我们将按照这个思路去实现一个二叉搜索树。

1. 创建BinarySearchTree类

这里我们将使用构造函数去创建一个类：

function BinarySearchTree(){     // 用于创建节点的类     let Node = function(key) {         this.key = key;         this.left = null;         this.right = null;     }     // 根节点     let root = null; }

我们将使用和链表类似的指针方式去表示节点之间的关系，如果不了解链表，请看我后序的文章《如何实现单向链表和双向链表》。

2.插入一个键

// 插入一个键 this.insert = function(key) {     let newNode = new Node(key);     root === null ? (root = newNode) : (insertNode(root, newNode)) }

向树中插入一个新的节点主要有以下三部分：1.创建新节点的Node类实例 --> 2.判断插入操作是否为根节点,是根节点就将其指向根节点 -->  3.将节点加入非根节点的其他位置。

insertNode的具体实现如下：

function insertNode(node, newNode){     if(newNode.key < node.key) {         node.left === null ? (node.left = newNode) : (insertNode(node.left, newNode))     }else {         node.right === null ? (node.right = newNode) : (insertNode(node.right, newNode))     } }

这里我们用到递归，接下来要实现的search，del等都会大量使用递归，所以说不了解的可以先自行学习了解。我们创建一个二叉树实例，来插入一个键：

let tree = new BinarySearchTree(); tree.insert(20); tree.insert(21); tree.insert(520); tree.insert(521);

插入的结构会按照二叉搜索树的规则去插入，结构类似于上文的第一个树图。

树的遍历

访问树的所有节点有三种遍历方式：中序，先序和后序。

• 中序遍历：以从最小到最大的顺序访问所有节点

• 先序遍历：以优先于后代节点的顺序访问每个节点

• 后序遍历：先访问节点的后代节点再访问节点本身

根据以上的介绍，我们可以有以下的实现代码。

1 中序排序

this.inOrderTraverse = function(cb){     inOrderTraverseNode(root, cb); }  // 辅助函数 function inOrderTraverseNode(node, cb){     if(node !== null){         inOrderTraverseNode(node.left, cb);         cb(node.key);         inOrderTraverseNode(node.right, cb);     } }

使用中序遍历可以实现对树进行从小到大排序的功能。

2 先序排序

// 先序排序 --- 优先于后代节点的顺序访问每个节点    this.preOrderTraverse = function(cb) {      preOrderTraverseNode(root, cb);    }     // 先序排序辅助方法    function preOrderTraverseNode(node, cb) {      if(node !== null) {        cb(node.key);        preOrderTraverseNode(node.left, cb);        preOrderTraverseNode(node.right, cb);      }    }

使用先序排序可以实现结构化输出的功能。

3 后序排序

// 后续遍历 --- 先访问后代节点，再访问节点本身    this.postOrderTraverse = function(cb) {      postOrderTraverseNode(root, cb);    }     // 后续遍历辅助方法    function postOrderTraverseNode(node, cb) {      if(node !== null){        postOrderTraverseNode(node.left, cb);        postOrderTraverseNode(node.right, cb);        cb(node.key);      }    }

后序遍历可以用于计算有层级关系的所有元素的大小。

搜索树中的值

在树中有三种经常执行的搜索类型：最大值，最小值，特定的值。

1 最小值

最小值通过定义可以知道即是左侧树的最底端的节点，具体实现代码如下：

// 最小值    this.min = function(){      return minNode(root)    }      function minNode(node) {      if(node) {        while(node && node.left !== null){          node = node.left;        }        return node.key      }      return null    }

相似的，实现最大值的方法如下：

// 最大值    this.max = function() {      return maxNode(root)    }     function maxNode(node) {      if(node){        while(node && node.right !== null){          node = node.right;        }        return node.key      }      return null    }

2.搜索一个特定的值

// 搜索树中某个值 this.search = function(key) {     return searchNode(root, key) }  // 搜索辅助方法 function searchNode(node, key){     if(node === null) {         return false     }     if(key < node.key) {         return searchNode(node.left, key)     } else if(key > node.key) {         return searchNode(node.right, key)     }else {         return true     } }

3 移除一个节点

this.remove = function(key){     root = removeNode(root, key); }  // 发现最小节点 function findMinNode(node) {     if(node) {     while(node && node.left !== null){         node = node.left;     }     return node     }     return null }  // 移除节点辅助方法 function removeNode(node, key) {     if(node === null) {     return null     }      if(key < node.key){     node.left = removeNode(node.left, key);     return node     } else if( key > node.key){     node.right = removeNode(node.right, key);     return node     } else {     // 一个页节点     if(node.left === null && node.right === null) {         node = null;         return node     }      // 只有一个子节点的节点     if(node.left === null) {         node = node.right;         return node     }else if(node.right === null) {         node = node.left;         return node     }      // 有两个子节点的节点     let aux = findMinNode(node.right);     node.key = aux.key;     node.right = removeNode(node.right, aux.key);     return node     } }

删除节点需要考虑的情况比较多，这里我们会使用和min类似的实现去写一个发现最小节点的函数，当要删除的节点有两个子节点时，我们要将当前要删除的节点替换为子节点中最大的一个节点的值，然后将这个子节点删除。

关于JavaScript 中怎么实现一个二叉树算法就分享到这里了，希望以上内容可以对大家有一定的帮助，可以学到更多知识。如果觉得文章不错，可以把它分享出去让更多的人看到。