/*
 *二叉樹(shù)的節(jié)點(diǎn)對(duì)象
 */
function Node() {
  this.text = '';      //節(jié)點(diǎn)的文本
  this.leftChild = null;  //節(jié)點(diǎn)的左孩子引用
  this.rightChild = null;  //節(jié)點(diǎn)右孩子引用
}

var charecters = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'];
function buildTree(node, i) {
    var leftIndex = 2*i+1,             //左孩子節(jié)點(diǎn)的索引
      rightIndex = 2*i+2;             //右孩子節(jié)點(diǎn)的索引
    if(leftIndex < charecters.length) {       //判斷索引的長(zhǎng)度是否超過(guò)了charecters數(shù)組的大小
      var childNode = new Node();         //創(chuàng)建一個(gè)新的節(jié)點(diǎn)對(duì)象
      childNode.text = charecters[leftIndex];   //給節(jié)點(diǎn)賦值
      node.leftChild = childNode;         //給當(dāng)前節(jié)點(diǎn)node加入左孩子節(jié)點(diǎn)
      buildTree(childNode, leftIndex);      //遞歸創(chuàng)建左孩子
    }
    if(rightIndex < charecters.length) {      //下面注釋參照上面的構(gòu)建左孩子的節(jié)點(diǎn)
      var childNode = new Node();
      childNode.text = charecters[rightIndex];
      node.rightChild = childNode;
      buildTree(childNode, rightIndex);
    }
}
//下面構(gòu)造二叉樹(shù)
var node = new Node();
node.text = charecters[0];
buildTree(node, 0);  //索引i是從0開(kāi)始構(gòu)建

var root;
function createBinaryTree() {
    var len = charecters.length,        //數(shù)組的長(zhǎng)度
      index = 0,               //索引從0開(kāi)始
      nodes = new Array();          //創(chuàng)建一個(gè)臨時(shí)數(shù)組，用于存放二叉樹(shù)節(jié)點(diǎn)
    //循環(huán)創(chuàng)建二叉樹(shù)節(jié)點(diǎn)存放到數(shù)組中
    for (var i = 0 ; i < charecters.length ; i++) {
      var node = new Node();
      node.text = charecters[i];
      nodes.push(node);
    }
    //循環(huán)建立二叉樹(shù)子節(jié)點(diǎn)的引用
    while(index < len) {
      var leftIndex = 2*index+1,       //當(dāng)前節(jié)點(diǎn)左孩子索引
        rightIndex = 2*index+2;       //當(dāng)前節(jié)點(diǎn)右孩子索引
      //給當(dāng)前節(jié)點(diǎn)添加左孩子
      nodes[index].leftChild = nodes[leftIndex];
      //給當(dāng)前節(jié)點(diǎn)添加右孩子
      nodes[index].rightChild = nodes[rightIndex];
      index++;
    }
    root = nodes[0];
}

function Stack() {
    var stack = new Array();        //存放棧的數(shù)組
    //壓棧
    this.push = function(o) {
      stack.push(o);
    };
    //出棧
    this.pop = function() {
      var o = stack[stack.length-1];
      stack.splice(stack.length-1, 1);
      return o;
    };
    //檢查棧是否為空
    this.isEmpty = function() {
      if(stack.length <= 0) {
        return true;
      }
      else {
        return false;
      }
    };
}
//使用方式如下
var stack = new Stack();
stack.push(1);    //現(xiàn)在棧中有一個(gè)元素
stack.isEmpty();   //false , 棧不為空
alert(stack.pop()); //出棧, 打印1
stack.isEmpty();   //true, 此時(shí)棧為空，因?yàn)樵谡{(diào)用了stack.pop()之后元素出棧了，所以為空

function firstIteration(node) {
    if(node.leftChild) {          //判斷當(dāng)前節(jié)點(diǎn)是否有左孩子
      firstIteration(node.leftChild);  //遞歸左孩子
    }
    if(node.rightChild) {         //判斷當(dāng)前節(jié)點(diǎn)是否有右孩子
      firstIteration(node.rightChild);  //遞歸右孩子
    }
}
//遞歸遍歷二叉樹(shù)
firstIteration(root);

