樹是一種非線性的數(shù)據(jù)結(jié)構(gòu)，以分層的方式存儲數(shù)據(jù)。樹被用來存儲具有層級關(guān)系的結(jié)構(gòu)，比如文件系統(tǒng)中的文件；樹還被用來存儲有序列表。

1. 二叉樹與二叉查找樹
   二叉樹是一種特殊的樹，它的子節(jié)點個數(shù)不超過兩個；一個父節(jié)點的兩個子節(jié)點分別稱為左節(jié)點和右節(jié)點。
   二叉查找樹(BST)是一種特殊的二叉樹；相對較小的值保持在左節(jié)點中，較大的值保存在右節(jié)點中。

2. js代碼實現(xiàn)二叉查找樹

• 首先我們先定義一個Node對象，用于保存數(shù)據(jù)(data)，也保存和其他節(jié)點的鏈接（left和right）。

function Node(data,left,right) {
  this.data = data;
  this.left = left;
  this.right = right;
  this.show = show;
}

• 定義show方法

function show() {
  return this.data;
}

• 創(chuàng)建一個類，用來表示二叉查找樹(BST)

function BST() {
  //將根節(jié)點初始化為null
  this.root = null;
  //insert方法用來向樹中加入新節(jié)點
  this.insert = insert;
  //inOrder方法用來遍歷樹
  this.inOrder = inOrder;
}

• 定義insert方法

function insert(data) {
  //首先實例化一個新的Node對象
  var n = new Node(data,null,null);
  //檢查BST是否有根節(jié)點，如果沒有，那么是顆新樹，傳入的該節(jié)點就是根節(jié)點
  if(this.root == null) {
    this.root = n;
  }else {
    //反之就定義一個current變量用于保存當前節(jié)點（根節(jié)點）
    var current = this.root;
    var parent;
    while(true) {
      parent = current;
      //如果插入的節(jié)點保存的數(shù)據(jù)小于當前節(jié)點，且當前節(jié)點的左節(jié)點為null，就將這個新的節(jié)點插入到這個位置
      if(data < current.data) {
        current = current.left;
        if(current == null) {
          parent.left = n;
          break;
        }
      }else {
        //反之，同理
        current = current.right;
        if(current == null) {
          parent.right = n;
          break;
        }
      }
    }
  }
}

3. 遍歷二叉查找樹
   有三種遍歷BST的方式
   中序：中序遍歷按照節(jié)點上的鍵值，以升序訪問BST上的所有節(jié)點。
   先序：先序遍歷先訪問根節(jié)點，然后以同樣的方式訪問左子樹和右子樹。
   后序：后序遍歷先訪問葉子節(jié)點(沒有任何子節(jié)點的節(jié)點)，從左子樹到右子樹，再到根節(jié)點。
   這三種遍歷理解了一種的實現(xiàn)代碼，其他的都好理解，所以我著重寫一下我對js代碼實現(xiàn)中序遍歷過程的具體理解。

• js代碼實現(xiàn)中序遍歷
  中序遍歷使用遞歸的方式，以升序訪問樹中所有節(jié)點，先訪問左子樹，在訪問根節(jié)點，最后訪問右子樹。

function inOrder(node) {
  if(!(node == null)) {
    inOrder(node.left);
    console.log(node.show());
    inOrder(node.right);      
  }
}
//比如：
var nums = new BST();
nums.insert(56);
nums.insert(22);
nums.insert(81);
nums.insert(10);
nums.insert(30);
nums.insert(77);
nums.insert(92);

inOrder(nums.root); //10 22 30 56 81 77 92

①先遞歸遍歷左子樹到盡頭，將每一項push到一個數(shù)組中，先是得到這樣的一個結(jié)果[56,22,10]。

②遞歸完成了，現(xiàn)在pop出第一項即10開始遍歷右子樹,為undefined。

③然后pop出第二項即22，遍歷右子樹，得30，因為console是在先遞歸左子樹后打印的，所以把30插到(push)56和22中間，結(jié)果為[56,30,22,10]。

④然后pop出第三項即30，undefined。

⑤然后pop出第四項即56，遍歷該右子樹，得結(jié)果[92,81,56,30,22,10]

⑥然后pop出第五項即81，發(fā)現(xiàn)有左子樹77，所以push進去，又因為console代碼在中間，所以要放到92和81中間，結(jié)果[92,81,77,56,30,22,10]所以最后打印結(jié)果為10,22,30,56,77,81,92

理解了一個，后面的先序遍歷和后序遍歷就沒問題了，只是console代碼放置的位置不同。主要是理解遞歸。

• 先序遍歷

function inOrder(node) {
  if(!(node == null)) {
    console.log(node.show());
    inOrder(node.left);
    inOrder(node.right);      
  }
}
inOrder(nums.root);

• 后序遍歷

function inOrder(node) {
  if(!(node == null)) {
    inOrder(node.left);
    inOrder(node.right);      
    console.log(node.show());
  }
}
inOrder(nums.root);

參考學習：

《數(shù)據(jù)結(jié)構(gòu)與算法JavaScript描述》
《高程》