二叉树的遍历

二叉树有常见的三种遍历方式

• 前序遍历: 根结点 -> 左子树 -> 右子树
• 中序遍历: 左子树 -> 根结点 -> 右子树
• 后序遍历: 左子树 -> 右子树 -> 根结点

要遍历的二叉树

const root = {
  val: "A",
  left: {
    val: "B",
    left: {
      val: "D"
    },
    right: {
      val: "E"
    }
  },
  right: {
    val: "C",
    right: {
      val: "F"
    }
  }
};

前序遍历

// 所有遍历函数的入参都是树的根结点对象
function preorder(root){
  // 递归边界，root 为空
    if(!root){
      return;
  }
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val);
  preorder(root.left);
  preorder(root.right);
}

中序遍历

递归边界照旧，唯一发生改变的是递归式里调用递归函数的顺序——左子树的访问会优先于根结点。我们参考先序遍历的分析思路，来写中序遍历的代码：

// 所有遍历函数的入参都是树的根结点对象
function preorder(root){
  // 递归边界，root 为空
    if(!root){
      return;
  }
  preorder(root.left);
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val);
  preorder(root.right);
}

后序遍历

递归边界照旧，唯一发生改变的仍然是是递归式里调用递归函数的顺序

// 所有遍历函数的入参都是树的根结点对象
function preorder(root){
  // 递归边界，root 为空
    if(!root){
      return;
  }
  preorder(root.left);
  preorder(root.right);
  // 输出当前遍历的结点值
  console.log('当前遍历的结点值是：', root.val);
}

深度优先遍历(DFS)

深度优先主要是利用栈，先压右子树，再压左子树

function DepthFirstSearch(biTree) {
    let stack = [];
    stack.push(biTree);
    while (stack.length != 0) {
        let node = stack.pop();
        console.log(node.data);
        if (node.rChild) {
            stack.push(node.rChild);
        }
        if (node.lChild) {
            stack.push(node.lChild);
        }
    }
}

广度优先遍历(BFS)

广度优先主要利用队列，先入左子树，再入右子树

function BreadthFirstSearch(biTree) {
    let queue = [];
    queue.push(biTree);
    while (queue.length != 0) {
        let node = queue.shift();
        console.log(node.data);
        if (node.lChild) {
            queue.push(node.lChild);
        }
        if (node.rChild) {
            queue.push(node.rChild);
        }
    }
}