二叉树

1二叉树的定义及其主要特征

1.1二叉树的定义

​ 二叉树是 n（n≥0）个结点的有限集合：

​ （1）或者为空二叉树，即 n = 0。

​ （2）或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。

1.2二叉树的特点

​ （1）每个结点至多只有两棵子树；

​ （2）左右子树不能颠倒（二叉树是有序树），因此，二叉树有五种基本形态。

1.3二叉树的五种形态

1.4二叉树与度为2的有序树的区别

​ （1）度为 2 的树至少有 3 个结点，而二叉树可以为空。

​ （2）度为 2 的有序树的孩子的左右次序是相对于另一孩子而言的，若某个结点只有一个孩子，则这个孩子就无须区分其左右次序；而二叉树无论其孩子数是否为 2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言，而是确定的。

1.5几个特殊的二叉树

​ 1.满二叉树

​ 一棵深度为 k，且有2^k − 1 个结点的二叉树称为满二叉树（Full Binary Tree）。它的特点是每一层上的结点数都达到了最大，即对给定的高度，它是具有最多结点数的二叉树。满二叉树中不存在度为 1 的结点（除叶子结点之外的每个结点度数均为 2），每个分支结点均有两棵高度相同的子树，且所有叶子都在最下一层上。

​ 可以对满二叉树按层序编号：约定编号从根结点(根结点编号为 1)起，自上而下，自左向右。这样，每个结点对应一个编号，对于编号为 i 的结点，若有双亲，则其双亲为⌊ i/2 ⌋ ，若有左孩子，则左孩子为 2i；若有右孩子，则右孩子为 2i+1。

​ 2.完全二叉树

​ 如果深度为 k，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 到 n 的结点一一对应，则该二叉树称为完全二叉树，其特点如下：

​ （1）若 i≤⌊ n/2 ⌋ ，则结点 i 为分支结点，否则为叶子结点

​ （2）叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。

​ （3）若有度为 1 的结点，则只可能有一个，且该结点只有左孩子而无右孩子（重要特征）。

​ （4）按层序编号后，一旦出现某结点（编号为 i）为叶子结点或只有左孩子，则编号大于 i 的结点均为叶子结点。

​ （5）若 n 为奇数，则每个分支结点都有左孩子和右孩子；若 n 为偶数，则编号最大的分支结点（编号为 n/2）只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

​ 3.二叉排序树

​ 二叉排序树或者是空二叉树，或者是具有如下性质的二叉树：

​ （1）左子树上所有结点的关键字均小于根结点的关键字；右子树上的所有结点的关键字均大于根结点的关键字。

​ （2）左子树和右子树又各是一棵二叉排序树。

​ 4.平衡二叉树

​ 平衡二叉树上任一结点的左子树和右子树的深度之差不超过 1。

1.6二叉树的性质

​ 因为二叉树也是一棵树，所以二叉树的性质是树的性质的一种特殊情况。

​ 1.二叉树性质 1：

​ 设非空二叉树中，度为 0、1 和 2 的结点个数分别为n0、n1和n2，则n0=n2+1（叶子结点比二分支结点多一个）。

​ 2.二叉树性质 2：

​ 二叉树第 i 层至多有2 ⁱ⁻¹个结点（i≥1）；m 叉树第 i 层至多有mⁱ⁻¹个结点（i≥1）。

​ 3.二叉树性质 3：

​ 高度为 h 的 m 叉树至多有(m^h -1)/(m-1)个结点（h≥1）；高度为 h 的二叉树至多有2 ^h -1 个结点。

​ 4.二叉树性质 4：

​ 具有 n（n>0）个结点的完全二叉树的深度为⌊ log2 n ⌋ + 1 或⌈ log2 (n + 1) ⌉ 。

​ 5.二叉树性质 5：

​ 如果对一棵有 n 个结点的完全二叉树（其深度为⌊ log2 n ⌋ + 1）的结点按层序编号（从第 1 层到⌊ log2 n ⌋ + 1 层，每层从左到右），则对任一结点 i（1≤i≤n），有：

​ （1）若 i=1，则结点 i 是二叉树的根，无双亲；若 i>1，则其双亲是结点 ⌊ i/2 ⌋ 。

​ （2）若 2i>n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i。完全二叉树中的结点若无左孩子，则肯定也无右孩子，即为叶子，故编号 i>⌊ n/2 ⌋ 的结点必定是叶子。

​ （3）若 2i+1>n，则结点 i 无右孩子，否则其右孩子为结点 2i+1。

​ （4）结点 i 所在层次（深度）为⌊ log2 n ⌋ +1。

2二叉树的存储结构

2.1二叉树的顺序存储

​ （1）二叉树的顺序存储

​ 定义一个长度为 MaxSize 的数组 t，按照从上至下、从左至右的顺序依次存储完全二叉树中的各个结点。满二叉树和完全二叉树最适合这种存储方式。其他的二叉树一定要把二叉树的结点编号与完全二叉树对应起来。

​ 此外，这种存储方式建议从数组下标 1 开始存储，否则在使用二叉树的性质时可能出错。

​ （2）二叉树顺序存储的部分性质：

i 的左孩子	2i
i 的右孩子	2i+1
i 的父节点	⌊ i/2 ⌋
i 所在的层次	⌈ log2 (n + 1) ⌉ 或 ⌊ log2 n ⌋ + 1

​ （3）有 n 个结点的完全二叉树的部分判断条件

判断 i 是否有左孩子？	2i≤n？
判断 i 是否有右孩子？	2i+1≤n？
判断 i 否是叶子/分支结点？	i＞ ⌊ n/2 ⌋ ？

2.2二叉树的链式存储

​ 对于一般的二叉树，通常采用链式存储方式。二叉树中每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域的链式结点结构是很自然的想法。

​ 1.二叉链表

​ 在二叉树中，结点结构通常包括若干数据域和若干指针域，而二叉链表至少包含 3 个域：数据域 data 左指针域 lchild 和右指针域 rchild。

//二叉树的结点（链式存储）
typedef struct BiTNode{ElemType data; 						//数据域struct BiTNode *lchild,*rchild; 	//左、右孩子指针
}BiTNode,*BiTree;

​ 显然，在含有 n 个结点的二叉链表中，含有 n+1 个空链域(重要结论，选择题经常出现)。这是因为，每个叶结点有 2 个空指针，每个度为 1 的结点有 1 个空指针，所以总共有 2n₀+n₁个空指针。

又由二叉树的性质 1 可知，n₀=n₂+1，而二叉树中，n=n₀+n₁+n₂，所以二叉链表中的空指针总数为2n₀+n₁=n₀+n₀+n₁=n₂+1+n₀+n₁=n+1。这些空链域可以用来组成后面我们会提到的另一种链表结构：线索链表。

​ 2.三叉链表

​ 相较于二叉链表，三叉链表增加了一个指向其父节点的指针，可以更加方便地找到结点的父节点。

typedef struct TriTNode{ElemType data; 						//数据域struct TriTNode *Lchild,*rchild; 	//左、右孩子指针struct TriTNode *parent; 			//父节点指针
}TriTNode,*TriTree;