二叉树的定义、性质及遍历算法

1 二叉树的定义

二叉树(Binary Tree)是$n(n\ge 0)$个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根节点和两棵互不相交的、分别称为根节点的左子树和右子树的二叉树组成，如下图所示。

1.1 二叉树的特点

二叉树的特点有：

• 每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点，没有一棵子树或者由一棵子树都是可以的。

• 左子树和右子树是有顺序的，次序不能颠倒。

• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。如图所示，树1和树2是同一棵树，但他们确实不同的二叉树。

  

二叉树具有五种基本形态：

1. 空二叉树。
2. 只有一个根结点。
3. 根结点只有左子树。
4. 根结点只有右子树。
5. 根结点既有左子树又有右子树。

1.2 特殊二叉树

1. 斜树

   所有的结点都只有左子树的二叉树叫左斜树。所有结点都只有右子树的二叉树叫右斜树。这两者统称为斜树。斜树有很明显的特点，就是每一层都只有一个结点，结点的个数与二叉树的深度相同。

   

   

2. 满二叉树

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

   

   单是每个结点都存在左右子树，不能算是满二叉树，还必须要所有叶子都在同一层上，这就做到了整棵树的平衡。满二叉树的特点有：

   1. 叶子只能出现在下一层。出现在其他层就不可能达到平衡。
   2. 非叶子结点的度一定为2.
   3. 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3. 完全二叉树

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

   

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

   完全二叉树的特点：

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

2 二叉树的性质

性质1：在二叉树的第$i$层至多有$2^i-1$个结点($i\ge 1$)

​

​ 第一层是根结点，只有一个，所以$2^{1-1}=2^0=1$。

​ 第二层有两个，$2^{2-1}=2^1=2$。

​ 第三层有四个，$2^{3-1}=2^2=4$。

​ 第四层有八个，$2^{4-1}$