欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java 数据结构与算法---树

程序员文章站 2022-04-24 16:07:36
树状图是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树,也就是说它是根朝上,而叶朝下的 ......

 

一、树的概念 

java 数据结构与算法---树

除根节点外,其余节点有且只有一个父节点。

1、度

java 数据结构与算法---树

 

 

节点的度:每个节点的子节点个数。

树的度:树内各个节点的度的最大值。

树的高度(深度):树中节点的最大层次称为树的深度。

节点路径:一个节点到另外一个节点的连线(树种该路径有且只有一条)。例如:B到J节点如果有两条路径,那么该结构就不是树。

子树:除根节点外的节点就是子树。

叶子结点:一棵树当中没有子结点的结点称为叶子结点(即度为0的节点),简称“叶子”。

 堂兄弟节点:双亲在同一层的节点互为堂兄弟;

二树的分类

顺序分:

有序树:树中节点的各子树从左至右是有序的、且不能互换。

无序树:树中节点的各子树从左至右是无序的、且能互换。

 

二、树的存储结构

简单的顺序存储是无法满足树的要求,一般我们结合顺序存储与链式存储来实现。

常用三种方式

1、双亲表示发

java 数据结构与算法---树

注释:下标一列我们可以当作是顺序存储通过parent 记录父类的位置;该方式我们我们找某个元素的父元素很简单,但是找子元素就相对复杂。

 

 

2、双亲孩子表示法

java 数据结构与算法---树

注释:该方式将双亲表示发与孩子表示法相结合 数组+链表 (HashMap的数据结构),该方式找孩子节点简单。

 

3、孩子兄弟表示发

java 数据结构与算法---树

注释:该方式找元素的子元素容易,但找父元素相对复杂。