二叉树、完全二叉树、完满二叉树、满二叉树

大家好，欢迎来到IT知识分享网。

目录

一. 前言

二. 二叉树

2.1. 定义

2.2. 特点

2.3. 性质

三. 分类

3.1. 斜树

3.2. 完全二叉树(Complete)

3.3. 完满二叉树(Full)

3.4. 满二叉树(Perfect)

四. 存储类型

五. 遍历种类 

一. 前言

    前一篇我们介绍了树的概念及结点的概念，参见《数据结构-树》，树是数据结构中的重中之重，尤其以各类二叉树为学习的难点。一直以来，对于树的掌握都是模棱两可的状态，现在希望通过写一个关于二叉树的文章，在学习与总结的同时更加深入的了解掌握二叉树。

二. 二叉树

2.1. 定义

    简单定义：每个节点最多只有2个子节点的树叫做二叉树。

    专业定义：二叉树是n(n>=0)个结点的有限集合，该集合或者为空集（称为空二叉树），或者由一个根结点和两棵互不相交的、分别称为根结点的左子树和右子树组成。

    下图为一棵普通二叉树

2.2. 特点

2.3. 性质

一个编号为 i 的结点有如下特性：

三. 分类

3.1. 斜树

所有的结点都只有左子树的二叉树叫左斜树。所有结点都是只有右子树的二叉树叫右斜树。这两者统称为斜树。

左斜树

右斜树

3.2. 完全二叉树(Complete)

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

3.3. 完满二叉树(Full)

除了叶子结点之外的每一个结点都有两个孩子，每一层(当然包含最后一层)都被完全填充。

3.4. 满二叉树(Perfect)

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

四. 存储类型

顺序存储：二叉树的顺序存储结构就是使用一维数组存储二叉树中的结点，并且结点的存储位置，就是数组的下标索引。

二叉链表：如果顺序存储不能满足二叉树的存储需求，那么考虑采用链式存储。由二叉树定义可知，二叉树的每个结点最多有两个孩子。因此，可以将结点数据结构定义为一个数据和两个指针域。

五. 遍历种类 

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