什么是完全二叉树和线索二叉树，它们的顺序存储结构是怎样的？

本文共计3672个文字，预计阅读时间需要15分钟。

在上文中，我们学习了二叉树的基本链式结构以及建树和遍历等相关操作。今天，我们要学习一些关于二叉树的概念以及二叉树的一种变形式——完全二叉树。完全二叉树是什么呢？

在上篇文章中，我们学习了二叉树的基本链式结构以及建树和遍历相关的操作。今天我们学习的则是一些二叉树相关的概念以及二叉树的一种变形形式。

完全二叉树

什么叫完全二叉树呢？在说到完全二叉树之前，我们先说另外一个名词：“满二叉树”。像我们之前文章中演示过的那个二叉树，就是一颗“满二叉树”。在这颗树中，所有的结点都有两个孩子结点，没有哪个结点是只有一个孩子结点的，并且所有最底层的叶子结点都在同一层，这种树就称为“满二叉树”，也称为“完美二叉树”。

是不是非常漂亮的一颗树？没错，这种二叉树非常地完美，它没有多余的结点，也没有缺少的结点，非常的漂亮。但是，在现实中，完美的东西是很稀少的，人生总会有一点缺憾嘛。我们尽量不要让自己有太多的缺憾，但也总不能过上没有一丝缺憾的人生。所以，我们允许叶结点出现在最下层和次下层，而且最下层的叶结点集中在树的左部，也就是叶结点只能有左子树，那么，这样的一颗略带缺憾的树就叫做“完全二叉树”。不要担心它不完美，因为这样略带缺憾的人生才是完整的嘛，所以“完全二叉树”是一种理想的树结构。

从定义中，我们可以看出，一颗“满二叉树”，必定是一颗“完全二叉树”，而一颗叶子结点都在一层的并且所有结点都有左右孩子结点的“完全二叉树”也就是一颗”满二叉树“。

为什么要讲”满二叉树“和”完全二叉树“呢？当然是为了我们接下来的内容做铺垫。因为”满二叉树“是最符合二叉树性质的一颗树。还记得树系列的第一篇文章中介绍过的二叉树的那五个性质吗？当时我们就是以那颗”满二叉树“为例进行讲解的。