二叉树前中后序遍历/层序遍历的递归/非递归实现

[devinxiang]

生成一个二叉搜索树

const Compare = {
  LESS_THAN: -1,
  BIGGER_THAN: 1,
  EQUALS: 0
};

function defaultCompare(a, b) {
  if (a === b) {
    return Compare.EQUALS;
  }
  return a < b ? Compare.LESS_THAN : Compare.BIGGER_THAN;
}

class Node {
  constructor(key) {
    this.key = key;
    this.val = key;
    this.left = null;
    this.right = null;
  }
  toString() {
    return `${this.key}`;
  }
}

class BinarySearchTree {
  constructor(CompareFn = defaultCompare) {
    this.compareFn = CompareFn;
    this.root = null;
  }
  insert(key) {
    if (this.root === null) {
      this.root = new Node(key);
    } else {
      this.insertNode(this.root, key);
    }
  }

  insertNode(node, key) {
    if (this.compareFn(key, node.key) === Compare.LESS_THAN) {
      if (node.left === null) {
        node.left = new Node(key);
      } else {
        this.insertNode(node.left, key);
      }
    } else {
      if (node.right === null) {
        node.right = new Node(key);
      } else {
        this.insertNode(node.right, key);
      }
    }
  }
}
const tree = new BinarySearchTree();
tree.insert(50);
tree.insert(20);
tree.insert(10);
tree.insert(30);
tree.insert(80);
tree.insert(70);
tree.insert(90);
tree.insert(40);
/**
 *             50
 *      20            80
 *    10    30    70      90
 *  nu nu  nu 40
 */

前序遍历

根节点 → 左节点 → 右节点

递归

var preOrder = function(node) {
  if (!node) return null;
  console.log("val", node.val);
  preOrder(node.left);
  preOrder(node.right);
};
preOrder(tree.root);
// 增加传入和返回;
var preOrder = function(node) {
  const nodes = [];
  preOrderNode(node, nodes);
  return nodes;
};
var preOrderNode = function(node, nodes) {
  if (!node) return null;
  nodes.push(node.key);
  preOrderNode(node.left, nodes);
  preOrderNode(node.right, nodes);
};

// [50, 20, 10, 30, 40, 80, 70, 90]
console.log(preOrder(tree.root));

非递归形式

/**
 * 1. 通过一个栈来存储节点值，把当前节点放入栈
 * 2. 如果左子节点存在一直往栈中添加，在添加的时候把值加入遍历的 nodes 中，因为每次添加都是根，或者最左的节点；保证了根左，然后回溯的时候保证右
 * 3. 添加完之后，开始回溯查找上一个节点，怎么回溯，替换 node = node.right; 当前节点进入 while，然后继续判断左节点的情况；
 * 有点绕：核心不断递归左节点，然后出栈，判断节点的右节点，存在则继续前面第一个操作递归左节点，从而达到前序遍历的效果
 *
 */
var preOrder = function(node) {
  const nodes = [];
  preOrderNode(node, nodes);
  return nodes;
};
var preOrderNode = function(root, nodes) {
  if (!root) return [];
  let stack = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    //  依次把左节点压入栈
    while (node !== null) {
      nodes.push(node.val);

      stack.push(node);
      node = node.left;
    }

    // 上面把左节点压入栈了，进行出栈，访问右子节点
    // 访问到 10 node.right = null， 出栈
    // 访问到 20， node.right = 30, 走一层；
    if (stack.length > 0) {
      node = stack.pop();
      console.log("node", node);
      // nodes.push(node.val);
      node = node.right;
    }
  }
};
console.log(preOrder(tree.root));

中序遍历

左节点 → 根节点 → 右节点

递归

var inOrder = function(node) {
  const nodes = [];
  inOrderNode(node, nodes);
  return nodes;
};

var inOrderNode = function(node, nodes) {
  if (!node) return null;
  inOrderNode(node.left, nodes);
  nodes.push(node.val);
  inOrderNode(node.right, nodes);
};

// [10, 20, 30, 40, 50, 70, 80, 90]
console.log(inOrder(tree.root));

非递归

/**
 * 中序遍历的非递归形式，
 * 1. 优先把左子树依次添加进栈中，
 * 2. 先出左子树，然后出 node
 * bst 中序遍历，是有小到大的排序
 * 在做出栈的时候进行遍历，因为先把所有的根和做节点压入了，出栈的时候先出的是左，然后是根，然后右入栈处理完开始出栈达到一个中序遍历效果
 */
