数据结构之数的定义、表示和术语

秒速五厘米 2022-02-12 10:26 479阅读 0赞

### 数 ###

*  定义
 *  性质
 *  术语
 *   *   *   *  结点的度
             *  数的度
             *  叶结点
             *  父节点
             *  子节点
             *  兄弟结点
             *  祖先结点
             *  结点的层次
             *  数的深度和数的高度
             *  分支
             *  路径和路径长度

# 定义 #

**官方说法**数是n（n>=0）个结点构成的有限集合。当n=0时成为空树。  
其实数就是类似与树枝的一种数据结构组织类型。

# 性质 #

1.数中有一个称为“树根”（Boot）的特殊结点，用r表示，这就类似于每个数只有一个树根。  
2.其余结点可以划分为m个不相交的子集T1，T2，···，Tn。任何子集Ti（i ∈ \[ 1,m \]）也是一个数，称为根结点r的“子树”（SubTree）。每个子树的根节点都与r有一条相接连的边，r是这些子树根节点的”父节点“（Parent）。  
3.一棵N个结点的树有N-1条边。

# 术语 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]

#### 结点的度 ####

一个结点的度是其子树的个数，如结点D的度为**3**，结点E的度为**0**（即该个结点的所有分支数量成为该结点的度。

#### 数的度 ####

数的所有结点中最大的度数，如上图中结点A有最大的度数为**4**，所以这棵树的度为**4**。

#### 叶结点 ####

度为**0**的结点，也称为端节点，如F,L,H,M,J,K,E都是叶结点（没有儿子的结点成为叶结点）

#### 父节点 ####

具有子树的结点时其子树的根节点的父节点，如B时F，G的父节点（父子关系）

#### 子节点 ####

与父节点相反。

#### 兄弟结点 ####

具有同一父亲结点的各结点彼此是兄弟结点，如BCDE有共同的父节点A，他们彼此是兄弟结点（即同一层同同父亲的结点成为兄弟结点）

#### 祖先结点 ####

沿数根到某一结点路径上所有结点都是这个结点的祖先结点，如ABG是L的祖先（即同一条线上比自己大的都叫祖先结点）h和\#\# 子孙节点  
与祖先结点相反

#### 结点的层次 ####

规定根节点在**1**层，其他任一结点的层数都是其父节点的层数加**1**（如图所示）

#### 数的深度和数的高度 ####

数中说有结点中最大的层次是这棵树的深度，如上图该数有四层，所以深度为**4**。数的高度和数的深度是一样的，只不过数的高度是从下往上数的叶结点的高度规定为**1**，其他任一结点的高度层数是其所有子结点的最大高度层数加**1**。数的高度就是其根节点的高度。

#### 分支 ####

数中两个相邻结点的连边成为一个分支（即那条**线**）

#### 路径和路径长度 ####

如A到M的路径为A，D，I，M，即这条直线上的所有结点

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0MjU2MjI3_size_16_color_FFFFFF_t_70]: /images/20220212/87d6267abc82410cb2d749cc272d622e.png