Java数据结构-------树介绍

淡淡的烟草味﹌ 2023-10-16 18:42 4阅读 0赞

**树（tree）**

树（tree）是包含n（n>0）个结点的有穷集合，其中：

*  每个元素称为结点（node）；
 *  有一个特定的结点被称为根结点或树根（root）。
 *  除根结点之外的其余数据元素被分为m（m≥0）个互不相交的集合T1，T2，……Tm-1，其中每一个集合Ti（1<=i<=m）本身也是一棵树，被称作原树的子树（subtree）。

树也可以这样定义：树是由根结点和若干颗子树构成的。树是由一个集合以及在该集合上定义的一种关系构成的。集合中的元素称为树的结点，所定义的关系称为父子关系。父子关系在树的结点之间建立了一个层次结构。在这种层次结构中有一个结点具有特殊的地位，这个结点称为该树的根结点，或称为树根。

**我们可以形式地给出树的递归定义如下:**

*  单个结点是一棵树，树根就是该结点本身。
 *  设T1,T2,..,Tk是树，它们的根结点分别为n1,n2,..,nk。用一个新结点n作为n1,n2,..,nk的父亲，则得到一棵新树，结点n就是新树的根。我们称n1,n2,..,nk为一组兄弟结点，它们都是结点n的子结点。我们还称n1,n2,..,nk为结点n的子树。
 *  空集合也是树，称为空树。空树中没有结点。

![Center][]

**树的四种遍历**

**1.先序遍历 （仅二叉树）**  
指先访问根，然后访问孩子的遍历方式  
  
**2.中序遍历（仅二叉树）**  
指先访问左（右）孩子，然后访问根，最后访问右（左）孩子的遍历方式  
  
**3.后序遍历（仅二叉树）**  
指先访问孩子，然后访问根的遍历方式  
  
 **4****.层次遍历**  
一层一层的访问，所以一般用广度优先遍历。

======================================================================================================

**树节点相关术语：**

*  节点的度：一个节点含有的子树的个数称为该节点的度；
 *  叶节点或终端节点：度为0的节点称为叶节点；
 *  非终端节点或分支节点：度不为0的节点；
 *  双亲节点或父节点：若一个结点含有子节点，则这个节点称为其子节点的父节点；
 *  孩子节点或子节点：一个节点含有的子树的根节点称为该节点的子节点；
 *  兄弟节点：具有相同父节点的节点互称为兄弟节点；
 *  节点的层次：从根开始定义起，根为第1层，根的子结点为第2层，以此类推；
 *  堂兄弟节点：双亲在同一层的节点互为堂兄弟；
 *  节点的祖先：从根到该节点所经分支上的所有节点；
 *  子孙：以某节点为根的子树中任一节点都称为该节点的子孙。

**树的几种表示法**

在实际中，可使用多种形式的存储结构来表示树，既可以采用顺序存储结构，也可以采用链式存储结构，但无论采用何种存储方式，都要求存储结构不但能存储各结点本身的数据信息，还要能唯一地反映树中各结点之间的逻辑关系。

**1．双亲表示法**

由于树中的每个结点都有唯一的一个双亲结点，所以可用一组连续的存储空间（一维数组）存储树中的各个结点，数组中的一个元素表示树中的一个结点，每个结点含两个域，数据域存放结点本身信息，双亲域指示本结点的双亲结点在数组中位置。

![Center 1][]

**2．孩子表示法**

1.多重链表：每个结点有多个指针域，分别指向其子树的根  
1）结点同构：结点的指针个数相等，为树的度k,这样n个结点度为k的树必有n(k-1)+1个空链域.  
![Center 2][]  
2）结点不同构：结点指针个数不等，为该结点的度d  
![Center 3][]  
  
2.孩子链表：每个结点的孩子结点用单链表存储，再用含n个元素的结构数组指向每个孩子链表

![Center 4][]

**3．双亲孩子表示法**

1.双亲表示法，PARENT（T，x）可以在常量时间内完成，但是求结点的孩子时需要遍历整个结构。  
2.孩子链表表示法，适于那些涉及孩子的操作，却不适于PARENT（T，x）操作。  
3.将双亲表示法和孩子链表表示法合在一起，可以发挥以上两种存储结构的优势，称为带双亲的孩子链表表示法  
![Center 5][]

**4．双亲孩子兄弟表示法 （二叉树专用）**

又称为二叉树表示法，以二叉链表作为树的存储结构。

![Center 6][]

![Center 7][]

[Center]: https://img-blog.csdn.net/20130923165350734?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 1]: https://img-blog.csdn.net/20130923133857328?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 2]: https://img-blog.csdn.net/20130923134124000?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 3]: https://img-blog.csdn.net/20130923134139343?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 4]: https://img-blog.csdn.net/20130923134204125?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 5]: https://img-blog.csdn.net/20130923134244609?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 6]: https://img-blog.csdn.net/20130923134453203?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center
[Center 7]: https://img-blog.csdn.net/20130923134547781?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveGlhb3Rpbmc0NTEyOTI1MTA=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center