var inOrder = function(root) {
  const stack = [];
  const nodes = [];
  let node = root;
  while (node !== null || stack.length > 0) {
    // 先做入栈
    while (node) {
      stack.push(node);
      node = node.left;
    }
    // 在做出栈
    if (stack.length > 0) {
      node = stack.pop();
      nodes.push(node.val);
      node = node.right;
    }
  }

  return nodes;
};
console.log(inOrder(tree.root));

后序遍历

左节点 → 右节点 → 根节点

递归

var postOrder = function(root) {
  const nodes = [];
  postOrderNode(root, nodes);

  return nodes;
};
var postOrderNode = function(node, nodes) {
  if (!node) return;
  postOrderNode(node.left, nodes);
  postOrderNode(node.right, nodes);
  nodes.push(node.val);
};

// [10, 40, 30, 20, 70, 90, 80, 50]
console.log(postOrder(tree.root));

非递归

/**
 * 非递归的形式
 * 实现思路：
 * 1. 通过栈来做，把左节点压入栈中
 * 2. 出栈，先出左节点，到根判断有没有右节点，有的话压住栈中，出有节点，出完出根节点；
 * 根的右节点压入栈中，继续压入左节点，相同的方法出栈入栈；
 * 关键点，怎么判断是该根节点开始运行了，做一个判断，该节点的左右节点是否都已经访问过了；或者不存在左右节点；
 * 不是上面的情况，则将右节点和左节点依次入栈，保证左节点在栈顶先被访问；
 * 做一个 prev 节点；
 */

var postOrder = function(root) {
  const stack = [];
  const nodes = [];
  let prev = null;
  let cur = null;

  stack.push(root);

  while (stack.length > 0) {
    // 获取到栈顶的元素
    cur = stack[stack.length - 1];
    // 两种可以访问的情况
    // 1. 当前节点无左右节点，可以访问
    // 2. 当前节点左右节点是否都访问过了，访问过的节点 prev 不为 null，第一个条件排除了左右节点都存在的情况，所以现在一定是单节点了，只要 prev 等于中的一个即可表示已经访问过子节点了
    if (
      (cur.left === null && cur.right === null) ||
      (prev !== null && (prev === cur.left || prev === cur.right))
    ) {
      nodes.push(cur.val);
      stack.pop();
      // 把当前节点存放到 prev 中，表示当前节点已经访问过了；
      prev = cur;
    } else {
      if (cur.right !== null) stack.push(cur.right);
      if (cur.left !== null) stack.push(cur.left);
    }
  }

  return nodes;
};
console.log(postOrder(tree.root));

层序遍历

非递归

/**
 * 非递归的形式
 * 思路：通过一个数组存储当前层的节点，然后依次 pop，pop 出来的节点判断有没有左右子节点，有的的接到数组后面，因为是一层一层的接的，所以可以把每一层的依次接入；
 * 关键判断核心，是 queue 是不是空的
 */
var levelOrder = function(root) {
  let queue = [];
  const ret = [];
  queue.push(root);

  while (queue.length > 0) {
    const node = queue.shift();
    ret.push(node && node.key);
    if (node && node.left !== null) {
      queue.push(node.left);
    }
    if (node && node.right !== null) {
      queue.push(node.right);
    }
  }

  return ret;
};

进阶

// 现在想要改为二维数组，就需要区分每一层的位置；
// 关键点，如何区分是那一层的值，没次进来的时候，获取到 queue 的长度，然后把当前层循环处理完，再次while 进来处理第二层；
var levelOrder = function(root) {
  let queue = [];
  queue.push(root);
  let list = [];
  while (queue.length > 0) {
    // 获取到每层进来的长度，把当层的循环完然后进入下一层
    const len = queue.length;
    const level = [];
    // console.log("len", queue.length); // 1 2 4 1
    for (let i = 0; i < len; i++) {
      const node = queue.shift();
      level.push(node.key);
      if (node && node.left !== null) {
        queue.push(node.left);
      }
      if (node && node.right !== null) {
        queue.push(node.right);
      }
    }

    list.push(level);
  }

  return list;
};

console.log(levelOrder(tree.root));