二叉树

[jinzhepro]

父节点、子节点、根节点、兄弟节点、叶子节点

• A 节点就是 B 节点的父节点，B 节点是 A 节点的子节点。
• B、C、D这三个节点的父节点是同一个节点，所以它们之间互称为兄弟节点。
• 没有父节点的节点叫做根节点。
• 没有子节点的节点叫做叶子节点。

高度、深度、层

高度和深度都是从0开始。

满二叉树

叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点。

完全二叉树

叶子节点都在最底下两层，最后一层叶子结点都靠左排列，除了最后一层，其他层的节点个数要达到最大。

解析

基于数组的顺序存储法，根节点为1，左子节点为2i，右子节点为2i+1，父节点为Math.floor(i/2)，2i>n则i没有左子节点，2i+1>n则i没有右子节点。

遍历

复杂度O(n)

前序遍历

对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

const preOrder = (node)=>{
  if(!node) return
  console.log(node.value) // 访问节点
  preOrder(node.children ? node.children[0] : null) // 递归左树
  preOrder(node.children ? node.children[1] : null) // 递归右数
}
// 1,2,3,4,5,6,7,8,9,10,11

中序遍历

对于树中的任意节点来说，先打印它的左子树，然后再打印这个节点，最后打印它的右子树。

const inOrder = (node)=>{
  if(!node) return
  inOrder(node.children ? node.children[0] : null) // 递归左树
  console.log(node.value) // 访问节点
  inOrder(node.children ? node.children[1] : null) // 递归右数
}
// 4,,3,5,2,6,1,8,7,10,9,11

后序遍历

对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点。

const postOrder = (node)=>{
  if(!node) return
  postOrder(node.children ? node.children[0] : null) // 递归左树
  postOrder(node.children ? node.children[1] : null) // 递归右数
  console.log(node.value) // 访问节点
}
// 4,5,3,6,2,8,10,11,9,7,1

层级遍历

按照树的层级顺序打印节点

const levelOrder = (node)=>{
  if(!node.value) return
  const nodes = [] // 存储节点
  let length = [] // 临时数组，循环使用
  length.unshift(node) // push根节点
  while (length.length !==0 ){
    const item = length.shift() // 从临时数组中拿出
    nodes.push(item.value) // push节点列表
    const {children} = item // 遍历子节点
    if(children){
      children.forEach(n=>{
        length.push(n) // push临时数组
      })
    }
  }
  console.log(nodes)
  return nodes // 节点列表
}
// [1, 2, 7, 3,  6, 8, 9, 4, 5, 10, 11]