点击上方蓝色字体，选择“置顶或者星标” 

二叉树简介

二叉树是由n（n>=0）个结点（Node）组成的有序集合，集合或者为空，或者是由一个根节点加上两棵分别称为左子树和右子树的、互不相交的二叉树组成。n=0时称为空二叉树。二叉树的五种形态：

特点

由二叉树定义以及图示分析得出二叉树有以下特点：

• 每个结点最多有两颗子树，所以二叉树中不存在度大于2的结点。
• 左子树和右子树是有顺序的，次序不能任意颠倒。
• 即使树中某结点只有一棵子树，也要区分它是左子树还是右子树。

性质

• 在二叉树的第i层上最多有2i-1 个节点 。（i>=1）
• 二叉树中如果深度为k,那么最多有2k-1个节点。(k>=1）
• n0=n2+1 n0表示度数为0的节点数，n2表示度数为2的节点数。
• 在完全二叉树中，具有n个节点的完全二叉树的深度为[]+1，其中[]是向下取整。
• 若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点有如下特性：

(1) 若 i=1，则该结点是二叉树的根，无双亲, 否则，编号为 [i/2] 的结点为其双亲结点;
(2) 若 2i>n，则该结点无左孩子， 否则，编号为 2i 的结点为其左孩子结点；
(3) 若 2i+1>n，则该结点无右孩子结点， 否则，编号为2i+1 的结点为其右孩子结点。

分类

斜二叉树

只有左子节点或只有右子节点的二叉树称为斜二叉树。

特点：

• 度为1；
• 只有左子节点或右子节点；

满二叉树

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

• 叶子只能出现在最下一层。出现在其它层就不可能达成平衡。
• 非叶子结点的度一定是2。
• 在同样深度的二叉树中，满二叉树的结点个数最多，叶子数最多。

完全二叉树

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

特点：

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

注：满二叉树一定是完全二叉树，但反过来不一定成立。

二叉树遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有节点，使得每个节点被访问依次且仅被访问一次。二叉树的遍历次序不同于线性结构，线性结构最多也就是分为顺序、循环、双向等简单的遍历方式。而树不存在唯一的后继节点，在访问一个节点后，下一个被访问的节点面临着不同的选择，所以我们需要规范遍历方式。

前序遍历：

定义：先访问根节点，然后访问左子树，再访问右子树；
按照定义遍历的顺序遍历结果为：A B D H I E J C F K G
访问顺序如下图：

中序遍历：

定义：先访问左子树，再访问根节点，最后访问右子树；
按照定义遍历的顺序遍历结果为：H D I B E J A F K C G
访问顺序如下图：

后序遍历：

定义：先访问左子树，再访问右子树，最后访问根节点；
按照定义遍历的顺序遍历结果为：H I D J E B K F G C A
访问顺序如下图：

层次遍历：

定义：逐层的从根节点开始，每层从左至右遍历；
按照定义遍历的顺序遍历结果为：A B C D E F G H I J K
访问顺序如下图：

二叉树存储结构

顺序存储结构

二叉树的顺序存储，就是用一组连续的存储单元存放二叉树中的结点。因此，必须把二叉树的所有结点安排成为一个恰当的序列，结点在这个序列中的相互位置能反映出结点之间的逻辑关系，用编号的方法从树根起，自上层至下层，每层自左至右地给所有结点编号,缺点是有可能对存储空间造成极大的浪费，在最坏的情况下，一个深度为k且只有k个结点的右单支树需要2k-1个结点存储空间。依据二叉树的性质，完全二叉树和满二叉树采用顺序存储比较合适，树中结点的序号可以唯一地反映出结点之间的逻辑关系，这样既能够最大可能地节省存储空间，又可以利用数组元素的下标值确定结点在二叉树中的位置，以及结点之间的关系。下图是完全二叉树的顺序存储结构：

对于一般的二叉树，如果仍按从上至下和从左到右的顺序将树中的结点顺序存储在一维数组中，则数组元素下标之间的关系不能够反映二叉树中结点之间的逻辑关系，只有增添一些并不存在的空结点，使之成为一棵完全二叉树的形式，然后再用一维数组顺序存储。下面给出了一棵一般二叉树改造后的完全二叉树形态和其顺序存储状态示意图。显然，这种存储对于需增加许多空结点才能将一棵二叉树改造成为一棵完全二叉树的存储时，会造成空间的大量浪费，不宜用顺序存储结构。

最坏的情况是右单支树，如图所示，一棵深度为k的右单支树，只有k个结点，却需分配2k－1个存储单元。

链式存储机构

二叉树的链式存储结构是指，用链表来表示一棵二叉树，即用链来指示元素的逻辑关系。通常的方法是链表中每个结点由三个域组成，数据域和左右指针域，左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址。其结点结构为：

其中，data域存放某结点的数据信息；lchild与rchild分别存放指向左孩子和右孩子的指针，当左孩子或右孩子不存在时，相应指针域值为空（用符号∧或NULL表示）。利用这样的结点结构表示的二叉树的链式存储结构被称为二叉链表，如图所示。