用js来实现那些数据结构-方法（二）

前一篇文章我们学会了第一个非顺序数据结构hashMap，那么这一篇我们来学学树，包括树的概念和一些相关的术语以及二叉搜索树的实现。唉?为什么不是树的实现，不是二叉树的实现。偏偏是二叉搜索树的实现?嗯，别急。我们一点一点循序渐进。

部分内容 由 小红书（www.xiaohongshutuiguang.cn）转载提供

我们先来了解一下什么是树。树是一种非线性数据结构，直观的看，它是数据元素(在树中称为节点)按分支关系组织起来的结构，很像自然界中的树那样。在现实生活中，最常见的例子就是家谱或者公司的组织架构图。就像是这样：

那么我们还要知道树的一些相关术语，比较多，大家要仔细阅读，不然后面就完全懵逼了。我们先来看一下树这种数据结构的图示。

这是我在百度上找到的一张图，还算清晰明了。这就是树数据结构了。

首先，一个树结构，存在一系列的父子关系，除了顶部的第一个节点以外，每一个结点都有一个父节点以及零个或多个子节点。位于树顶部的节点叫做根节点。看上图，根节点就是A。树中的每一个元素(A,B,C,D,E,F这些)都叫做节点。节点又分为内部节点和外部节点。至少有一个子节点的节点称为内部节点(如上图的A,B,C,E)。没有子节点的节点称为外部节点或叶节点(如上图的D,F,G)。

另一个概念是子树，定义是这样的：子树由节点和它的后代构成。也就是说，把树中的一部分剖离出来，它仍旧可以看作是是一颗单独的树，那么就可以称之为子树。

节点还有一个属性，叫做度，也可以叫做深度，节点的深度取决于它有多少个祖先节点。如上图的H，深度就是3，因为它有E,B,A三个祖先节点。E的深度就是2。

除了节点的深度，一棵树还可以被分解层级。根节点是第0层，根节点的子节点是第1层。以此类推。

那么我们对树的概念有了简单的了解，那么什么是二叉树呢?其实不论是二叉树，还是二叉搜索树，又或者是其它什么树，只不过是在树的基础上加上一个限制条件以便更高效率的操作。

在二叉树中，一个节点的子节点最多只能有两个节点，一个左节点，一个右节点，二叉树只能是左右分叉的，所以叫做二叉树。

那二叉搜索树(BST)呢?不过是在二叉树的基础上，又加了一个插入元素的条件，就是，只允许你在左侧节点存储比父节点小的值，在右侧节点存储大于或等于父节点的值。这里要注意的一点是，二叉树的子节点最多只能有两个节点，也就说不一定非要有两个节点，只有一个左节点，或者只有一个右节点都是可以的可能的允许的。

那么似乎我们不去实现树，也不去实现二叉树，而是直接实现二叉搜索树的原因就出来了。只要我们学会了二叉搜索树，自然树和二叉树的实现也就会了。

来，我们来看图说话，在开始实现二叉搜索树之前，先给大家放张图(图片百度的)，以便大家更好的理解。

既然图有了，我们就来看看如何实现一个BinarySearchTree。首先，要告诉大家的是，在链表中，我们称每一个节点本身称作节点，但是在树中，我们叫它键。唉?我好像看到了链表?树跟链表有毛关系?嗯。。。确实没关系，但是我们要实现树的方式却跟链表有关系。我们之前学习过双向链表，双向链表中有prev和next，分别指向当前节点的上一个和下一个节点。树的实现我们也要借用类似的方式，只不过是一个指向左侧子节点，另一个指向右侧子节点。

那么我们都要实现哪些方法呢?

1、insert(key)：像树中插入一个新的键。

2、search(key)：在树中查找一个键。

3、inOrderTraverse：中序遍历。

4、preOrderTraverse：先序遍历。

5、postOrderTraverse：后序遍历。

6、min：返回树中最小的值/键。

7、max：返回树中最大的值/键。

8、remove(key)：从树中移除某个键。

我们知道了基本的实现方式和BinarySearchTree需要的方法。我们开始吧。