二叉树相关

二叉树的两个分类

满二叉树：所有非叶子节点都有左右子树，所有叶子节点都在一层


完全二叉树：有n个节点的二叉树，如果编号为i的节点与同样深度的满二叉树中节点i的位置完全相同。

满二叉树一定是完全二叉树，反之不一定成立。

二叉树的层数与节点数(根节点在第1层)

• 二叉树第k层最多为2^(k-1)个节点
• 二叉树深度为k，则最多有2^k-1个节点
• 在完全二叉树中，具有n个节点的完全二叉树深度为[log(2底)n]+1，其中[log(2底)n]是向下取整。

二叉树的遍历

已知两种遍历顺序，还原二叉树结构

一般有两类：

1. 已知：前序+中序 -> 后序
2. 已知：中序+后序 -> 前序
   注：不知道中序是无法确定二叉树结构的

例1：
前序：ABDGHCEFI
中序：GDHBAECIF

step1:前序确定根节点A，中序确定左右子树包含哪些节点

    A

DDHB ECIF

step2:递归确定左右子树的根节点及其左右子树

    B

GDH

    C

E IF

    D

G H

     F

I

因此后序：GHDBIFCA

例2：
中序：ADEFGHMZ
后序：AEFDHZMG

step1:后序确定根节点A，中序确定左右子树包含哪些节点

    G

ADEF HMZ

    D

A EF

    M

H Z

    F

E

前序遍历：DGDAFEMHZ