前言：

二叉樹的特點(diǎn)(例圖只是二叉樹的一種情況，不要嘗試用例圖推理以下結(jié)論)

• 除了最下面一層，每個(gè)節(jié)點(diǎn)都是父節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都有且最多有兩個(gè)子節(jié)點(diǎn)；
• 除了嘴上面一層，每個(gè)節(jié)點(diǎn)是子節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)都會(huì)有一個(gè)父節(jié)點(diǎn)；
• 最上面一層的節(jié)點(diǎn)（即例圖中的節(jié)點(diǎn)50）為根節(jié)點(diǎn)；

• 最下面一層的節(jié)點(diǎn)稱為葉子節(jié)點(diǎn)，他們沒有子節(jié)點(diǎn)；

  
  
• 左子節(jié)點(diǎn)的值 < 父節(jié)點(diǎn)的值 <= 右節(jié)點(diǎn)的值

1 節(jié)點(diǎn)的javascript實(shí)現(xiàn)

// 節(jié)點(diǎn)對象
function Node(data, left, right) {
   this.data = data;  // 節(jié)點(diǎn)值
   this.left = left;  // 當(dāng)前節(jié)點(diǎn)的左子節(jié)點(diǎn)
   this.right = right;  // 當(dāng)前節(jié)點(diǎn)的右子節(jié)點(diǎn)
   this.show = show;  // 輔助function
}

function show() {
   return this.data;
}

感受下上面實(shí)現(xiàn)節(jié)點(diǎn)的代碼，感覺和鏈表有點(diǎn)相似不是嗎，存著當(dāng)前值，又存著下個(gè)節(jié)點(diǎn)（左、右子節(jié)點(diǎn)）的引用，下面是一張偽代碼的草圖：

2 二叉樹的實(shí)現(xiàn)
實(shí)現(xiàn)二叉樹，當(dāng)然就是要插入節(jié)點(diǎn)構(gòu)成二叉樹，先看看實(shí)現(xiàn)二叉樹的js代碼

function BST() {
   this.root = null;
   this.insert = insert;
}

function insert(data) {
   var n = new Node(data, null, null);
   if (this.root == null) {
      this.root = n;
   }
   else {
      var current = this.root;
      var parent;
      while (true) {
         parent = current;
         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;
            }
         }
      }
   }
}

然后是看一下偽代碼：

function BST() {
   this.root = null;  // 根節(jié)點(diǎn)
   this.insert = insert;
}

function insert(data) {
   // 初始化一個(gè)節(jié)點(diǎn)，為什么要將左右子節(jié)點(diǎn)的引用初始化為空呢，因?yàn)榭赡苁侨~子節(jié)點(diǎn)，加入他有子節(jié)點(diǎn)，會(huì)在下面的代碼添加
   var n = new Node(data, null, null);
   if (該二叉樹是否為空，是空則根節(jié)點(diǎn)為空，因此可以用根節(jié)點(diǎn)判斷二叉樹是否為空) {
      // 將當(dāng)前節(jié)點(diǎn)存為根節(jié)點(diǎn)
      this.root = n;
   }
   else {
      // 來到這里就表示，該二叉樹不為空，這里關(guān)鍵的是兩句代碼：
      // 0.while (true);
      // 1.parent = current；
      // 2.current = current.left;/current = current.right;
      // 3.break;
      var current = this.root;
      var parent;
      while (true) {
         parent = current;  // 獲得父節(jié)點(diǎn)，第一次循環(huán)，那么父節(jié)點(diǎn)就是根節(jié)點(diǎn)
         if (data < current.data) {  // 當(dāng)前節(jié)點(diǎn)值小于父節(jié)點(diǎn)的值就是存左邊，記得二叉樹的特點(diǎn)吧，如果真是小于父節(jié)點(diǎn)，那么就說明該節(jié)點(diǎn)屬于，該父節(jié)點(diǎn)的左子樹。
            current = current.left;
            if (current == null) {
               parent.left = n;
               break;
            }

            // 其實(shí)上面這樣寫不好理解，可以等價(jià)于下面的代碼：
            // start
            if(current.left == null){  // 若果左節(jié)點(diǎn)空，那么這個(gè)空的節(jié)點(diǎn)就是我們要插入的位置
                current.left = n;
                break;
            }else{
                // 不空則繼續(xù)往下一層找空節(jié)點(diǎn)（插入的位置）
                current = current.left;
            }
            // end
         }
         else {
            // 右節(jié)點(diǎn)的邏輯代碼個(gè)左節(jié)點(diǎn)的一樣的
            current = current.right;
            if (current == null) {
               parent.right = n;
               break;
            }
         }
      }
   }
}

下面是一個(gè)更好理解的插入函數(shù)

function insert(data) {
   var n = new Node(data, null, null);
   if (this.root == null) {
      this.root = n;
   }
   else {
      var current = this.root;
      // start change
      while (true) {
         if (data < current.data) {
            if (current.left == null) {
               current.left = n;
               break;
            }else{
               current = current.left;
            }
         }else {
            if (current.right == null) {
               current.right = n;
               break;
            }else{
               current = current.right;
            }
         }
      }
   }
}

小結(jié)：
二叉樹的實(shí)現(xiàn)的三個(gè)部件

• Node對象

function Node(data, left, right) { ... }

• BST對象

function BST() { ... }

• 插入節(jié)點(diǎn)函數(shù)

function insert(data) { ... }