JavaScript实现二叉树定义、遍历及查找的方法详解(4)

日期：2020-05-11 栏目：程序人生浏览：次

function notFirstIteration(node) {
    var stack = new Stack(),         //开辟一个新的栈对象
      resultText = '';           //存放非递归遍历之后的字母顺序
    stack.push(root);            //这个root在上面非递归方式构建二叉树的时候已经构建好的
    var node = root;
    resultText += node.text;
    while(!stack.isEmpty()) {
      while(node.leftChild) {       //判断当前节点是否有左孩子节点
        node = node.leftChild;      //取当前节点的左孩子节点
        resultText += node.text;     //访问当前节点
        stack.push(node);        //将当前节点压入栈中
      }
      stack.pop();             //出栈
      node = stack.pop().rightChild;    //访问当前节点的兄弟节点（右孩子节点）
      if(node) {              //当前节点的兄弟节点不为空
        resultText += node.text;     //访问当前节点
        stack.push(node);        //将当前节点压入栈中
      }
      else {                //当前节点的兄弟节点为空
        node = stack.pop();       //在回溯到上一层
      }
    }
}
//非递归先序遍历
notFirstIteration(root);

2. 中序遍历

只要把思路理清楚了现实起来其实还是挺容易的，只要我们熟悉了一种二叉树的非递归遍历方式，其他几种非递归方式就容易多了，照着葫芦画瓢，下面是中序遍历的递归方式，中序遍历的思想是：先访问左孩子节点，在访问根节点，最后访问右节点

var strText = "";
function secondIteration(node) {
    //访问左节点
    if(node.leftChild) {
      if(node.leftChild.leftChild) {
        secondIteration(node.leftChild);
      }
      else {
        strText += node.leftChild.text;
      }
    }
    //访问根节点
    strText += node.text;
    //访问右节点
    if(node.rightChild) {
      if(node.rightChild.leftChild) {
        secondIteration(node.rightChild);
      }
      else {
        strText += node.rightChild.text;
      }
    }
}
secondIteration(root);
alert(strText);

中序遍历的非递归方式

思想是：1. 从根节点一直往下找左孩子节点，直到找到最后一个左孩子节点（用栈将此路径保存，但不访问）2.访问最后一个左孩子节点，然后再访问根节点（要先弹出栈，就是在栈中取上一层节点）3.在访问当前节点（最后一个左孩子节点）的兄弟节点（右孩子节点），这里要注意如果兄弟节点是一个叶节点就直接访问，否则是兄弟节点是一颗子树的话不能马上访问，要先来重复 1， 2，3步骤，直到栈为空，循环结束

function notSecondIteration() {
    var resultText = '',
      stack = new Stack(),
      node = root;
    stack.push(node);
    while(!stack.isEmpty()) {
      //从根节点一直往下找左孩子节点直到最后一个左孩子节点，然后保存在栈中
      while(node.leftChild) {
        node = node.leftChild;
        stack.push(node);
      }
      //弹出栈
      var tempNode = stack.pop();
      //访问临时节点
      resultText += tempNode.text;
      if(tempNode.rightChild) {
        node = tempNode.rightChild;
        stack.push(node);
      }
    }
    alert(resultText);
}

转载注明出处：http://www.heiqu.com/243.html

JavaScript实现二叉树定义、遍历及查找的方法详解(4)

相关推荐