js 二叉树遍历

L、D、R 分别表示遍历左子树、访问根结点和遍历右子树

二叉树

const obj = {
  value: 1,
  left: {
    value: 2,
    left: {
      value: 4
    },
    right: {
      value: 5
    }
  },
  right: {
    value: 3,
    left: {
      value: 6
    },
    right: {
      value: 7
    }
  }
}

const arr = [];

前序遍历

根 左 右

const DLR = function (obj) {
  arr.push(obj.value);
  if (obj.left) {
    DLR(obj.left);
  }
  if (obj.right) {
    DLR(obj.right);
  }
}

// arr = [ 1, 2, 4, 5, 3, 6, 7 ]

中序遍历

左 根 右

const LDR = function (obj) {
  if (obj.left) {
    LDR(obj.left);
  }
  arr.push(obj.value);
  if (obj.right) {
    LDR(obj.right);
  }
}

// arr = [ 4, 2, 5, 1, 6, 3, 7 ]

后序遍历

左 右 根

const LRD = function (obj) {
  if (obj.left) {
    LRD(obj.left);
  }
  if (obj.right) {
    LRD(obj.right);
  }
  arr.push(obj.value);
}

// arr = [ 4, 5, 2, 6, 7, 3, 1 ]

层次遍历

将根结点放入队列中，打印根结点的 value 值
判断根结点是否有左子树，有则将左子树放入队列中
判断根结点是否有右子树，有则将右子树放入队列中
将根结点出队
循环遍历队列中的结点

const layer = function (obj) {
  const queue = [];
  queue.push(obj);
  while (queue.length) {
    arr.push(queue[0].value);
    if (queue[0].left) {
      queue.push(queue[0].left);
    }
    if (queue[0].right) {
      queue.push(queue[0].right);
    }
    queue.shift();
  }
}

// arr = [ 1, 2, 3, 4, 5, 6, 7 ]