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

 

一、树的概念 

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

1、度

 

 

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

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

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

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

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

叶子结点：一棵树当中没有子结点的结点称为叶子结点（即度为0的节点），简称“叶子”。

 堂兄弟节点：双亲在同一层的节点互为堂兄弟；

二树的分类

顺序分：

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

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

 

二、树的存储结构

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

常用三种方式

1、双亲表示发

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

 

 

2、双亲孩子表示法

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

 

3、孩子兄弟表示发

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