国内教程和国外对满二叉树的定义有一些的区别。
一、国内满二叉树
1、定义
如果一个二叉树的每一层的节点数都达到最大值，则这个二叉树就是满二叉树。也即如果一个二叉树有n层，且节点总数为(2^n)-1，则它就是满二叉树。如下图就是国内教程版满二叉树：
image
2、特点
1）从外形上来看，满二叉树一个三角形。
2）从数学角度上来看，各个层的节点数遵循一个首项为1，公比为2的等比数列。由此满二叉树又满足以下性质：
a、一个k层的满二叉树总节点数为2^k-1，且节点数一定为基数个。
b、第n层上的节点数位2^(n-1)个。
c、一个k层的满二叉树的叶子节点个数（也即最后一层节点个数）为2^(k-1)个。
二、国外满二叉树
1、定义
如果一个二叉树的节点有两个子节点，或者要么它自己是叶子节点，则这个二叉树为满二叉树（*a binary tree T is full if each node is either a leaf or possesses exactly two childnodes*）。如下图为国外版满二叉树：
image
2、特点
每个节点要么没有子节点，要么有两个子节点（国内版则必须要有2个子节点）；也即要么度为0，要么度为2，不存在度为1的节点。因此上图是不满足国内版满二叉树定义的。
网友评论