前言

废话不多，数据结构必须学！ 每天更新一章，一篇写不完的话会分成两篇来写~

资料获取

6.4 二叉树的定义

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

看一个不是二叉树的情况

D结点不满足二叉树，因为它有三个子树

6.4.1 二叉树特点

1.每个结点最多有两颗子树，所以二叉树中不存在大于2的结点。不是只有两颗子树，而是最多有。没有子树或者一颗子树的也是可以的！

2.左子树和右子树是有顺序的，次序不能任意颠倒

3.即使树中某结点只有一棵子树，也要区分它是左子树还是右子树

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

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

5个结点的树有5中二叉树的形态

6.4.2 特殊二叉树

1.斜树

顾名思义，斜树一定要是斜的，但是往哪斜还是有讲究。所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树

上面的树2就是左斜树，树5就是右斜树

其实线性表结构就可以理解为是树的一种极其特殊的表现形式

2.满二叉树

人有悲欢离合，月有阴晴圆缺，此事古难全

理想是完美的，不完美才是人生

完美的二叉树就叫满二叉树

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

满二叉树的特点有：

(1)叶子只能出现在最下一-层。出现在其他层就不可能达成平衡。 (2)非叶子结点的度一-定是2。否则就是“缺胳膊少腿”了。 (3)在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

3.完全二叉树

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

满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树

只能最后一层右边缺，其他地方缺都必须是连续的，不连续就不是完全二叉树

如下图所示

完全二叉树的特点：

1.叶子结点只能出现在最下两层

2.最下层的叶子一定集中在左部连续位置

3.倒数二层，若有叶子结点，一定都在右部连续位置。

4.如果结点度为1，则该结点只有左孩子，即不存在只有右子树的情况

5.同样结点数的二叉树，完全二叉树的深度最小