数据结构：树与二叉树（一）树的基本知识

这篇文章给大家简单讲一下树。

1.树逻辑结构

（1）树（Tree）是一个非空的有限元素的集合，元素之间有如下关系：有且仅有一个特殊元素，它没有前驱（称为树根Root），其余元素都有且仅有一个前驱元素，所有的元素（报货树根元素）可以有零个或多个后继。

（2）树的递归定义：树T是一个非空数据元素的有限集合，其中有且仅有一个特定元素称为树T的根，剩余的元素（若有的话）可被划分为 m 个互不相交的集合 T1，T2，… ，Tm，而每个集合又都是树，称为T的子树( Subtree ) 。

特点：除根外，每个元素有且仅有一个前驱元素，有零个或多个后继元素。

（3）树数据结构的形式化定义：

说实话，这些知识太久远了，有些地方我也不知道自己理解的对不对。上面这张图中，D是数据集合，R是数据之间的关系，按照我的理解，上面的这个形式化定义，应该是通过定义根与其子树根之间的关系来定义树的。各个子树的根分别为r1,r2,r3…,rm，它们以root（它们自己的上层元素，不是树根的那个root）为前驱元素。D是根的集合，包括树根root（这个root是树根的那个root）；R是根与各子树根之间的关系，其实就是相连关系。

举个例子：

（4）树数据结构的术语：

结点	树中的每一个数据元素都被称为一个结点（比如上面那棵树，a、b、c到m被称为结点）
结点的度（degree）	任一结点子树的树目（其实就是这个结点的后继结点的数目，比如上面这棵树，结点a的度为3，结点b的度为2，结点c的度为1）
叶子（leaf）	度为零的结点，又称为末端结点（如上面那棵树的结点k、l、f、m等）
分支结点	度不为零的结点，又称为非末端结点（如上面那棵树的结点b、e、c等）
分支	结点之间的关系（如上面那棵树的{d，e}、{d，f}等）
内部结点	除根之外的分支结点（如上面那棵树的结点b、e、h、i等）
树的度	树中结点度的最大值（K叉树，如上面那棵树，树的度就是结点d和a的度，为3，所以上面这棵树是三叉树）
孩子（儿子）	结点的子树的根成为该结点的孩子（意思就是这个结点所有的后继结点都是该结点的儿子，如上面这棵树中，结点b的儿子有e、f）
双亲（父亲）	一个结点是它各子树的根结点的双亲（前趋，比如上面那棵树，结点e的双亲就是结点b）
兄弟（sibling）	具有相同双亲的结点（比如上面那棵树，e和f就是兄弟）
祖先	从根结点到该结点路径上所有结点都称为该结点的祖先（比如上面那棵树，结点e的祖先有b和a）
子孙	该结点所有子树上的结点都称为该结点的子孙（比如上面那棵树的结点b，它的子孙结点有e、f、k、l）
结点的层次	根结点定义为第1层，根的儿子定义为第2层，… ，依次类推。记作 L(v)
树的深度（高度）	各个结点层次的最大值（比如上面那棵树，深度为4）
堂兄弟	双亲在同一层上的结点（比如上面那棵树，结点e和结点g就是堂兄弟）
有序树	结点的子树（后继）是有顺序的（兄弟有大小、先后之分）
路径	树中的k个结点n1,n2,…,nk，满足 ni是 ni+1的双亲，称n1到nk有一条路径
路径长度	路径长度=路径上结点个数-1