01、什么是树

小二：掌柜的，最近大家都在忙着种树，说是要保护环境。

老板娘：树 ? 咱们店有呀，前几年种的那棵葡萄树，不是都结果子了吗？就数你吃的最多。

小儿：这.......。

大家应该猜到，咱们今天要唠啥了。

之前给大家介绍了链表,栈，哈希表 等数据结构

今天咱们来看一种新的数据结构，树。

PS：本篇文章内容较基础，对于没有学过数据结构的同学会有一些帮助，如果你已经学过的话，也可以复习一下，查缺补漏，后面会继续更新这个系列。

文章大纲

树

我们先来看下百度百科对树的定义

树是 n （n >= 0） 个节点的有限集。 n = 0 时 我们称之为空树, 空树是树的特例。

在任意一棵非空树中：

• 有且仅有一个特定的节点称为根（Root）的节点
• 当 n > 1 时，其余节点可分为 m （m > 0）个互不相交的有限集 T1、T2、........Tm，其中每一个集合本身又是一棵树，并且称为根的子树。

我们一起来拆解一下上面的两句话，到底什么是子树呢？见下图

例如在上面的图中

有且仅有一个特定的节点称为根节点，也就是上图中的橙色节点。

当节点数目大于 1 时，除根节点以外的节点，可分为 m 个互不相交的有限集 T1,T2........Tm。

例如上图中，我们将根节点以外的节点，分为了 T1 （2，3，4，5，6，7），T2（8，9）两个有限集。

那么 T1 （绿色节点）和 T2（蓝色节点）就是根节点（橙色节点）的子树。

我们拆解之后发现，我们上图中的例子符合树的要求，另外不知道大家有没有注意到这个地方。

除根节点以外的节点，可分为 m 个互不相交的有限集。

那么这个互不相交又是什么含义呢？见下图。

我们将 (A) , (B) , (C) , (D) 代入上方定义中发现，(A) , (B) 符合树的定义，（C）, (D) 不符合，这是因为 (C) , (D) 它们都有相交的子树。

好啦，到这里我们知道如何辨别树啦，下面我们通过下面两张图再来深入了解一下树。

主要从节点类型，节点间的关系下手。

这里节点的高度和深度可能容易记混，我们代入到现实即可。

我们求深度时，从上往下测量，求高度时，从下往上测量，节点的高度和深度也是如此。