二叉树和特殊二叉树的介绍、性质和性质

1。二叉树简介

二叉树是 n (n>=0) 个节点的有限集合。该集合要么是空集（称为空二叉树），要么由一个根节点和两个不相交的左子树子树和右子树（分别称为根节点）组成。

如图

如图，每个结最多有一个左结和一个右结，没有多余的结。这是二叉树

2 的一个明显属性。二叉树的性质

根据二叉树的定义和图形分析，可以得出二叉树具有以下性质：

1）每个节点最多有两个子树，因此不存在有度的节点二叉树中大于2的点。

2）Put和右子树是有序的，不能随意改变顺序。

3）即使树节点中只有一棵子树，也要区分它是左子树还是真正的子树。

3。二叉树的性质

二叉树具有以下性质

性质 1：二叉树第 i 层的节点数最多为 2 (i-1) 的节点次方 (i ≥ 1) 。
性质2：深度为k的二叉树最多有2 k-1个节点（k≥1）。
性质3：具有N个节点的二叉树的高度至少为log2(n+1)。
性质4：任意二叉树中，若终端节点数为n0，度节点数为n2，则n0=n2+1。

4。几种特殊的二叉树

l 偏斜树

偏斜树：所有节点都只有左子树的二叉树，称为左偏斜树。所有节点都只有右子树的二叉树称为右偏树。两者统称为歪树。

图中，一棵树向左倾斜

l 满二叉树

满二叉树：在二叉树中。如果所有分支节点都有左子树和右子树，并且所有叶子都在同一级，这样的二叉树称为满二叉树。

满二叉树的属性是：

1）叶子只能在最低层可见。通过在其他层面上表现来达到平衡是不可能的。

2）非叶子节点的度数必须为2。

3）在相同深度的二叉树中，满二叉树的节点数最多，叶子也最多。

图为一棵完全二叉树

l 完全二叉树

完全二叉树：n个节点的二叉树按层编号。如果编号为 i (1