二叉树的概念、存储及遍历

一、二叉树的概念

1、二叉树的定义

二叉树（ binary tree）是 n 个结点的有限集合，该集合或为空集（空二叉树），或由一个根结点与两棵互不相交的，称为根结点的左子树、右子树的二叉树构成。

二叉树的特点是：

（1）每个结点最多有两棵子树，故二叉树中不存在度大于 2 的结点。
（2）二叉树是有序的，其次序不能任意颠倒，即使树中的某个结点只有一棵子树，也要区分它是左子树还是右子树。
二叉树具有以下 5 种基本形态：

1、

2、特殊的二叉树

在实际应用中，常会用到以下几种特殊的二叉树。

1.斜树

所有的结点都只有左子树的二叉树称为左斜树，所有的结点都只有右子树的二叉树称为右斜树,在斜树中，每层只有一个结点，因此斜树的结点个数与其深度相同.

2.满二叉树

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

其特点是：

叶子只能出现在最下一层
只有度为 0、度为 2 的结点

由于满二叉树的特性可知：满二叉树在同样深度的二叉树中结点个数、叶结点个数最多。

3.完全二叉树

对一棵具 n 个结点的二叉树按层序编号，若编号为 i 的结点与同样深度的满二叉树中编号 i 的结点在二叉树中的位置完全相同，则称为完全二叉树，那么显然有：满二叉树是完全二叉树

其特点是：

(1)若i ≤ n / 2, 则结点i为分支结点，否则为叶子结点。
(2)叶子结点只可能在层次最大的两层上出现。对于最大层次中的叶子结点，都依次排列在该层最左边的位置上。
(3)若有度为1的结点，则只可能有一个，且该结点只有左孩子而无右孩子(重要特征)。
(4)按层序编号后，一旦出现某结点(编号为i)为叶子结点或只有左孩子，则编号大于i 的结点均为叶子结点。
(5)若n为奇数，则每个分支结点都有左孩子和右孩子;若n为偶数，则编号最大的分支结点(编号为n / 2 )只有左孩子，没有右孩子，其余分支结点左、右孩子都有。

简单来说，在满二叉树中，从最后一个结点开始，连续去掉任意个的结点，即是一棵完全二叉树

3、二叉树的性质

1.非空二叉树的第 i 层上行最多有 $2^{i-1}(i\geqslant 1)$ 个结点

2.在一棵深度为 k 的二叉树中，最多有 $2^{k}-1$ 个结点，最少有 k 个结点

推论：深度为 k 且具 $2^{k}-1$ 个结点的二叉树一定是满二叉树，但深度为 k 具有 k 个结点的二叉树不一定是斜树

3.任意一棵树，若结点数量为n ,则边的数量为n − 1 。

4.在一棵二叉树中，若叶结点个数为 $n_0$ ，度为 2 结点个数为 $n_2$ ，那么有： $n_0=n_2+1$

5.具有 n 个结点的完全二叉树的深度为 $\left \lfloor log_2\:n \right \rfloor +1$ ,

6.对完全二叉树按从上到下、从左到右的顺序依次编号1 , 2,...,n,则有以下关系:
(1)若 i=1，则：结点 i 为根节点；若 i>1，则：结点 i 的父结点编号为 i / 2,即当i 为偶数时，它是双亲的左孩子;当i为奇数时，它是双亲的右孩子。
(2)若2 i ≤ n 时，结点i 的左孩子编号为2 i , 否则无左孩子。

(3)若2 i + 1 ≤ n 时，结点i 的右孩子编号为2 i + 1 ，否则无右孩子。

(4)结点i 所在层次(深度)为 $\left \lfloor log_2\:n \right \rfloor +1$

4、二叉树的存储结构

1、顺序存储结构

二叉树的顺序存储结构是用一维数组存储二叉树中的结点，并用结点的存储位置表示结点间的逻辑关系（父子关系）

由于二叉树本身不具有顺序关系，因此二叉树的顺序存储结构要解决的关键问题是如何利用数组下标来反映结点间的逻辑关系。

由于完全二叉树中结点的层序编号可以唯一反映结点间的逻辑关系，因此对于一般的二叉树，可以添加一些不存在的空结点，使其成为一棵完全二叉树，再利用一维数组存储。

具体步骤为：

1、根节点编号为 1
2、若某结点 i 有左孩子，则其左孩子编号为 2i
3、若某结点 i 有右孩子，则其右孩子编号为 2i+1

缺陷：顺序存储会造成存储空间的浪费，最坏的情况是右斜树，一棵深度为 k 的右斜树，却要分配 $2^k-1$ 个存储空间。

因此，二叉树的顺序存储结构一般仅用于存储完全二叉树。

2、链式存储结构

既然顺序存储适用性不强，我们就要考虑链式存储结构。二叉树每个结点最多有两个孩子，所以为它设计一个数据域和两个指针域是比较自然的想法，我们称这样的链表叫做二叉链表。

lchild

data

rchild

其中data是数据域，lchild 和rchild都是指针域，分别存放指向左孩子和右孩子的指针。
以下是我们的二叉链表的结点结构定义代码。

/*二叉树的二叉链表结点构造定义*/
/*结点结构*/
struct BiTNode{
	TElemType data;	//结点数据
	BiTNode *lchild, *rchild;	//左右孩子指针
} BiTNode, *BiTree;  //根结点

容易验证，在含有n 个结点的二叉链表中，含有n + 1 个空链域。

二、遍历二叉树

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有结点，使得每个结点被访问一次且仅被访问一次。

1、先序遍历

先序遍历(PreOrder) 的操作过程如下：若二叉树为空，则什么也不做，否则，
1)访问根结点;
2)先序遍历左子树;
3)先序遍历右子树。

2、中序遍历

中序遍历( InOrder)的操作过程如下：若二叉树为空，则什么也不做，否则，
1)中序遍历左子树;
2)访问根结点;
3)中序遍历右子树。

3、后序遍历

后序遍历( InOrder)的操作过程如下：若二叉树为空，则什么也不做，否则，
1)中序遍历左子树;
2)中序遍历右子树。
3)访问根结点;

三种遍历算法中,递归遍历左、右子树的顺序都是固定的，只是访问根结点的顺序不同。不管采用哪种遍历算法，每个结点都访问一次且仅访问一次，故时间复杂度都是O(n)。在递归遍历中，递归工作栈的栈深恰好为树的深度，所以在最坏情况下，二叉树是有n个结点且深度为n的单支树，遍历算法的空间复杂度为O(n)。