[学习类] 树结构的基本知识

--> 　树是一种重要的非线性数据结构，直观地看，它是数据元素（在树中称为结点）按分支关系组织起来的结构，很象自然界中的树那样。树结构在客观世界中广泛存在，如人类社会的族谱和各种社会组织机构都可用树形象表示。树在计算机领域中也得到广泛应用，如在编译源程序如下时，可用树表示源源程序如下的语法结构。又如在数据库系统中，树型结构也是信息的重要组织形式之一。一切具有层次关系的问题都可用树来描述。
   其基本定义是：一棵树（tree）是由n（n>0）个元素组成的有限集合，其中：
　　（1）每个元素称为结点（node）；
　　（2）有一个特定的结点，称为根结点或根（root）；
　　（3）除根结点外，其余结点被分成m（m>=0）个互不相交的有限集合，而每个子集又都是一棵树（称为原树的子树）
  其中的几个基本概念：
    度　
    树的度——也即是宽度，简单地说，就是结点的分支数。以组成该树各结点中最大的度作为该树的度，如上图的树，其度为3;树中度为零的结点称为叶结点或终端结点。树中度不为零的结点称为分枝结点或非终端结点。除根结点外的分枝结点统称为内部结点
    深度
    树的深度——组成该树各结点的最大层次
    层次
    根结点的层次为1，其他结点的层次等于它的父结点的层次数加1.
    路径
    对于一棵子树中的任意两个不同的结点，如果从一个结点出发，按层次自上而下沿着一个个树枝能到达另一结点，称它们之间存在着一条路径。可用路径所经过的结点序列表示路径，路径的长度等于路径上的结点个数减1.
    森林
    指若干棵互不相交的树的集合