树

树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。

树型存储结构类似于家族的族谱，各个结点之间也同样可能具有父子、兄弟、表兄弟的关系。

A 和B、F、G 有关系； B 和 C、E 有关系。这就是“一对多”的关系。

整个存储形状在逻辑结构上看，类似于实际生活中倒着的树，所以称这种存储结构为“树型”存储结构。

节点

节点：使用树结构存储的每一个数据元素都被称为“节点”。

根节点：每一个非空树都有且只有一个被称为根的节点。

叶子节点：节点没有任何子节点。

父节点、子节点：A为B、F、G的父节点，B、F、G为A的子节点。

兄弟节点：有相同的父节点

子树和空树

空树：如果集合本身为空，那么构成的树就被称为空树。空树中没有节点。

子树：任何一个节点拆开来看，都是一个根节点，此时也是一棵树。

备注：在树结构中，对于具有同一个根节点的各个子树，相互之间不能有交集。如果有，就破坏了树的结构，不能算做是一棵树。

度和层

有序树和无序树

树中节点的子树从左到右看，谁在左边，谁在右边，是有规定的，这棵树称为有序树；反之称为无序树。

在我们大多数的应用中都是有序树。

森林

树可以理解为是由根节点和多个子树构成，而这多个子树本身是一个森林。

Tree(树) =（root,F）

root 表示树的根节点，F 表示由 m（m >= 0）棵树组成的森林。

树的表示方法

广义表、凹入表示法、嵌套的集合的形式表示。