二叉树遍历（前中后层序）

什么是二叉树不做介绍，在排序前下面先定义了树节点和二叉树两个类，然后创建了一个二叉树实例用于后续遍历使用。

//树节点
class TreeNode {
  constructor(val) {
    this.value = val;
    this.left = null;
    this.right = null;
  }
}

//简单构建了一个二叉树类
class Tree {
  constructor(root) {
    this.root = root;
  }

  addTreeNode(node) {
    if (!this.root) this.root = node;
    else this.compare(node, this.root);
  }

  compare(node, parent) {
    if (node.value < parent.value) {
      if (parent.left) this.compare(node, parent.left);
      else parent.left = node;
    } else if (node.value > parent.value) {
      if (parent.right) this.compare(node, parent.right);
      else parent.right = node;
    } else {
      console.log("error: add same value");
    }
  }
}

const tree = new Tree();
[5, 8, 1, 3, 2, 9, 7, 4, 6].forEach((v) => {
  tree.addTreeNode(new TreeNode(v));
});

这时候二叉树的结构如下：

            5                      //第一层
        /       \
    1               8            //第二层
      \           /   \
        3        7      9       //第三层
       / \      /
      2   4    6               //第四层

前序遍历 （递归 非递归实现）

遍历顺序：访问根–>遍历左子树–>遍历右子树
预期结果： 5-1-3-2-4-8-7-6-9

//递归写法
function preorder(node) {
  if (node) {
    console.log(node.value);
    preorder(node.left);
    preorder(node.right);
  }
}
preorder(tree.root);

//非递归写法
function preoder_non_recursive(node) {
  var stack = [node];
  while (stack.length) {
    var cur = stack.pop();
    console.log(cur.value);
    if (cur.right) stack.push(cur.right);
    if (cur.left) stack.push(cur.left);
  }
}
preoder_non_recursive(tree.root);

中序遍历 （递归 非递归实现）

遍历顺序：遍历左子树–>访问根–>遍历右子树
预期结果： 1-2-3-4-5-6-7-8-9

//递归写法
function inorder(node) {
  if (node) {
    inorder(node.left);
    console.log(node.value);
    inorder(node.right);
  }
}
inorder(tree.root);

//非递归写法
function inoder_non_recursive(node) {
  var stack = [];
  while (stack.length || node) {
    if (node) {
      stack.push(node);
      node = node.left;
    } else {
      node = stack.pop();
      console.log(node.value);
      node = node.right;
    }
  }
}
inoder_non_recursive(tree.root);

中序非递归的执行顺序如下：
stack:[5] result:[]
stack:[5,1] result:[]
stack:[5] result:[1]
stack:[5,3] result:[1]
stack:[5,3,2] result:[1]
stack:[5,3] result:[1,2]
stack:[5] result:[1,2,3]
stack:[5,4] result:[1,2,3]
stack:[5] result:[1,2,3,4]
stack:[] result:[1,2,3,4,5]
stack:[8] result:[1,2,3,4,5]
stack:[8,7] result:[1,2,3,4,5]
stack:[8,7,6] result:[1,2,3,4,5]
stack:[8,7] result:[1,2,3,4,5,6]
stack:[8] result:[1,2,3,4,5,6,7]
stack:[] result:[1,2,3,4,5,6,7,8]
stack:[9] result:[1,2,3,4,5,6,7,8]
stack:[] result:[1,2,3,4,5,6,7,8,9]

后序遍历 （递归 非递归实现）

遍历顺序：遍历左子树–>遍历右子树–>访问根
预期结果： 2-4-3-1-6-7-9-8-5

//递归写法
function postorder(node) {
  if (node) {
    postorder(node.left);
    postorder(node.right);
    console.log(node.value);
  }
}
postorder(tree.root);

//非递归写法
function postoder_non_recursive(node) {
  var stack = [node];
  while (stack.length) {
    if (node.left && !node.visit) {
      node.visit = "left";
      stack.push(node.left);
      node = node.left;
    } else if (node.right && node.visit !== "right") {
      node.visit = "right";
      stack.push(node.right);
      node = node.right;
    } else {
      node = stack.pop();
      console.log(node.value);
      delete node.visit;
      node = stack[stack.length - 1];
    }
  }
}
postoder_non_recursive(tree.root);

后序非递归的执行顺序如下：
stack:[5] result:[]
stack:[5,1] result:[]
stack:[5,1,3] result:[]
stack:[5,1,3,2] result:[]
stack:[5,1,3] result:[2]
stack:[5,1,3,4] result:[2]
stack:[5,1,3] result:[2,4]
stack:[5,1] result:[2,4,3]
stack:[5] result:[2,4,3,1]
stack:[5,8] result:[2,4,3,1]
stack:[5,8,7] result:[2,4,3,1]
stack:[5,8,7,6] result:[2,4,3,1]
stack:[5,8,7] result:[2,4,3,1,6]
stack:[5,8] result:[2,4,3,1,6,7]
stack:[5,8,9] result:[2,4,3,1,6,7]
stack:[5,8] result:[2,4,3,1,6,7,9]
stack:[5] result:[2,4,3,1,6,7,9,8]
stack:[] result:[2,4,3,1,6,7,9,8,5]

层序遍历

遍历顺序：按照层一层层遍历
预期结果： 5-1-8-3-7-9-2-4-6

function levelOrder(node) {
  var list = [node];
  while (list.length) {
    var cur = list.shift();
    console.log(cur.value);
    if (cur.left) list.push(cur.left);
    if (cur.right) list.push(cur.right);
  }
}
levelOrder(tree.root);