function notFirstIteration(node) {
    var stack = new Stack(),         //開(kāi)辟一個(gè)新的棧對(duì)象
      resultText = '';           //存放非遞歸遍歷之后的字母順序
    stack.push(root);            //這個(gè)root在上面非遞歸方式構(gòu)建二叉樹(shù)的時(shí)候已經(jīng)構(gòu)建好的
    var node = root;
    resultText += node.text;
    while(!stack.isEmpty()) {
      while(node.leftChild) {       //判斷當(dāng)前節(jié)點(diǎn)是否有左孩子節(jié)點(diǎn)
        node = node.leftChild;      //取當(dāng)前節(jié)點(diǎn)的左孩子節(jié)點(diǎn)
        resultText += node.text;     //訪問(wèn)當(dāng)前節(jié)點(diǎn)
        stack.push(node);        //將當(dāng)前節(jié)點(diǎn)壓入棧中
      }
      stack.pop();             //出棧
      node = stack.pop().rightChild;    //訪問(wèn)當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)（右孩子節(jié)點(diǎn)）
      if(node) {              //當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)不為空
        resultText += node.text;     //訪問(wèn)當(dāng)前節(jié)點(diǎn)
        stack.push(node);        //將當(dāng)前節(jié)點(diǎn)壓入棧中
      }
      else {                //當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)為空
        node = stack.pop();       //在回溯到上一層
      }
    }
}
//非遞歸先序遍歷
notFirstIteration(root);

var strText = "";
function secondIteration(node) {
    //訪問(wèn)左節(jié)點(diǎn)
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        secondIteration(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //訪問(wèn)根節(jié)點(diǎn)
    strText += node.text;
    //訪問(wèn)右節(jié)點(diǎn)
    if(node.rightChild) {
      if(node.rightChild.leftChild) {
        secondIteration(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
}
secondIteration(root);
alert(strText);

function notSecondIteration() {
    var resultText = '',
      stack = new Stack(),
      node = root;
    stack.push(node);
    while(!stack.isEmpty()) {
      //從根節(jié)點(diǎn)一直往下找左孩子節(jié)點(diǎn)直到最后一個(gè)左孩子節(jié)點(diǎn)，然后保存在棧中
      while(node.leftChild) {
        node = node.leftChild;
        stack.push(node);
      }
      //彈出棧
      var tempNode = stack.pop();
      //訪問(wèn)臨時(shí)節(jié)點(diǎn)
      resultText += tempNode.text;
      if(tempNode.rightChild) {
        node = tempNode.rightChild;
        stack.push(node);
      }
    }
    alert(resultText);
}

var strText = '';
function lastIteration(node) {
    //首先訪問(wèn)左孩子節(jié)點(diǎn)
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        lastIteration(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //然后再訪問(wèn)右孩子節(jié)點(diǎn)
    if(node.rightChild) {
      if(node.rightChild.rightChild) {
        lastIteration(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
    //最后訪問(wèn)根節(jié)點(diǎn)
    strText += node.text;
}
//中序遞歸遍歷
lastIteration(root);
alert(strText);

function notLastIteration() {
    var strText = '',
    stack = new Stack();
    nodo = root;
    stack.push(node);
    while(!stack.isEmpty()) {
      while(node.leftChild) {
        node = node.leftChild;
        stack.push(node);
      }
      //彈出棧
      var tempNode = stack.pop();
      //訪問(wèn)左孩子節(jié)點(diǎn)
      strText += tempNode.text;
      //訪問(wèn)右孩子節(jié)點(diǎn)
      if(tempNode.rightChild) {
        if(tempNode.rightChild.leftChild || tempNode.rightChild.rightChild) { //判斷最后一個(gè)左孩子節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是否為頁(yè)節(jié)點(diǎn)
          stack.push(tempNode.rightChild);
        }
        else {
          strText += tempNode.rightChild.text;
        }
      }
    }
    alert(strText);
}