二叉树

二叉树

第一层是1个根节点，最多有2个字节点，分别是左子节点和右子节点，也可以没有字节点的树，第i层最多有 $2^{i-1}$个节点。

满二叉树

每一层节点都是满的。 一个n层的满二叉树，一共有 $2{n}-1$ 个节点。

完全二叉树

定义：只有最后一层缺失节点，而且缺失的节点都在最后（可以是右边，也可以是左边，一般是缺右边子节点） 一个节点总数为k的完全二叉树，设1号节点为根节点，有一下性质： xxx 数组存储空间需要设置为节点数的4倍

二叉树的遍历

BFS 使用队列

DFS 使用栈

前序遍历

def preorder(node:Node):
  print(node.value)
  preorder(node.left)
  preorder(node.right)

中序遍历

def inorder(node:Node):
  inorder(node.left)
  print(node.value)
  inorder(node.right)

后序遍历

def postorder(node:Node) {
  postorder(node.left)
  postorder(node.right)
}

已知“中序遍历结果+前序遍历结果”或“中序遍历结果+后序遍历结果”，可以确定一颗二叉树。 必须要知道“中序遍历结果”，因为存在前序遍历结果和后序遍历结果都相同的，而实际中序遍历结果不同的二叉树。