树形结构是一层次的嵌套结构。 一个树形结构的外层和内层有相似的结构， 所以这种结构多可以递归的表示。经典数据结构中的各种树状图是一种典型的树形结构：一颗树可以简单的表示为根， 左子树， 右子树。 左子树和右子树又有自己的子树。

树的介绍

1.树的定义

树是一种数据结构，它是由n（n>=1）个有限节点组成一个具有层次关系的集合。
tree_1.png
把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：

  • 每个节点有零个或多个子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树。

2. 基本术语

  • 根——即根结点（没有前驱）
  • 叶子——即终端结点（没有后继）
  • 森林——指m棵不相交的树的集合（例如删除A后的子树个数）
  • 有序树——结点各子树从左至右有序，不能互换（左为第一）
  • 无序树——结点各子树可互换位置。
  • 双亲——即上层的那个结点(直接前驱)
  • 孩子——即下层结点的子树的根(直接后继)
  • 兄弟——同一双亲下的同层结点（孩子之间互称兄弟）
  • 堂兄弟——即双亲位于同一层的结点(例如G和H互为堂兄弟）
  • 祖先——即从根到该结点所经分支的所有结点(例如结点E的祖先是A和B)
  • 子孙——即该结点下层子树中的任一结点
  • 结点——即树的数据元素
  • 结点的度——结点挂接的子树数
  • 节点的层——从根到该结点的层数（根结点算第一层）
  • 终端结点——即度为0的结点，即叶子
  • 分支结点——即度不为0的结点（也称为内部结点）
  • 树的度——所有结点度中的最大值
  • 树的深度——指所有结点中最大的层数

3.其它表示方式

tree_2.png