二叉树( binary tree )是有限节点集合构成的结构,其结构的递归定义为:
所以节点个数为零的空树也是二叉树,二叉树根节点的左、右子树也是二叉树,其结构同样符合以上定义,当左子树为空树时,表示根节点没有左子节点。且二叉树区分左、右子树,以下两个二叉树为不同的二叉树。
one
another one
首先说明下几个概念:
关于高度和深度的起始值 0 或 1 的个人看法:
对于深度、高度和层数的起点值,可能有些地方基数是从1开始计算的。对于这个起点值的设置,个人觉得如果你高兴,从10086开始也无妨,因为在应用中,这些数据量只是为了方便计算,起作用的只是相对值而已。
为了方便理解,这里设置基数为0,深度可以认为是从水平面,也就是0深度,往下有几层,深度就是几;高度类似理解,地平面是0,往上有几层,高度就是几。
参考下图:
图片来源:What is the difference between tree depth and height?
关于完全二叉树和满二叉树的定义,因为最初翻译的不同,已经混淆很久了,所以已经属于一个历史问题了。这里尽量不去分辨哪一种定义是正确的,只按照个人的理解去描述。
示例:
Full Binary Tree
示例:
Complete Binary Tree
示例:
Perfect Binary Tree
以上概念参考:
下面介绍二叉树几个数据量之间的关系,变量声明如下:
:树的高度
:节点总数
:度为 0 的节点个数,即叶子节点个数
:度为 1 的节点个数
:度为 2 的节点个数
:第
层上节点个数
层上节点个数为:
proof: 1.第 0 层上,只有根节点,所以 0 层节点个数为:
; 2.每层节点度都为 2 ,所以下一层的节点个数为:
; 3.所以第
层节点个数为:
。
的完美二叉树,节点总数为:
proof: 1.每层的节点个数
构成等比数列,公比为:
; 2.第 0 层节点个数
,所以总节点个数为:
的完美二叉树,非叶子节点和叶子节点的个数有:
,节点总数与叶子节点个数有:
proof: 深度为
的完美二叉树,则
层节点即为叶子节点,即:
,由以上结论可知,深度为
的完美二叉树,叶子节点个数为
,总节点个数为
,所以非叶子节点个数为:
,即:
,
与度为 2 的节点个数
关系为:
proof: 1.设度为 1 的节点个数为
,则节点总数
2.设二叉树中边的个数为
,有如下关系: 【1】树中除根节点外,每个节点都存在该节点到其父节点的一条边,即除根节点外,每个节点都对应着一条边,则有关系:
【2】树中每个节点度,表示该节点的子节点个数,也表示着该节点对应的边的个数,则有关系:
根据【1】【2】可知,有关系:
,根据 1 中
,则有:
,即:
,二叉树中叶子节点个数为度为 2 的节点个数加 1。