链表通常可以提供比数组更大的灵活性，但是由于链表是线性结构，所以很难使用它们来组织对象的分层结构。虽然栈和队列反映了某些层次，但它们是一维的。为了避免这种限制，我们来探究一种新的数据结构，称为树，树由节点和弧组成。

就像这样：

图1-1

与自然界的树不同，数据结构中的树是倒过来的：根在顶部，叶子(末端节点)在底部。根是一个没有父节点只有子节点的节点，而叶节点没有子节点或者子节点是空结构。一颗树中非叶子节点我们称之为非终端节点，包括根节点。

每个节点都可以从根节点经一个唯一的弧序列到达，此弧序列被称之为路径，路径中弧的数量称之为路径的长度。节点的层次是从根节点到该节点的路径的长度加1，也就是该路径上节点的数量。树的高度(深度)是树中节点的最大层次。空结构是空树，所以空树高度为0。只有一个根节点的树的高度是1，而且该树比较特殊，它是“节点既是根也是叶子”的唯一情况。在一棵树中，如果某个节点拥有n个子节点，那么我们称该节点的度为n。树在极端情况下可以退化为链表，这种树的高度为唯一叶节点的层次。

就像这样：

图1-2

什么是二叉树呢？上面说的都是树的概念，节点下面可以有多个子节点，而二叉树对此做了限制。二叉树是节点可以包含最多两个子节点的树，每一个子节点都区分左子节点或右子节点。例如图1-1中13和23节点分别是根节点的左右子节点。我们进一步对二叉树进行划分：

完美二叉树

在一棵二叉树中，如果每个非终端节点都有两个子节点，并且所有叶子节点位于同一层次，那么称之为完美二叉树。

就像这样：

图1-3

其中非终端节点包括15/13/23，它们都有两个子节点，并且所有叶子节点都位于第3层。可以看到，完美二叉树左右子树是完美对称的。对于完美二叉树，有以下特性：

1、第i+1层的节点数为2^i

2、如果完美二叉树高度为n，那么总的节点数为2^n - 1

3、如果完美二叉树中叶子节点为m，非终端节点为k，那么m=k+1

4、如果完美二叉树中某节点下标为n，那么它的左节点下标为2n+1，右节点下标为2n+2

证明：

1、性质1可以用数学归纳法来证明，假设完美二叉树中第i层节点数为2^(i-1)，我们只要推导出第i+1层节点数为2^i即可。从定义出发，已知第i层的节点都有两个左右子节点，那么第i+1层的节点数为(2^(i-1))*2，也就是2^i，证明完毕

2、性质2由性质1衍生出来，对于高度为n的完美二叉树，节点总数为2^0+2^1+......+2^(n-1)，也就是2^n - 1，证明完毕

3、性质3也是由数学归纳法证明的，假设高度为n的完美二叉树中非终端节点数为k，叶子节点为m，并且m=k+1，只要推导出高度为n+1的完美二叉树也符合这种情况即可。假设该树非终端节点数为k1，叶子节点数为m1，可以计算出k1=k+m，m1=2*m，那么m1-k1=2*m-(k+m)=m-k=1，即m1=k1+1，证明完毕

4、性质4的证明比较麻烦，假设完美二叉树第n层存在一个节点下标为i，那么第n层剩余节点个数(包括i节点)为(2^n-1)-i,即2^n-i-1，我们记为k，假设i节点左节点下标为j，那么在第n+1层中j节点之前(不包括j节点)节点数为2^(n+1-1)-2*k=2^n-2*k，我们记为m，那么j-i=m+k=2^n-2*k+k=2^n-k=2^n-(2^n-i-1)=i+1，即j-i=i+1，那么j=2i+1，证明完毕

完全二叉树

对于高度为K的，有n个结点的二叉树，当且仅当其每一个结点都与高度为K的完美二叉树中编号从0至n-1的结点一一对应时称之为完全二叉树.

完满二叉树

在一棵二叉树中，只存在度为0或者2的节点，称该树为完满二叉树

我们知道，在二叉树中只存在度为0或1或2的节点，记为n0,n1,n2，那么二叉树中节点总数n可以记为n=n0+n1+n2。在所有二叉树中存在一个重要的性质：n0=n2+1。该性质可以用数学归纳法证明，假设在一棵二叉树p中，度为2的节点个数为n2，那么n0=n2+1，我们只要证明在度为2的节点个数为n2+1的二叉树q中，该性质不变即可。想象在二叉树p中，我们为某个叶子节点添加左右节点，那么该二叉树变为q，并且度为2的节点个数增加了1，而叶子节点也增加了1，n0依然比n2大1。想象在二叉树p中，为某个度为1的节点添加一个子节点，那么该二叉树变为q，并且度为2的节点个数增加了1，而叶子节点也增加了1，n0依然比n2大1。证明完毕

到目前为止，我们已经了解完美二叉树、完全二叉树、完满二叉树，对于完美二叉树有4个性质，而完全二叉树、完满二叉树有1个。也许有同学会觉得二叉树还有其他性质，事实上，其他性质完全可以用以上性质直接或间接推导出来，性质记得越少越不容易忘记。

二叉树不是停留在学术上的数据结构，我们是要在程序中实现二叉树，并且运用它的性质来满足软件开发需求。第一步，我们首先要遍历二叉树，能够遍历才能对节点进行操作。遍历二叉树的方法在下一篇进行探讨。

数据结构与算法-栈与队列