这篇文章主要介绍了如何使用JavaScript实现二叉搜索树算法，具有一定借鉴价值，感兴趣的朋友可以参考下，希望大家阅读完这篇文章之后大有收获，下面让小编带着大家一起了解一下。

在编码面试中很常见，BST（Binary search tree） 是一种树状数据结构，顶部有一个根。它们是存储数值的好方法，因为它们的有序性质允许快速搜索和查找。

与普通树相比，BST 具有以下特性：

每个左孩子的值都比其父母小

每个右孩子的值都比它的父母大

每个节点可以包含 0 到 2 个子节点。

下图应该更清楚地说明事情。

我们通常在 Javascript 中定义一个二叉树节点，函数如下：

functionTreeNode(val,left,right){this.val=valthis.left=leftthis.right=right}二叉树基本遍历（中序、后序、前序）

首先要知道如何遍历 BST 的每个节点。这允许我们在 BST 的所有节点上执行一个功能。例如，如果我们想在 BST 中找到一个值，我们就需要节点。

有三种主要方法可以做到这一点。幸运的是，他们有共同的主题。

递归算法是开始使用二叉树中序遍历的最简单方法。思路如下：

如果节点为空，则什么都不做——否则，递归调用节点左子节点上的函数。

然后，遍历完所有左子节点后，对节点进行一些操作。我们当前的节点保证是最左边的节点。

最后，调用 node.right 上的函数。

Inorder 算法从左、中、右遍历树节点。

/***@param{TreeNode}root*/constinorder=(root)=>{constnodes=[]if(root){inorder(root.left)nodes.push(root.val)inorder(root.right)}returnnodes}//forourexampletree,thisreturns[1,2,3,4,5,6]后序遍历

递归算法是开始后序遍历的最简单方法。

如果节点为空，则什么都不做——否则，递归调用节点左子节点上的函数。

当没有更多的左孩子时，调用 node.right 上的函数。

最后，在节点上做一些操作。

后序遍历从左、右、中访问树节点。

/***@param{TreeNode}root*/constpostorder=(root)=>{constnodes=[]if(root){postorder(root.left)postorder(root.right)nodes.push(root.val)}returnnodes}//forourexampletree,thisreturns[1,3,2,6,5,4]前序遍历

递归算法是开始前序遍历的最简单方法。

如果节点为空，则什么都不做——否则，在节点上做一些操作。

遍历节点的左子节点并重复。

遍历到节点的右孩子并重复。

后序遍历从中、左、右访问树节点。

/***@param{TreeNode}root*/constpreorder=(root)=>{constnodes=[]if(root){nodes.push(root.val)preorder(root.left)preorder(root.right)}returnnodes}//forourexampletree,thisreturns[4,2,1,3,5,6]什么是有效的二叉搜索树？

有效的二叉搜索树 (BST) 具有所有值小于父节点的左子节点，以及值大于父节点的所有右子节点。

要验证一棵树是否是有效的二叉搜索树：

定义当前节点可以具有的最小值和最大值

如果节点的值不在这些范围内，则返回 false

递归验证节点的左孩子，最大边界设置为节点的值

递归验证节点的右孩子，最小边界设置为节点的值

/***@param{TreeNode}root*/constisValidBST=(root)=>{consthelper=(node,min,max)=>{if(!node)returntrueif(node.val<=min||node.val>=max)returnfalsereturnhelper(node.left,min,node.val)&&helper(node.right,node.val,max)}returnhelper(root,Number.MIN_SAFE_INTEGER,Number.MAX_SAFE_INTEGER)}如何找到二叉树最大深度

在这里，算法试图找到我们 BST 的高度/深度。换句话说，我们正在查看 BST 包含多少个“级别”。

如果节点为空，我们返回 0 因为它没有添加任何深度

否则，我们将 + 1 添加到我们当前的深度（我们遍历了一层）

递归计算节点子节点的深度并返回node.left和node.right之间的最大和

/***@param{TreeNode}root*/constmaxDepth=function(root){constcalc=(node)=>{if(!node)return0returnMath.max(1+calc(node.left),1+calc(node.right))}returncalc(root)};如何找到两个树节点之间的最小公共祖先

让我们提高难度。我们如何在我们的二叉树中找到两个树节点之间的共同祖先？让我们看一些例子。

在这棵树中，3和1的最低共同祖先是2。3和2的LCA是2。6和1和6的LCA是4。

看到这里的模式了吗？两个树节点之间的 LCA 要么是节点本身之一（3 和 2 的情况），要么是父节点，其中第一个子节点位于其左子树中的某处，而第二个子节点位于其右子树中的某处。

寻找两个树节点 p 和 q 之间的最低共同祖先（LCA）的算法如下：

验证是否在左子树或右子树中找到 p 或 q

然后，验证当前节点是 p 还是 q

如果在左子树或右子树中找到 p 或 q 之一，并且 p 或 q 之一是节点本身，我们就找到了 LCA

如果在左子树或右子树中都找到了 p 和 q，我们就找到了 LCA

/***@param{TreeNode}root*@param{TreeNode}p*@param{TreeNode}q*/constlowestCommonAncestor=function(root,p,q){letlca=nullconstisCommonPath=(node)=>{if(!node)returnfalsevarisLeft=isCommonPath(node.left)varisRight=isCommonPath(node.right)varisMid=node==p||node==qif(isMid&&isLeft||isMid&&isRight||isLeft&&isRight){lca=node}returnisLeft||isRight||isMid}isCommonPath(root)returnlca};

感谢你能够认真阅读完这篇文章，希望小编分享的“如何使用JavaScript实现二叉搜索树算法”这篇文章对大家有帮助，同时也希望大家多多支持亿速云，关注亿速云行业资讯频道，更多相关知识等着你来学习!