二叉树

一、定义

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

二叉树.png

二、二叉树的特点

1.每个结点最多有两棵子树，所以二叉树中不存在度大于2的结点。

注意：不是都需要两棵子树，而是最多可以是两棵，
没有子树或者有一棵子树也都是可以的。

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

3.即使树中某结点只有一棵子树，也要区分它是左子树还是右子树，下面是完全不同的二叉树：

二叉树1.png 二叉树2.png

二叉树的五种基本形态

①空二叉树

空二叉树.png

②只有一个根结点

只有一个根结点.png

③根结点只有左子树

根结点只有左子树.png

④根结点只有右子树

根结点只有右子树.png

⑤根结点既有左子树又有右子树

根结点既有左子树又有右子树.png

拥有三个结点的普通树只有两种情况：两层或者三层。
但对于二叉树来说，由于要区分左右，所以就演变成五种形态：

1.png 2.png 3.png 4.png 5.png

三、特殊二叉树

1.斜树

顾名思义，斜树是一定要斜的，但只能在一条线上斜；如图：

斜树1.png 斜树2.png

2.满二叉树

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

满二叉树.png

满二叉树的特点：

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

3.完全二叉树

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

完全二叉树.png

完全二叉树的特点：

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

注意：满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树。

以下这些都不是完全二叉树：

①缺少A结点：

缺少A.png

②缺少6、7结点

缺少6、7.png

③缺少A、B结点

缺少A、B.png

四、二叉树的性质

1.性质一

在二叉树的第i层上至多有2^(i-1)个结点(i>=1)

2.性质二

深度为k的二叉树至多有2^{k-1个结点(k>=1)。（是2}k再-1）

3.性质三

对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1

推导：

• 首先我们再假设度为1的结点数为n1，则二叉树T的结点总数n=n0+n1+n2
• 其次我们发现连接数总是等于总结点数n-1，并且等于n1+2*n2
• 所以n-1=n1+2*n2
• 所以n0+n1+n2-1=n1+n2+n2
• 最后n0=n2+1

4.性质四

具有n个结点的完全二叉树的深度为⌊log₂n⌋+1（⌊⌋：取下限）

由满二叉树的定义结合性质二我们知道，深度为k的满二叉树的结点树n一定是2^k-1
那么对于满二叉树我们可以通过n=2^k-1倒推得到满二叉树的深度为k=log₂(n+1)
由于完全二叉树前边我们已经提到，它的叶子结点只会出现在最下面的两层，我们可以同样如下推导

• 那么对于倒数第二层的满二叉树我们同样很容易回推出它的结点数为n=2^(k-1)-1
• 所以完全二叉树的结点数的取值范围是：2^(k-1)-1 < n <= 2^k-1
• 由于n是整数，n <= 2^k-1可以看成n < 2^k
• 同理2^(k-1)-1 < n可以看成2^(k-1) <= n
• 所以2^(k-1) <= n < 2^k
• 不等式两边同时取对数，得到k-1<=log₂n<k
• 由于k是深度，必须取整，所以k=⌊log₂n⌋+1

5.性质五

如果对一棵有n个结点的完全二叉树(其深度为⌊log₂n⌋+1)的结点按层序编号，对任一结点i(1<=i<=n)有以下性质：

• 如果i = 1，则结点 i 是二叉树的根，无双亲；如果i > 1，则其双亲是结点⌊i/2⌋
• 如果2i > n，则结点 i 无做左孩子(结点 i 为叶子结点)；否则其左孩子是结点2i
• 如果2i+1 > n，则结点 i 无右孩子；否则其右孩子是结点2i+1

五、二叉树的存储结构

二叉树是一种特殊的树，由于它的特殊性，使得用顺序存储结构或链式存储结构都能够简单实现。
二叉树的顺序存储结构就是用一维数组存储二叉树中的各个结点，并且结点的存储位置能体现结点之间的逻辑关系。

二叉树的顺序存储结构.png

由于他的严格定义，在数组直接能表现出逻辑结构。

对于一般的二叉树，尽管层序编号不能反映逻辑关系，但是也可以按照完全二叉树编号方式修改一下，把不存在的结点用“^”代替即可。

完全二叉树存储结构.png

如果是一个右斜树，那么如图：

右斜树顺序存储结构.png

六、二叉链表

顺序存储方式的适用性不强，那么我们就要考虑链式存储结构。
二叉树的存储按照国际惯例来说一般也是采用链式存储结构的。

1.定义：

二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

二叉链表.png

二叉链表的结点结构定义代码：

typedef struct BiTNode
{
    ElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

二叉链表结构.png