ErQi

什么是树

发表于 | 分类于

什么是树

树的定义

  1. 树是有n(n>=0)个结点的有限集,n = 0时称之为空树.在任意一颗非空树中,有且只有一个特定的称为根(Root)的结点.
  2. 当n>1时,其余的结点可以分为m(m > 0)个互不相交的有限集,每一个集合本身又是一棵树,并称之为根的子树,注意:子树个数没有限制,但它们一定是互不交互的.

结点分类

结点拥有的子树成为结点的度,度为0的结点称之为叶结点或终端结点,度不为0的结点成为非终端结点或分支结点.除根结点之外,分之结点也成为内部结点.
树的度是树内各结点的度的最大值.

结点间关系

结点的子树称之为该结点的孩子,相应的,该结点成为孩子的父结点.统一父结点的孩子互称为兄弟,结点的祖先是从根结点到该结点所经分支上的所有结点.
以某结点为根的子树中任一结点都成为该结点的子孙.

树的其他概念

结点的层次是从根开始定义起,根为第一层,根的孩子为第二层.树中结点的最大层次称为树的深度或高度.
树中任意结点的子结点之间有顺序关系,这种树称为有序树.
树中任意结点的子结点之间没有顺序关系,这种树称为无序树,也称自由树.
森林是M棵互不交互树的集合.

树的存储结构

树中的某个结点的孩子可以是多个,这就意味着,无论按照何种顺序将树中所有结点储存到数组中,结点的储存位置都无法直接反应逻辑关系.
不过充分利用顺序储存和链式储存结构特点,可以实现对树的储存结构的标识.

双亲表示法

在每个结点中,都用一个指示器指示其父结点在数组中的位置

1
2
3
4
5
6
7
8
9
10
11
// 结点
class PTNode {
    Object data; // 数据
    int parent; // 双亲位置
}
class PTree {
    PTNode[] nodes; // 结点数组
    int r; // 根结点
    int n; // 结点数
}

孩子表示法

每个结点中,用单链表保存孩子的位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class CTNode {
    int child; // 孩子的位置
    CTNode next; // 下一个孩子位置
}
class CTBox {
    Object data; // 数据
    CTNode firstchild; // 孩子结点信息
}
class CTree {
    CTBox[] nodes; // j结点数组
    int r; // 根结点
    int n; // 结点数
}

孩子兄弟表示法

每个结点中,设置两个指针,只想该结点的第一个孩子和此结点的有兄弟

1
2
3
4
5
class CSNode{
    Object data; // 数据
    CSNode firstchild; // 第一个孩子结点
    CSNode rightsib; // 右边兄弟结点
}