摘要：第二步自終止，第三步自調用，第四步回調函數會重復進行，直到我們遍歷到樹的所有節點。執行回調函數，傳入賦值為第二層第二個子節點。

本文譯自Cho S. Kim的文章：Data Structures With JavaScript: Tree

“樹”，是web開發中最常用的數據結構之一。這句話對開發者和用戶來講，都適用：開發人員通過HTML創造了一個DOM，用戶則通過DOM消費網絡信息。

進一步講，您正在閱讀的本文也是以樹的形式在瀏覽器中渲染的。文章中的段落由

標簽中的文字所代表；

標簽嵌套在元素中，而元素則是的子元素。

數據的嵌套類似一個家譜：元素是一個爹爹，元素是一個孩兒，

元素則是元素的孩兒。如果你感覺這種類比容易理解，那么在接下來實現一棵樹的過程中，更多的類比對你來說應該也不成問題。

在本文中，我們將創建一顆有兩種遍歷方式的樹：Depth-First-Search(DFS)深度優先搜索，和Breadth-First-Search(BFS)寬度優先搜索（遍歷是指訪問樹的每一個節點）。這兩種遍歷方式各自強調了對一顆樹操作的不同姿勢；而且他們用到了我們之前提過的（ 沒翻，去找原文 ）數據結構：DFS用到了棧，BFS用到了隊列。

樹，是一種使用節點來模擬分等級（層次）數據的數據結構。節點存儲數據，并指向其他節點（每個節點都存儲有自身數據，和指向其它節點的指針）。部分讀者可能對節點、指針等術語不太熟悉，所以我們這里做一個類比：把一棵樹比作一個組織結構。這個組織結構有一個最高負責人（根節點），比如說總經理。緊跟著就是在其之下的職位，比如說一個副總。

我們用一個從老總指向副總的箭頭來表示這種關系。老總 → 副總。一個職位（老總），就是一個節點；老總和副總之間的關系（箭頭），就是指針。在組織結構圖中創建更多的類似關系，只需要重復上面的步驟，一個節點指向另外一個節點。

在概念上，我希望節點和指針能夠講得通。在實踐上，我們再可以舉一個DOM的栗子。一個DOM的根節點就是，它指向了和。然后重復下去生成一顆DOM樹。

這么搞最贊的一點就是它具有嵌套節點的能力：一個

