数据结构之树

在计算器科学中，树（英语：tree）是一种抽象数据类型或是实现这种抽象数据类型的数据结构，用来模拟具有树状结构性质的数据集合。它是由n（n>0）个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。

树

• 树的定义
  • 树是n个有限数据元素的集合
  • 当n=0时称为空树；当n>0时，是非空树，它满足两个条件
    • 1.有且只有一个称为根的结点
    • 2.其余结点为互不相交的非空集合，每个集合又是一棵树，称为根的子树
• 树的表示方法
  • 树形表示法。使用一棵倒置的树表示树结构。
  • 嵌套集合表示法。也称为文氏图法，它是使用集合以及集合的包含关系描述树结构
  • 凹入表表示法。使用线段的伸缩关系描述树结构
  • 广义表表示法。将树的根结点写在括号的左边，除根结点外的其余结点写在括号内并用逗号间隔来描述树的结构
• 树的基本术语
  • 结点。即数据元素
  • 结点的度。该结点所拥有的分支数目或后继结点的个数
  • 树的度。树中各结点度的最大值
  • 叶子。即终端结点，度为0的结点称为叶子结点
  • 分支结点。即非终端结点，度不为0的结点称为分支结点
  • 孩子结点。一个结点的后继称为该结点的孩子结点
  • 双亲结点。一个结点的前驱称为该结点的双亲结点
  • 兄弟结点。同一双亲下的孩子结点互称为兄弟结点
  • 堂兄弟。双亲互为兄弟的两个结点互称为堂兄弟
  • 子孙结点。一个结点的所有子树结点称为该结点的子孙结点
  • 祖先结点。从树的根结点到达这个结点路径上的所有结点称为该结点的祖先结点
  • 结点的层次。树的根结点的层次为1，其余结点的层次等于它双亲结点的层次加1
  • 树的深度。树中结点的最大层次称为树的深度（或高度）
  • 有序树或无序树。如果一棵树中的结点的各子树从左到右是有次序的，即若交换了某结点各子树的相对位置，则构成了不同的树，称这样的子树为有序树。反之
  • 森林。m（m>=0）棵互不相交的树的集合