二叉树（二）中，如何实现高效的遍历算法？

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

二叉树的概念及结构概念：一种有限的节点集合，该集合或为空集，或由一个根节点和两个不相交的、分别称为左子树和右子树的二叉树组成。结构：一个二叉树由根节点、左子树和右子树组成。左子树和右子树都是二叉树，且左子树和右子树的结构相同。

从上图可以看出：

1.二叉树不存在度大于1的结点。

二叉树的概念及结构

概念

一颗二叉树是结点的有限集合，该集合或者为空，或者由一个根节点加上两棵别称为左子树和右子树的二叉树的组成。

从上图可以看出：

1.二叉树不存在度大于2的结点；

2.二叉树的子树有左右之分，次序不能颠倒，因此二叉树是有序树。

注意：对于任意的二叉树都是由以下几种情况复合而成的

特殊的二叉树

满二叉树

满二叉树：一个二叉树，如果每一层的结点数都达到最大值，则这个二叉树就是满二叉树。也就是说，如果一个二叉树的层数为K，且结点总数是2^k^-1，则它就是满二叉树。

满二叉树中如果第k层满了，则第k层的结点个数是2^k-1^；如果满二叉树的深度为h，则满二叉树一共有2^h^-1个结点。

扩展：满二叉树第一层有一个结点即2^0^，第二层有2个结点2^1^，第三层有4个节点2^2^……所以第k层节点个数为2^k-1^。

当我们知道满二叉树的深度为h时，可以根据k层的结点个数通过错位相减推导出该满二叉树的结点个数。