二叉树的遍历

参考:
Tree Traversal via JavaScript | DigitalOcean

Breadth-First Search 广度优先搜索

function BFS(tree) {
  let visited = [],
      queue = [],
      current = tree.root;

  queue.push(current);

  while (queue.length) {
    current = queue.shift();
    visited.push(current.val);

    if (current.left) queue.push(current.left);
    if (current.right) queue.push(current.right);
  };

    return visited;
}

console.log(BFS(tree)); 
//[ 20, 14, 57, 9, 19, 31, 62, 3, 11, 72 ]

Depth-First Search 深度优先搜索

前序遍历

node -> left -> right

适用场景 例如目录结构

function preOrder(tree) {
  let visited = [],
      current = tree.root;

  let traverse = node => {
    visited.push(node.val);
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
  };

  traverse(current);
  return visited;
}

console.log(preOrder()); 
// [ 20, 14, 9, 3, 11, 19, 57, 31, 62, 72 ]

后序遍历

left -> right -> node

function postOrder(tree) {
  let visited = [],
      current = tree.root;

  let traverse = node => {
    if (node.left) traverse(node.left);
    if (node.right) traverse(node.right);
    visited.push(node.val);
  };

  traverse(current);
  return visited;
}

console.log(postOrder(tree)); 
// [ 3, 11, 9, 19, 14, 31, 72, 62, 57, 20 ]

中序遍历

left -> node -> right

适用场景,表达式树

function inOrder(tree) {
  let visited = [],
      current = tree.root;

  let traverse = node => {
    if (node.left) traverse(node.left);
    visited.push(node.val);
    if (node.right) traverse(node.right);
  };

  traverse(current);
  return visited;
}

console.log(inOrder(tree)); 
// [ 3, 9, 11, 14, 19, 20, 31, 57, 62, 72 ]

迭代方式实现,利用栈的后进先出

function inOrder(tree) {
  let current = tree.root;
  let result = [];
  let callStack = [];

  while(true) {
    while(!!current) {
      callStack.push(current);
      current = current.left;
    }

    if (callStack.length === 0) break;

    let lastCurrent = callStack.pop();
    result.push(lastCurrent.val);
    current = lastCurrent.right;
  }

  return result;
}

console.log(inOrder(tree)); 
// [ 3, 9, 11, 14, 19, 20, 31, 57, 62, 72 ]