前面两篇博客介绍了线性表的顺序存储与链式存储以及对应的操作，并且还聊了栈与队列的相关内容。本篇博客我们就继续聊数据结构的相关东西，并且所涉及的相关Demo依然使用面向对象语言Swift来表示。本篇博客我们就来介绍树结构的一种：二叉树。在之前的博客中我们简单的聊了一点树的东西，树结构的特点是除头节点以外的节点只有一个前驱，但是可以有一个或者多个后继。而二叉树的特点是除头结点外的其他节点只有一个前驱，节点的后继不能超过2个。

本篇博客，我们只对二叉树进行讨论。在本篇博客中，我们对二叉树进行创建，然后进行各种遍历，最后将二叉树进行线索化。在Demo实现之前，我们先对二叉树的概念及其特性进行介绍，然后在给出具体的代码实现。

 

一、二叉树的特性

上面我们已经提到过，一个除头结点外，每个节点只有一个前驱，有零到两个后继的树即为二叉树。在二叉树中，一个节点可以有左节点或者左子树，也可以有右节点或者右子树。一些特殊的二叉树，比如斜二叉树、满二叉树、完全二叉树等等就不做过多赘述了。说这么多，不如看一张图来的直观。下方就是一个典型的二叉树。

了解二叉树，理解其特性还是比较重要的。基于二叉树本身的逻辑结构，下方是二叉树这种数据结构所具备的特性。

  • 特性1：在二叉树的第i层上至多有2^(i-1)（i >= 1）个节点。
    • 这一特性比较好理解，如果层数是从零开始数的话，那么低i层上的节点数就是2^i，因为二叉树层与层之间的节点数是以2的指数幂进行增长的。如果根节点算是第0层的话，那么第n层的节点数就是2^n次幂。
  • 特性2：深度为k的二叉树至多有2^k-1（k>=1）个节点。
    • 这一特性也是比较好理解的, 由数学上的递加公式就可以很容易的推出来。由特性1易知每层最多有多少个节点，那么深度为k的话，说明一共有k层，那么共有节点数为：2^0 + 2^1 + 2^2 + 2^(k-1) = 2^k - 1。