一.基础概念

1.度：

结点拥有的子树个数称为结点的度，

2.叶子结点

度为0的结点称为叶子结点；

3.树的度：

是树中所有结点度的最大值
image.png

4.高度：

树中结点的最大层次称为树的高度（深度）
image.png

二.二叉树分类：

1.满二叉树

所有分支结点都有左右两个子树，所有叶子结点都在一层上，这样的二叉树称为满二叉树；

2.完全二叉树：

1）对于一个具有n个结点的二叉树，根据层序编号，如果编号为i(1=2）满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树

三.二叉树的性质：

1. 性质1

二叉树深度为i的层上，至多有2^(i-1)个结点

2.性质2

深度为k的二叉树，至多有2^k-1个结点（k>=1)

3.性质三

对于任何二叉树T，如果叶子结点为N1，度为2的结点树为N2,则N1 = N2+1;

4.性质4

有N个结点的完全二叉树的深度为[log2^N]+1 ([log2^N]表示log2^N的整数部分）