认识达内从这里开始

学习如何使用数据结构是每一位Java编程开发程序员都需要熟练掌握的一个编程开发知识点，而本文我们就通过案例分析来简单了解一下，Java编程树数据结构基础知识分享。

树是一种数据结构，它是由n(n>=1)个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：每个结点有零个或多个子结点;没有父结点的结点称为根结点;每一个非根结点有且只有一个父结点;除了根结点外，每个子结点可以分为多个不相交的子树;

1、结点的层次和树的深度

树的结点包含一个数据元素及若干指向其子树的若干分支。结点的层次(level)从根开始定义，层次数为0的结点是根结点，其子树的根的层次数为1。若结点在L层，其子树的根就在L+1层。对于层次为k(k>0)的每个结点c，都有且仅有一个层次为k-1的结点p与之对应，p称为c的父亲(parent)或父结点。若p是c的父亲，则c称为p的孩子(child)。父子之间的连线是树的一条边。在树中根结点没有父亲，其余结点只有一个父结点，但是却可能有多个孩子，同一结点的孩子相互称为兄弟(sibling)。树中结点的大层次数称为树的深度(Depth)或高度。树中结点也有高度，其高度是以该结点为根的树的高度。

2、结点的度与树的度

结点拥有的子树的数目称为结点的度(Degree)。度为0的结点称为叶子(leaf)或终端结点。度不为0的结点称为非终端结点或分支结点。除根之外的分支结点也称为内部结点。在这里需要注意的是结点的直接前驱结点，即它的父结点不计入其度数。

3、在树结构中有一个重要的性质如下：

树中的结点数等于树的边数加1，也等于所有结点的度数之和加1。这是因为除根结点以外每个结点都与指向它的一条边对应，所以除根结点以外的结点数等于树中边数之和。因此树中的结点数等于树的边数加1。而边数之和就是所有结点的度数之和，因此树中的结点数也等于所有结点的度数之和加1。

这个性质说明在树中结点总数与边的总数是相当的，基于这一事实，在对涉及树结构的算法复杂性进行分析时，可以用结点的数目作为规模的度量。

4、路径

在树中k+1个结点通过k条边连接构成的序列{(v0,v1),(v1,v2),…,(vk-1,vk)|k≥0}，称为长度为k的路径(path)。注意，此时忽略了树中边的方向。由单个结点，0条边构成的是长度为0的路径。结论：树中任意两个结点之间都存在的路径。这意味着树既是连通的，同时又不会出现环路。从根结点开始，存在到其他任意结点的一条路径，根到某个结点路径的长度，恰好是该结点的层次数。

5、祖先、子孙、堂兄弟

将父子关系进行扩展，就可以得到祖先、子孙、堂兄弟等关系。结点的祖先是从根到该结点路径上的所有结点。以某结点为根的树中的任一结点都称为该结点的子孙。父亲在同一层次的结点互为堂兄弟。

6、有序树、m叉树、森林

如果将树中结点的各子树看成是从左至右是有次序的，则称该树为有序树;若不考虑子树的顺序则称为无序树。对于有序树，我们可以明确的定义每个结点的一个孩子、二个孩子等，直到后一个孩子。若不特别指明，一般讨论的树都是有序树。

树中所有结点大度数为m的有序树称为m叉树。

森林(forest)是m(m≥0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。树和森林的概念相近。删去一棵树的根，就得到一个森林;反之，加上一个结点作树根，森林就变为一棵树。

【免责声明】：本内容转载于网络，转载目的在于传递信息。文章内容为作者个人意见，本平台对文中陈述、观点保持中立，不对所包含内容的准确性、可靠性与完整性提供形式地保证。请读者仅作参考。更多内容请加danei0707学习了解。欢迎关注“达内在线”参与分销，赚更多好礼。