那些年错过的数据结构与算法(八)

本篇文章将结合《算法》第4版、业界大牛的博客和自己的理解，具体描述树的一些概念，如有错误，请大佬指出。如有侵权，请联系我删除，谢谢。

树

基本概念

树是一种简单的非线性结构，是以分支关系定义的层级结构。和自然界的树结构形式很类似，所以称之为树。例如，物种分类(门、纲、目、科、属、种等)、组织结构(处、科、室等)、行政区(国家、省、市、区)，这些具有层次关系的数据，都可以用树这种数据结构来描述。

在用图形表示数据结构中元素之间的前后关系时，一般使用有向箭头，但在树形结构中，一般去掉箭头也不会引起歧义，常常使用无向线段代表数据元素之间的逻辑关系。

下面结合图来介绍相关术语(图片来源于网络)。

• 父结点：在树结构中，每一个结点只有一个前件，称为父结点，没有前件的结点只有一个，称为树的根结点。图中结点A是树的根结点。

• 子结点和叶子结点：在树结构中，每一个结点可以有多个后件，称为该结点的子结点。没有后件的结点称为叶子结点。图中结点G、I、J、F均为叶子结点。

• 度：在树结构中，一个结点所拥有的后件个数称为该结点的度，所有结点中最大的度称为树的度。图中，根结点A、结点C和结点D的度为2，结点B、H、E的度为1，结点G、I、J、F的度为0，所以该树的度为2。

• 深度：定义一个树的根结点所在的层次为1，其他结点所在的层次等于它的父结点所在的层次加1。树的最大层次称为树的深度。图中，根结点A在第1层，结点B、C在第2层，结点D、E、F在第3层，结点G、H、J在第4层，结点I在第5层，所以该树的深度为5。

• 子树：在树中，以某结点的一个子结点为根构成的树称为该结点的一棵子树。图中，结点A有2棵子树，分别以B、C为根结点。结点B有1棵子树，以D为根结点。结点D有2棵子树，分别以G、H为根结点，其中以G为根结点的子树实际上只有根结点1个结点，树的叶子结点度为0，所以没有子树。

这一篇讲的是树的基本要点，内容不多，本来还有二叉树，但是写在一起又觉得多了点，就分开2篇来写。所以下一篇讲二叉树的一些概念。敬请期待哦<(￣︶￣)>。