完全二叉树
对于一棵具有n个节点的二叉树（按层序编号），
如果编号为i的节点与同样深度的满二叉树中编号为i的节点在二叉树的位置完全相同，
则为完全二叉树。
换句话来说，如果每个节点按照满二叉树的结构逐层顺序进行编号，如果编号出现编号空挡，就说明不是完全二叉树，否则就是。如下图所示：
完全二叉树
左边二叉树按照完全二叉树进行编号，出现了10号的空挡，右边二叉树出现了6,7号的空挡，所以以上两棵树都不是完全二叉树。
二叉树的遍历
二叉树的遍历主要包括
前序遍历、中序遍历、后序遍历和层序遍历四种，
其中前三种是非常常用的，下面主要介绍前三种遍历的方法。
- 前序遍历
若二叉树为空，则空操作返回，
否则先访问根节点，然后前序遍历左子树，再前序遍历右子树。
如下图所示：
前序遍历
- 中序遍历
若二叉树为空，则空操作返回，
否则从根节点开始（注意不是先访问根节点），
中序遍历根节点的左子树，然后是访问根节点，最后中序遍历右子树。
如下图所示：
中序遍历
- 后序遍历
若二叉树为空，则空操作返回，
否则从左到右先叶子后节点的方式遍历访问左右子树，最后是访问根节点。
后序遍历
遍历的性质
两个二叉树遍历的性质：
1、已知前序遍历和中序遍历，可以唯一的确定一个二叉树；
2、已知后序遍历和中序遍历，可以唯一的确定一个二叉树；
网友评论