二叉树性质

二叉树定义

二叉树（Binary Tree）是 n（n >= 0）个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别
称为根结点的左子树和右子树的二叉树组成。

二叉树的特点：

• 每个结点最多有两棵子树
• 左子树和右子树有顺序
• 树中某个结点只有一棵子树，也要区分是左子树还是右子树。树1和树2是同一棵树，但它们却是不同的二叉树。

[图片上传失败...(image-20814c-1652521949356)]

二叉树的五种基本形态：

• 空二叉树
• 只有一个根结点
• 根结点只有左子树
• 根结点只有右子树
• 根结点既有左子树又有右子树

特殊二叉树

1.斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。统称斜树。

线性表结构可以理解为是树的一种极其特殊的表现形式。（斜树）

2.满二叉树

在一棵二叉树中，所有分支结点都存在左子树和右子树，并且所有叶子都在同一层上，这样的二叉树称为满二叉树。

满二叉树特点：

• 叶子只能出现在最下一层
• 非叶子结点的度一定是2
• 同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

对一棵具有n个结点的二叉树按层序编号，如果编号为i（1 <= i <= n）的结点与==同样深度的满二叉树==中编号为i的结点在二叉树中位置
完全相同，则这棵二叉树称为完全二叉树。

==满二叉树一定是一棵完全二叉树，但完全二叉树不一定是满二叉树。==

完全二叉树如下图：
[图片上传失败...(image-583a7a-1652521949356)]

非完全二叉树如下图：
[图片上传失败...(image-7313b4-1652521949356)]

完全二叉树特点：

• 叶子结点只能出现在最下两层。
• 最下层的叶子一定集中在左部连续位置。
• 倒数第二层，如果有叶子结点，一定在右部连续位置。
• 如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况。
• 同样结点数的二叉树，完全二叉树的深度最小。

二叉树性质

1. 在二叉树的==第i层==上至多有2^(i-1)个结点（i>=1）
2. 深度为k的二叉树至多有2^k - 1个结点（深度为k意思就是有k层的二叉树）
3. ==对任何一棵二叉树T，如果终端结点数为n0，度为2的结点数为n2，则n0 = n2 + 1==
4. 具有n个结点的完全二叉树的最大深度为log2 n + 1 （取最大整数） （==这里有个疑问？是不是log2(2n+1)？==）