什么是二叉樹

二叉樹就是樹的每個節點最多只能有兩個子節點

什么是二叉搜索樹

二叉搜索樹在二叉樹的基礎上，多了一個條件，就是二叉樹在插入值時，若插入值比當前節點小，就插入到左節點，否則插入到右節點；若插入過程中，左節點或右節點已經存在，那么繼續按如上規則比較，直到遇到一個新的節點。

二叉搜索樹的特性

二叉搜索樹由于其獨特的數據結構，使得其無論在增刪，還是查找，時間復雜度都是O(h)，h為二叉樹的高度。因此二叉樹應該盡量的矮，即左右節點盡量平衡。

二叉搜索樹的構造

要構造二叉搜索樹，首先要構造二叉樹的節點類。由二叉樹的特點可知，每個節點類都有一個左節點，右節點以及值本身，因此節點類如下：

class Node { constructor(key) {  this.key = key;  this.left = null;  this.right = null; }}

接著構造二叉搜索樹

class Tree{ constructor(param = null) {  if (param) {   this.root = new Node(param);  } else {   this.root = null;  } }}

這里this.root就是當前對象的樹。

二叉搜索樹的新增

由二叉搜索樹左子樹比節點小，右子樹別節點大的特點，可以很簡單的寫出二叉搜索樹新增的算法，如下：

insert(key) { if (this.root === null) {  this.root = new Node(key); } else {  this._insertNode(this.root, key); }}_insertNode(node, key) { if (key < node.key) {  if (node.left === null) {   node.left = new Node(key);{1}  } else {   this._insertNode(node.left, key);{2}  } } else if (key > node.key) {  if (node.right === null) {   node.right = new Node(key);{3}  } else {   this._insertNode(node.right, key);{4}  } }}

如上代碼先判斷新增的key與當前節點的key大小，如果小，就遞歸遍歷左子節點，直到找到一個為null的左子節點；如果比當前節點大同理。如上代碼{1}{2}{3}{4}之所以能改變this.root的值，是由于JavaScript函數是按值傳遞，而當參數是非基本類型時，例如這里的對象，其對象的值為內存，因此每次都會直接改變this.root的內容。

二叉搜索樹的遍歷

二叉搜索樹分為先序、中序、后序三種遍歷方式。

inOrderTraverse(callback) { this._inOrderTraverse(this.root, callback);}_inOrderTraverse(node, callback) { if (node) {  this._inOrderTraverse(node.left, callback);  callback(node.key);  this._inOrderTraverse(node.right, callback); }}

如上是中序遍歷。

這里需要理解的一點是遞歸。要知道，函數的執行可以抽象為一種數據結構——棧。針對函數的執行，會維護一個棧，來存儲函數的執行。函數在每一次遞歸時，都會將當前的執行環境入棧并記錄執行的位置。以上述代碼為例，有如下一個數據