，內部可以有n個
• 節點，每個
• 也可以有兄弟
• 節點。（作者發出了奇怪的贊美）
  對樹進行操作

  樹跟節點可以用兩個多帶帶的構造器來描述：Node和Tree。

  Node

  data存儲一個值

  parent指向這個節點的父節點

  children指向表中的下一個節點 （這個可能有一堆，那么可能是一個數組）

  Tree

  _root指向這個樹的根節點

  traverseDF(callback)使用DFS遍歷樹的節點

  traverseBF(callback)使用BFS遍歷樹的節點

  contains(data,traversal)在樹里面搜索一個節點

  add(data,toData,traverse)向樹添加一個節點

  remove(child,parent)刪除樹的一個節點

  實現一棵樹

  下面開始寫代碼！

  節點Node的屬性

  function Node(data) {
      this.data = data;
      this.parent = null;
      this.children = [];
  }

  每個Node的實例都包含三個屬性，data，parent和children。第一個屬性保存跟這個節點有關的數據，比如“村長”。第二個屬性指向一個節點（在js中，就是等于號，比如this.parent = someOtherNode 這個就實現指針了好吧。什么值傳遞就不細展開了。其他算法中的指針實現也類似。）。

  function Tree(data) {
      var node = new Node(data);
      this._root = node;
  }

  Tree包含兩行代碼，第一行創建了一個Node的實例node，第二行把這個node賦值給了this._root。就是對一個樹進行了初始化，給了它一個根節點。
  Tree和Node的定義只需要很少的代碼，但是這些代碼已經足夠我們模擬一個有層次的數據結構。為了說明這一點，我們可以通過用一點測試數據來創建Tree的實例（間接也創建了Node的實例）：

  var tree = new Tree("CEO");
  
  
  tree._root;
  // 返回{data: "CEO", parent: null, children: []}

  有parent和children的存在，我們可以把節點添加為_root的子節點，同時把這些子節點的父節點賦值為_root。

  樹的方法

  接下來，我們給樹添加下面這5個方法：

  Tree

  traverseDF(callback)

  traverseBF(callback)

  contains(data,traversal)

  add(child,parent)

  remove(node,parent)

  這些方法都需要對樹進行遍歷，我們首先來實現遍歷方法（們）。

  第一個: traverseDF(callback)

  對樹進行深度優先遍歷：

  Tree.prototype.traverseDF = function(callback) {
  
      // 一個遞歸，立即執行函數
      (function recurse(currentNode) {
          // 第二步
          for (var i = 0, length = currentNode.children.length; i < length; i++) {
              // 第三步
              recurse(currentNode.children[i]);
          }
  
          // 第四步
          callback(currentNode);
  
          // 首先執行
      })(this._root);
  
  };

  traverseDF(callback)有一個callback參數，顧名思義，callback是一個稍后會在traverseDF(callback)內調用的函數。

  traverseDF(callback)內包含了一個叫做recurse的函數。recurse的意思是遞歸，這是一個遞歸函數，用人話說就是這個函數會調用自己，然后（特定條件下）自動結束。注意上面代碼注釋中的第*步，我會用他們來描述一下recurse函數是怎么遍歷到整棵樹的：

  首先執行： recurse，以樹的根節點作為參數。此時，currentNode指向這個根節點。

  第二步： 進入到一個for循環，對currentNode（比如說根節點）的每一個子節點進行迭代，從第一個開始。

  第三步： 在for循環體內，調用recurse，傳參currentNode的某一個子節點。具體哪一個子節點取決于for循環的迭代情況。

  第四步： 當currentNode沒有更多的子節點，退出for循環，并調用在調用traverseDf(callback)時傳遞進來的callback函數。

  第二步（自終止），第三步（自調用），第四步（回調函數） 會重復進行，直到我們遍歷到樹的所有節點。

  完整的講述遞歸需要一整面文章，這超出了本文的范圍。讀者可以用上面的traverseDF(callback)來實驗（在瀏覽器里面打個斷點看看是怎么執行的），來嘗試理解它是怎么工作的。

  下面這段例子用來說明一個樹是如何被traverseDF(callback)遍歷的。
  首先我們創建一顆樹用來遍歷，下面這種方法并不好，但是可以起到說明的效果。理想的方式是使用后面在第四部分要實現的add(value)。

  /*
  
  建立一顆結構如下的樹
  
  one
  ├── two
  │   ├── five
  │   └── six
  ├── three
  └── four
      └── seven
  
  */
  
  var tree = new Tree("one");
  
  tree._root.children.push(new Node("two"));
  tree._root.children[0].parent = tree;
  
  tree._root.children.push(new Node("three"));
  tree._root.children[1].parent = tree;
  
  tree._root.children.push(new Node("four"));
  tree._root.children[2].parent = tree;
  
  tree._root.children[0].children.push(new Node("five"));
  tree._root.children[0].children[0].parent = tree._root.children[0];
  
  tree._root.children[0].children.push(new Node("six"));
  tree._root.children[0].children[1].parent = tree._root.children[0];
  
  tree._root.children[2].children.push(new Node("seven"));
  tree._root.children[2].children[0].parent = tree._root.children[2];
  

  然后我們調用traverseDF(callback):

  tree.traverseDF(function(node) {
      console.log(node.data)
  });
  /*
  
  logs the following strings to the console(這個就不翻了)
  
  "five"
  "six"
  "two"
  "three"
  "seven"
  "four"
  "one"
  
  */

  第二個: traverseBF(callback)

  這個方法用來進行寬度優先遍歷。
  深度優先和寬度優先的遍歷順序是不一樣的，我們使用在traverseBF(callback)中用過的樹來證明這一點：

  /*
  
   tree
  
   one (depth: 0)
   ├── two (depth: 1)
   │   ├── five (depth: 2)
   │   └── six (depth: 2)
   ├── three (depth: 1)
   └── four (depth: 1)
       └── seven (depth: 2)
  
   */

  然后傳入相同的回調函數：

  tree.traverseBF(function(node) {
      console.log(node.data)
  });
  
  /*
  
  logs the following strings to the console
  
  "one"
  "two"
  "three"
  "four"
  "five"
  "six"
  "seven"
  
  */

  上面的log和樹的結構已經說明了寬度優先遍歷的模式。從根節點開始，然后向下一層，從左向右遍歷所有這一層的節點。重復進行知道到達最底層。

  現在我們有了概念，那么來實現代碼：

  Tree.prototype.traverseBF = function(callback) {
      var queue = new Queue();
  
      queue.enqueue(this._root);
  
      currentNode = queue.dequeue();
  
      while(currentNode){
          for (var i = 0, length = currentNode.children.length; i < length; i++) {
              queue.enqueue(currentNode.children[i]);
          }
  
          callback(currentNode);
          currentNode = queue.dequeue();
      }
  };

  traverseBF(callback)的定義包含了很多邏輯，作者在這里解釋了一堆。我感覺對理解代碼并沒有幫助。
  嘗試解釋一下，根節點算第一層：

  從根節點開始，這個時候currentNode是根節點；

  第一次while遍歷currentNode的所有子節點，推進隊列。（這個時候第二層已經遍歷到了，并且會在while循環中依次執行，先進先出）

  執行回調函數，傳入currentNode；

  currentNode賦值為第二層第一個子節點。

  第二次while：對currentNode，第二層第一個子節點的所有子節點遍歷，推入隊列。注意這里是第三層的第一部分。

  執行回調函數，傳入currentNode；

  currentNode賦值為第二層第二個子節點。

  第三次while：對currentNode，第二層第二個子節點的所有子節點遍歷，推入隊列。注意這里是第三層的第二部分。

  執行回調函數，傳入currentNode；

  currentNode賦值為第二層第三個子節點。

  最后幾次while

  ：這個時候已經沒有下一層了，不會進入for循環，就是依次把隊列里剩的節點傳到回調函數里面執行就對了。

  這樣就很清楚了。

  第三個: contains(callback,traversal)

  這個方法用來在樹里搜索一個特定的值。為了使用我們之前定義的兩種遍歷方式，contains(callback,traversal)可以接受兩個參數，要找的值，和要進行的遍歷方式。

  Tree.prototype.contains = function(callback, traversal) {
      traversal.call(this, callback);
  };

  call方法的第一個參數把traversal綁定在調用contains(callback,traversal)的那棵樹上面，第二個參數是一個在每個節點上面調用的函數。
  下面這個函數大家自己理解，我感覺原作者解釋反了。

  // tree is an example of a root node
  tree.contains(function(node){
      if (node.data === "two") {
          console.log(node);
      }
  }, tree.traverseBF);

  第四個: add(data, toData, traversal)

  現在我們會找了，再來個添加的方法吧。

  Tree.prototype.add = function(data, toData, traversal) {
      //實例一個node
      var child = new Node(data),
          parent = null,
          //找爹函數
          callback = function(node) {
              if (node.data === toData) {
                  parent = node;
              }
          };
          //按某種方式執行找爹函數
      this.contains(callback, traversal);
      //找到了嗎
      if (parent) {
        //找到了，領走，認爹
          parent.children.push(child);
          child.parent = parent;
      } else {
        //沒找到，報錯：沒這個爹
          throw new Error("Cannot add node to a non-existent parent.");
      }
  };

  注釋就很清楚了。

  var tree = new Tree("CEO");
  
  tree.add("VP of Happiness", "CEO", tree.traverseBF);
  
  /*
  
  our tree
  
  "CEO"
  └── "VP of Happiness"
  
  */

  var tree = new Tree("CEO");
  
  tree.add("VP of Happiness", "CEO", tree.traverseBF);
  tree.add("VP of Finance", "CEO", tree.traverseBF);
  tree.add("VP of Sadness", "CEO", tree.traverseBF);
  
  tree.add("Director of Puppies", "VP of Finance", tree.traverseBF);
  tree.add("Manager of Puppies", "Director of Puppies", tree.traverseBF);
  
  /*
  
   tree
  
   "CEO"
   ├── "VP of Happiness"
   ├── "VP of Finance"
   │   ├── "Director of Puppies"
   │   └── "Manager of Puppies"
   └── "VP of Sadness"
  
   */
  

  第五個: remove(data, fromData, traversal)

  類似的，刪除方法：

  Tree.prototype.remove = function(data, fromData, traversal) {
      var tree = this,
          parent = null,
          childToRemove = null,
          index;
          //因為是刪除某個數據下的某個值，所以先定義找爹
      var callback = function(node) {
          if (node.data === fromData) {
              parent = node;
          }
      };
        //按某種方式找爹
      this.contains(callback, traversal);
        //爹存在嗎
      if (parent) {
          //存在，找娃的排行
          index = findIndex(parent.children, data);
          //找著了嗎
          if (index === undefined) {
            //妹找著
              throw new Error("Node to remove does not exist.");
          } else {
            //找著了，干掉，提頭
              childToRemove = parent.children.splice(index, 1);
          }
      } else {
        //爹不存在，報錯
          throw new Error("Parent does not exist.");
      }
      //拿頭交差
      return childToRemove;
  };

  function findIndex(arr, data) {
      var index;
      //遍歷某個data爹的娃，如果全等，那么返回這個娃的排行，否則返回的index等于undefined
      for (var i = 0; i < arr.length; i++) {
          if (arr[i].data === data) {
              index = i;
          }
      }
  
      return index;
  }

  在全文的最后，作者放出了全家福：

  function Node(data) {
      this.data = data;
      this.parent = null;
      this.children = [];
  }
  
  function Tree(data) {
      var node = new Node(data);
      this._root = node;
  }
  
  Tree.prototype.traverseDF = function(callback) {
  
      // this is a recurse and immediately-invoking function
      (function recurse(currentNode) {
          // step 2
          for (var i = 0, length = currentNode.children.length; i < length; i++) {
              // step 3
              recurse(currentNode.children[i]);
          }
  
          // step 4
          callback(currentNode);
  
          // step 1
      })(this._root);
  
  };
  
  Tree.prototype.traverseBF = function(callback) {
      var queue = new Queue();
  
      queue.enqueue(this._root);
  
      currentTree = queue.dequeue();
  
      while(currentTree){
          for (var i = 0, length = currentTree.children.length; i < length; i++) {
              queue.enqueue(currentTree.children[i]);
          }
  
          callback(currentTree);
          currentTree = queue.dequeue();
      }
  };
  
  Tree.prototype.contains = function(callback, traversal) {
      traversal.call(this, callback);
  };
  
  Tree.prototype.add = function(data, toData, traversal) {
      var child = new Node(data),
          parent = null,
          callback = function(node) {
              if (node.data === toData) {
                  parent = node;
              }
          };
  
      this.contains(callback, traversal);
  
      if (parent) {
          parent.children.push(child);
          child.parent = parent;
      } else {
          throw new Error("Cannot add node to a non-existent parent.");
      }
  };
  
  Tree.prototype.remove = function(data, fromData, traversal) {
      var tree = this,
          parent = null,
          childToRemove = null,
          index;
  
      var callback = function(node) {
          if (node.data === fromData) {
              parent = node;
          }
      };
  
      this.contains(callback, traversal);
  
      if (parent) {
          index = findIndex(parent.children, data);
  
          if (index === undefined) {
              throw new Error("Node to remove does not exist.");
          } else {
              childToRemove = parent.children.splice(index, 1);
          }
      } else {
          throw new Error("Parent does not exist.");
      }
  
      return childToRemove;
  };
  
  function findIndex(arr, data) {
      var index;
  
      for (var i = 0; i < arr.length; i++) {
          if (arr[i].data === data) {
              index = i;
          }
      }
  
      return index;
  }