树

定义

1. 树型结构是一种非线性数据结构。
2. 在任何一颗非空的树中：
   1. 有且仅有一个根结点root。
   2. 根结点以外的结点（如果有）可分为若干个互不相交的有限集，其中每个集都是一棵树，称为子树。
   3. 一个结点包含了数据元素以及若干指向其他子树的分支。结点拥有的子树的数目称为结点的度。
   4. 结点的度为0的结点称为叶子结点/终端结点， 反之称为分支结点/非终端结点。
   5. 树内各结点的度的最大值就是树的度。
   6. 结点子树的根称为结点的孩子(child)，该结点是孩子结点的双亲/父亲/父母(parent)。
   7. 同一个双亲的孩子结点之间称兄弟(sibling)。
   8. 根节点的层次为1，即第一层，根的孩子为第二层，以此类推。
   9. 树内各结点的层次的最大值就是树的深度或高度。
   10. 某结点的深度是指从根结点到该结点的最长简单路径边的条数。 （根结点深度为0）
   11. 某结点的高度是从该结点点到叶子结点的最长简单路径边的条数。 （叶子结点高度为0）
3. 森林是$m$棵互不相交的树的集合。 对树中每个结点而言，其子树的集合就是森林。
4. 可以用二元组来表示一棵树：Tree=(root, F)。其中root是数据元素，F是森林。

二叉树

参见二叉树