轻松搞定树之树的定义和二叉树

什么是树？树长什么样？树的数据结构怎么定义？树的数据怎么遍历？树的数据怎么进行增删改查操作…等等，对于初学者来说，这都是经常会困恼我们的问题，通过树系列我们将一一来解答这些问题

今天我们先来了解树的基本定义和二叉树的定义

进入正文之前，我们先简单了解一下线性数据结构和非线性数据结构，

线性数据结构:数据元素之间存在一对一的线性关系，我们熟知的数组、链表、栈和队列都是线性的数据结构。

什么是非线性数据结构呢？

我们今天所讨论的树就是典型的非线性数据结构——数据元素之间存在一对多的关系。如下图所示为树的基本结构。

由以上的树的结构图，我们可以概括，树的定义为：树是n(n>=0)个节点的有限集。
（至于树的节点保存什么内容，节点和节点之间是如何关联的，我们以后再讨论。)

任意一棵非空的树中，它有以下几个特点：

(1)有且仅有一个根(Root)节点——A节点就是根节点

(2)当n>1时，除了根节点的其他节点可以分成m(m>0)个互不相交的有限集，并且每个有限集本身也是一棵树，我们把这m个有限集叫做根节点的子树。

在我们上面的树中，根节点A有B、C和D三棵子树，节点B有E和F两棵子树，节点C有G一棵子树，节点D有H、I和J三棵子树，其他节点依此类推。

我们知道了树的基本定义和它的结构，我们再来了解一下有关树的基本术语，也是我们在学习过程中必须要牢记的。

(1)节点的度：节点拥有的子树数。如节点A的度为3——它有B、C和D三棵子树；节点F的度为0——它没有子树

(2)叶子节点：度为0的节点，也就是没有子树的节点，图中F、G、H、I、K、L和M都是叶子节点

(3)树的度：树中所有节点的度的最大值，图中节点A和节点D的度最大，都为3，所以数的度为3

(4)孩子和双亲:如在上图中节点A称为节点B、C和D的双亲(Parent),节点B、C和D称为节点A的孩子(child)而节点B、C和D互为兄弟;同理节点B又是节点E和F的双亲，其他的关系依次类推。

(5)节点的层次：从根开始定义，根为第一层，根的孩子为第二层，类似于我们的血缘关系，每一代代表一层。每个节点在哪一代就是在哪一层。

(6)树的深度或高度：树中节点的最大层次，图中的树的最大层次为4，所以高度为4。也就是A的后代最远繁衍到第四代就灭绝了。

-------------------二叉树分割线-----------------------------

以上就是树的基本知识，下面我们再说说二叉树，为什么要说二叉树呢？而不是三叉树、四叉树呢？
说完二叉树的定义和性质，这个问题就迎刃而解了。

什么是二叉树？二叉树首先是树，只是对树中节点的子树进行了限制——也即树中每个节点的至多有两个子树，并且节点的子树有左右之分，其顺序不能任意颠倒。

二叉树可以类比于人类的繁衍，就像现在开放了二胎政策，每对夫妻至多可以生育两个孩子，如果有两个孩子，是有哥哥和弟弟的区分的，所以他们的顺序是不能颠倒的。二叉树结构如图所示

结合二叉树结构图，我们来说说二叉树的性质：

(1)二叉树在第i层至多有2^(i-1)个节点

(2)深度为k的二叉树至多有(2^{k)-1个节点=1+2+4+…+2}(k-1)=(2^k)-1

从上图看到我们的二叉树的节点的子树虽然都满足至多只有两个子树，但是没有任何规律可言，所以这里不得不提到两种特殊的二叉树

(1)满二叉树：顾名思义，就是除了叶子节点的所有节点都有两棵子树也即高度为k的二叉树有(2^k)-1个节点，直接上图更加直观

(2)完全二叉树:直接上图更直观的了解，与满二叉树不同的是高度为k的完全二叉树的节点数少于(2^k)-1,但是满足树从上到下，从左到右，每个节点优先满足有两个子树的条件。

回到我们原来的问题，为什么要讲二叉树而不是三叉树、四叉树，这是因为二叉树在实际的运用当中更加广泛和高效。