猫史档案馆

-----------------------------------------------------------------------------------------------------------------

树（一 基本概念）

---------------------------------------------------------------------------------------------------

    1.树的定义：一个n个点，n-1条边组成的图。

    看到这里相信你已经蒙了。其实树就像一棵树一样，只不过上下颠倒了。

    你也可以理解为一个点向外发散再发散的结果。

 

    2.树的节点

    如上图，每一个小圆形代表一个节点。

    红色的节点叫做根节点，因为没有人发散给它。

    绿色的节点叫做叶子节点，因为它不能再发散了。

 

    3.发散关系

    如果一个节点A发散，形成了三个点B,C,D。那么我们称A是B,C,D的父节点，B,C,D是A的子节点。

    假设另外一个节点E发散，形成了F。那么F是A的子节点吗？显然不是。因为他们的父亲不同，总不能让E的喵无缘无故就送给A。看看下图以理解。

   

   4.树的判定：一个n个点，n-1条边组成的图是树。暂且不管图是什么，首先我们来看上面图1。我们数出节点有7个，边有6条。因为6=7-1，所以这是一个树。我们来看图2，我们数出节点有6个，但是边只有4条，所以这不是树。

 

    5.度：一个节点拥有的子树数量称为度。别急，我们来看看图一。红色根节点发散出三个节点，所以根节点的度是3。注意！不要把第三层的也算进去了。

 

    6.深度&高度：这个很容易混淆！虽然树的深度=树的高度，但是每个节点的深高度不一样！看看下面这张图，你应该就能懂了。（depth：深度 height：高度）

   基本概念需要熟练掌握，才能继续走好下一步。

   下一节>>【数据结构&教程贴】树（二：表示方法，输入输出）