2018-06-17__二叉树遍历.md

二叉树遍历

递归写法

前序遍历

根结点 ---> 左子树 ---> 右子树

/*
 * 1) 访问结点P，并将结点P入栈;
 * 2) 判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);
 * 若不为空，则将P的左孩子置为当前的结点P;
 * 3) 直到P为NULL并且栈为空，则遍历结束。
 */
function preOrder (root) {
  if (!root) {
    return
  }
  console.log(root.value)
  preOrder(root.left)
  preOrder(root.right)
}

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

preOrder(root) // 1 2 4 5 3 6 7

中序遍历

左子树---> 根结点 ---> 右子树

function inOrder (root) {
  if (!root) {
    return
  }
  inOrder(root.left)
  console.log(root.value)
  inOrder(root.right)
}

后序遍历

左子树 ---> 右子树 ---> 根结点

function postOrder (root) {
  if (!root) {
    return
  }
  postOrder(root.left)
  postOrder(root.right)
  console.log(root.value)
}

非递归写法

先序遍历

function preOrder2 (root) {
  let current = root
  const stack = []
  while (current || stack.length ) {
    while (current) {
      console.log(current.value)
      stack.push(current)
      current = current.left
    }
    if (stack.length) {
      current = stack.pop()
      current = current.right
    }
  }
}

中序遍历

function inOrder2 (root) {
  let current = root
  const stack = []
  while (current || stack.length) {
    while (current) {
      stack.push(current)
      current = current.left
    }
    if (stack.length) {
      current = stack.pop()
      console.log(current.value)
      current = current.right
    }
  }
}

后序遍历

/*
 * 要保证根结点在左孩子和右孩子访问之后才能访问，因此对于任一结点P，先将其入栈。
 * 如果P不存在左孩子和右孩子，则可以直接访问它；
 * 或者P存在左孩子或者右孩子，但是其左孩子和右孩子都已被访问过了，则同样可以直接访问该结点。
 * 若非上述两种情况，则将P的右孩子和左孩子依次入栈，
 * 这样就保证了每次取栈顶元素的时候，左孩子在右孩子前面被访问，左孩子和右孩子都在根结点前面被访问。
 */
function postOrder2 (root) {
  let current = root
  let pre = null
  const stack = []
  stack.push(root)
  while (stack.length) {
    current = stack[stack.length - 1]
    if ((!current.left && !current.right) || (pre && (pre === current.left || pre === current.right))) {
      console.log(current.value)
      stack.pop();
      pre = current
    } else {
      if (current.right) {
        stack.push(current.right)
      }
      if (current.left) {
        stack.push(current.left)
      }
    }
  }
}

普通树遍历

非递归

function s (tree) {
  const s = []
  let p
  tree.forEach(root => {
    s.push(root)
    while (s.length) {
      p = s.shift()
      console.log(p.v)
      if (p.children && p.children.length) {
        p.children.forEach(c => s.push(c))
      }
    }
  })
}

const tree = [{
  v: 1,
  children: [{
    v: '2-1',
    children: [{
      v: '3-1'
    }, {
      v: '3-2',
      children: [{
        v: '4-1'
      }]
    }]
  }, {
    v: '2-2'
  }]
}, {
  v: 2
}]