满二叉树(Full Binary Tree)和完全二叉树(Complete Binary Tree)是二叉树的两种特殊形式。满二叉树是指每个节点都有两个子节点,或者没有子节点(即每个节点的度都是2或者0)。完全二叉树是指除了最后一层之外,其他层的节点度都达到最大值,并且最后一层的节点尽可能集中在左侧。
之所以说“满二叉树也是完全二叉树”,是因为满二叉树满足完全二叉树的定义。在满二叉树中,除了最后一层之外,其他各层的节点度都达到了最大值,也就是说,除了最后一层的节点可能没有左孩子或右孩子之外,其他各层的节点都有两个子节点。同时,由于满二叉树中所有节点都有两个子节点或没有子节点,所以最后一层的节点也尽可能集中在左侧。因此,满二叉树是一种特殊的完全二叉树。
需要注意的是,虽然满二叉树是完全二叉树的一种特殊形式,但并非所有的完全二叉树都是满二叉树。例如,一个完全二叉树可能存在某个节点只有左孩子而没有右孩子的情形,此时该树就不是满二叉树。
满二叉树一定是完全二叉树,但完全二叉树不一定是满二叉树。
满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点的二叉树;完全二叉树:除最后一层外,每一层上的节点数均达到最大值;在最后一层上只缺少右边的若干结点。