如何用JavaScript将二叉搜索树改写为询问长尾词的算法？

本文共计3902个文字，预计阅读时间需要16分钟。

计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是其引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双向链表，每个节点包含一些数据以及指向左右子树的指针。

计算机科学中最常用和讨论最多的数据结构之一是二叉搜索树。这通常是引入的第一个具有非线性插入算法的数据结构。二叉搜索树类似于双链表，每个节点包含一些数据，以及两个指向其他节点的指针；它们在这些节点彼此相关联的方式上有所不同。二叉搜索树节点的指针通常被称为“左”和“右”，用来指示与当前值相关的子树。这种节点的简单 JavaScript 实现如下：

var node = { value: 125, left: null, right: null };

从名称中可以看出，二叉搜索树被组织成分层的树状结构。第一个项目成为根节点，每个附加值作为该根的祖先添加到树中。但是，二叉搜索树节点上的值是唯一的，根据它们包含的值进行排序：作为节点左子树的值总是小于节点的值，右子树中的值都是大于节点的值。通过这种方式，在二叉搜索树中查找值变得非常简单，只要你要查找的值小于正在处理的节点则向左，如果值更大，则向右移动。二叉搜索树中不能有重复项，因为重复会破坏这种关系。下图表示一个简单的二叉搜索树。

上图表示一个二叉搜索树，其根的值为 8。当添加值 3 时，它成为根的左子节点，因为 3 小于 8。当添加值 1 时，它成为 3 的左子节点，因为 1 小于 8（所以向左）然后 1 小于3（再向左）。当添加值 10 时，它成为跟的右子节点，因为 10 大于 8。不断用此过程继续处理值 6，4，7，14 和 13。此二叉搜索树的深度为 3，表示距离根最远的节点是三个节点。