数据结构与算法学习笔记（第五章树与二叉树）（1）树

绝地灬酷狼 2023-02-12 03:28 12阅读 0赞

### 目录 ###

*  树
 *   *  定义：
     *  应用于计算机领域
     *  表示方式
     *  一堆术语
     *   *  孩子
         *  双亲
         *  祖先
         *  子孙
         *  兄弟
         *  堂兄弟
         *  根结点
         *  结点的度
         *  树的度
         *  结点的层
         *  树的深度
         *  分支结点
         *  叶子节点
         *  有序树、无序树
         *  森林
     *  树的结构
     *  注意！

# 树 #

## 定义： ##

*  n个结点的有限集
 *  n=0，树是空树
 *  n>0
    
     *  有且仅有一个处于顶端的结点我们把它称作根结点
     *  其余结点分为m个互不相交的有限集T1,T2,T3…,TM
     *  每个集合本身又是一棵树，称为根结点的子树
 *  树的定义是递归的定义

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

## 应用于计算机领域 ##

*  编译
 *  数据库系统
 *  算法分析

## 表示方式 ##

*  倒树表示（最常见）
 *  嵌套集合
 *  凹入表示
    
     *  凹入越深的结点，其层次越低
 *  广义表

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200524120638733.png]

## 一堆术语 ##

### 孩子 ###

*  一个结点的子树的根结点称为该结点的孩子

### 双亲 ###

*  对应的，这个结点称为孩子的双亲

### 祖先 ###

*  从根到某个结点经过的分支上所有的结点

### 子孙 ###

*  以某结点为根的子树中任意结点

### 兄弟 ###

*  双亲都同一个的两个结点称为兄弟

### 堂兄弟 ###

*  双亲都在同一层的两个结点称为堂兄弟

### 根结点 ###

*  非空树中无前驱结点的结点

### 结点的度 ###

*  结点拥有的子树数

### 树的度 ###

*  树内各结点的的度的最大值

### 结点的层 ###

*  根结点第一层，往下的分支结点叫第二层，再往下第三层，以此类推，叶子结点的层数最大

### 树的深度 ###

*  树中结点的最大层次

### 分支结点 ###

*  结点的度不为0的结点，也叫非终端结点
 *  根结点以外的分支结点称为内部结点

### 叶子节点 ###

*  结点的度为0的结点，也叫终端结点

### 有序树、无序树 ###

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

### 森林 ###

*  m（m>=0)棵互不相交的树的集合
 *  找一棵树，把根结点删除，剩下的那堆子树就成了森林
 *  一棵树也是森林，因为m>=0，你可以认为是特殊的森林
 *  给森林的各子树加上一个双亲结点，森林就变成树
 *  so **森林不一定是树，但树一定是森林**

## 树的结构 ##

*  一对多

## 注意！ ##

*  **树的术语也可以用于二叉树上**
 *  **但是二叉树不属于树，二叉树和树属于两个东西，不要混为一谈**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200524120355185.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200524120426699.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70
[20200524120638733.png]: https://img-blog.csdnimg.cn/20200524120638733.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200524120544500.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTkxMDQwOA==,size_16,color_FFFFFF,t_70