前端: JavaScript 中的二叉树算法实现
圣 诞 快 乐 接下来让我们一起来探讨js数据结构中的树。这里的树类比现实生活中的树，有树干，树枝，在程序中树是一种数据结构，对于存储需要快速查找的数据非有用，它是一种分层数据的抽象模型。一个树结构包含一系列存在父子关系的节点。每个节点都有一个父节点以及零个或多个子节点。如下所以为一个树结构：） 和树相关的概念：1. 子树：由节点和他的后代构成，如上图标示处。2. 深度：节点的深度取决于它祖节点的数量，比如节点5有2个祖节点，他的深度为2。3. 高度：树的高度取决于所有节点深度的最大值。 二叉树和二叉搜索树介绍 二叉树中的节点最多只能有2个子节点，一个是左侧子节点，一个是右侧子节点，这样定义的好处是有利于我们写出更高效的插入，查找，删除节点的算法。 二叉搜索树是二叉树的一种，但是它只允许你在左侧子节点存储比父节点小的值，但在右侧节点存储比父节点大的值。接下来我们将按照这个思路去实现一个二叉搜索树。 1. 创建BinarySearchTree类 这里我们将使用构造函数去创建一个类： functionBinarySearchTree(){//用于创建节点的类letNode=function(key){this.key=key;this.left=null;this.right=null;}//根节点letroot=null;} 我们将使用和链表类似的指针方式去表示节点之间的关系，如果不了解链表，请看我后序的文章《如何实现单向链表和双向链表》。 2.插入一个键 //插入一个键this.insert=function(key){letnewNode=newNode(key);root===null?(root=newNode):(insertNode(root,newNode))} 向树中插入一个新的节点主要有以下三部分：1.创建新节点的Node类实例 --> 2.判断插入操作是否为根节点,是根节点就将其指向根节点 --> 3.将节点加入非根节点的其他位置。 insertNode的具体实现如下： functioninsertNode(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等都会大量使用递归，所以说不了解的可以先自行学习了解。我们创建一个二叉树实例，来插入一个键： lettree=newBinarySearchTree();tree.insert(20);tree.insert(21);tree.insert(520);tree.insert(521); 插入的结构会按照二叉搜索树的规则去插入，结构类似于上文的第一个树图。 树的遍历 访问树的所有节点有三种遍历方式：中序，先序和后序。 中序遍历：以从最小到最大的顺序访问所有节点 先序遍历：以优先于后代节点的顺序访问每个节点 后序遍历：先访问节点的后代节点再访问节点本身 根据以上的介绍，我们可以有以下的实现代码。 中序排序 this.inOrderTraverse=function(cb){inOrderTraverseNode(root,cb);}//辅助函数functioninOrderTraverseNode(node,cb){if(node!==null){inOrderTraverseNode(node.left,cb);cb(node.key);inOrderTraverseNode(node.right,cb);}} 使用中序遍历可以实现对树进行从小到大排序的功能。 先序排序 //先序排序---优先于后代节点的顺序访问每个节点this.preOrderTraverse=function(cb){preOrderTraverseNode(root,cb);}//先序排序辅助方法functionpreOrderTraverseNode(node,cb){if(node!==null){cb(node.key);preOrderTraverseNode(node.left,cb);preOrderTraverseNode(node.right,cb);}} 使用先序排序可以实现结构化输出的功能。 后序排序 //后续遍历---先访问后代节点，再访问节点本身this.postOrderTraverse=function(cb){postOrderTraverseNode(root,cb);}//后续遍历辅助方法functionpostOrderTraverseNode(node,cb){if(node!==null){postOrderTraverseNode(node.left,cb);postOrderTraverseNode(node.right,cb);cb(node.key);}} 后序遍历可以用于计算有层级关系的所有元素的大小。 搜索树中的值 在树中有三种经常执行的搜索类型：最大值，最小值，特定的值。 最小值 最小值通过定义可以知道即是左侧树的最底端的节点，具体实现代码如下： //最小值this.min=function(){returnminNode(root)}functionminNode(node){if(node){while(node&&node.left!==null){node=node.left;}returnnode.key}returnnull} 相似的，实现最大值的方法如下： //最大值this.max=function(){returnmaxNode(root)}functionmaxNode(node){if(node){while(node&&node.right!==null){node=node.right;}returnnode.key}returnnull} 2.搜索一个特定的值 //搜索树中某个值this.search=function(key){returnsearchNode(root,key)}//搜索辅助方法functionsearchNode(node,key){if(node===null){returnfalse}if(key<node.key){returnsearchNode(node.left,key)}elseif(key>node.key){returnsearchNode(node.right,key)}else{returntrue}} 移除一个节点 this.remove=function(key){root=removeNode(root,key);}//发现最小节点functionfindMinNode(node){if(node){while(node&&node.left!==null){node=node.left;}returnnode}returnnull}//移除节点辅助方法functionremoveNode(node,key){if(node===null){returnnull}if(key<node.key){node.left=removeNode(node.left,key);returnnode}elseif(key>node.key){node.right=removeNode(node.right,key);returnnode}else{//一个页节点if(node.left===null&&node.right===null){node=null;returnnode}//只有一个子节点的节点if(node.left===null){node=node.right;returnnode}elseif(node.right===null){node=node.left;returnnode}//有两个子节点的节点letaux=findMinNode(node.right);node.key=aux.key;node.right=removeNode(node.right,aux.key);returnnode}} 删除节点需要考虑的情况比较多，这里我们会使用和min类似的实现去写一个发现最小节点的函数，当要删除的节点有两个子节点时，我们要将当前要删除的节点替换为子节点中最大的一个节点的值，然后将这个子节点删除。 至此，一个二叉搜索树已经实现，但是还存在一个问题，如果树的一遍非常深，将会存在一定的性能问题，为了解决这个问题，我们可以利用AVL树，一种自平衡二叉树，也就是说任何一个节点的左右两侧子树的高度之差最多为1。 如果想学习更多js算法和数据结构，可以继续观看哦~ 点个在看，你最好看 本文分享自微信公众号 - 趣谈前端（beautifulFront）。如有侵权，请联系 support@oschina.cn 删除。本文参与“OSC源创计划”，欢迎正在阅读的你也加入，一起分享。
