【数据结构与算法之树结构】树的基本概念

傷城~ 2024-03-25 12:36 112阅读 0赞

#### 【数据结构与算法之树结构】树的基本概念 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之树结构】树的基本概念
         *   *   *  1 树的定义
                 *  2 常见术语
                 *  3 树的性质

###### 1 树的定义 ######

树Tree 是由n(n ≥ 0) 个节点组成的有限集合。

在任意一棵非空树中：

*  有且仅有一个根root 节点
 *  当n > 1时，其余节点分为m 个互不相交的有限集，其中每个集合都是一棵树，称为子树。

![在这里插入图片描述][9880e6154f644f6abc6dfdd274260470.png_pic_center]

###### 2 常见术语 ######

【节点的度 Degree】节点拥有的子树数量。

【树的度】树中各节点度的最大值。

【叶子节点 Leaf】度为0的节点称为树的叶子节点。

【孩子节点 Child】一个节点的子树的根节点称为该节点的孩子节点。

【双亲节点 Parent】双亲节点与叶子节点对应，如果节点B是节点A的孩子节点，那么节点A 称为节点B的双亲节点。

【兄弟节点 Sibling】一个双亲节点的孩子节点互为兄弟节点。

【节点的层次 Level】从根节点开始，根节点为第1层，根节点的孩子节点为第2层，以此类推。如果某节点在 第 l 层，其孩子节点就在 l + 1层。

【树的深度 Depth】树中节点的最大深度称为树的深度。

【森林 Forest】m( m ≥ 0) 棵互不相交的树的集合称为森林。

###### 3 树的性质 ######

1.  非空树的节点总数 = 树中所有节点的度之和 + 1
2.  度为k 的非空树的第i 层最多有  k i − 1 k^\{i - 1\} ki−1 个节点( i ≥ 1)。
3.  深度为h 的k叉树，最多有  k h − 1 / ( k − 1 ) k^\{h\} - 1 / (k-1) kh−1/(k−1) 个节点
4.  具有n 个节点的k叉树的最小深度为  ⌈ l o g k ( n ( k − 1 ) + 1 ) ⌉ ⌈ log\_k^\{(n(k-1) + 1)\} ⌉ ⌈logk(n(k−1)\+1)⌉

[9880e6154f644f6abc6dfdd274260470.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/92e7d89c5104412ca8fc45165fce697d.png

发表评论取消回复

表情：

评论列表（有 0 条评论，112人围观）

还没有评论，来说两句吧...

相关阅读

相关【数据结构与算法之树结构】案例

【数据结构与算法之树结构】案例文章目录【数据结构与算法之树结构】案例 1 计算二叉树的深度

女爷i/ 2024年03月25日 14:12/ 0 赞/ 127 阅读

相关【数据结构与算法之树结构】二叉排序树与AVL树

【数据结构与算法之树结构】二叉排序树与AVL树文章目录【数据结构与算法之树结构】二叉排序树与AVL树二叉排序树也称为二叉查找树。它或者

冷不防/ 2024年03月25日 14:12/ 0 赞/ 109 阅读

相关【数据结构与算法之树结构】创建二叉树

【数据结构与算法之树结构】创建二叉树文章目录【数据结构与算法之树结构】创建二叉树利用二叉树遍历的思想，在遍历过程中生成二叉树的节点，进而建

柔情只为你懂/ 2024年03月25日 14:12/ 0 赞/ 88 阅读

相关【数据结构与算法之树结构】二叉树的遍历

【数据结构与算法之树结构】二叉树的遍历文章目录【数据结构与算法之树结构】二叉树的遍历 1 基于深度优先搜索的

不念不忘少年蓝@/ 2024年03月25日 14:12/ 0 赞/ 109 阅读

相关【数据结构与算法之树结构】二叉树

【数据结构与算法之树结构】二叉树文章目录【数据结构与算法之树结构】二叉树 1 二叉树的定义

小鱼儿/ 2024年03月25日 12:36/ 0 赞/ 103 阅读

相关【数据结构与算法之树结构】树的基本概念

【数据结构与算法之树结构】树的基本概念文章目录【数据结构与算法之树结构】树的基本概念 1 树的定义

傷城~/ 2024年03月25日 12:36/ 0 赞/ 113 阅读

相关数据结构之树的基本概念

树是以分支关系定义的层次结构。（1）树（tree）是n（n大于等于0）个节点的有限集。在任何一棵非空树中：（1）有且只有一个特定的称为跟（root）的节点；（2）当n>1

谁借莪１个温暖的怀抱￠/ 2022年08月02日 09:47/ 0 赞/ 200 阅读

相关数据结构与算法基本概念

数据 > 数据（Data）是能够被计算机程序识别、存储、加工和处理的描述客观事物的数字等符号集合的总称。数据项 > 数据项（Data Item）是具有独立含义的

r囧r小猫/ 2022年05月28日 07:39/ 0 赞/ 253 阅读

相关数据结构与算法-基本概念

概要数据结构基本概念逻辑结构与物理结构抽象数据类型

迈不过友情╰/ 2022年03月25日 14:30/ 0 赞/ 325 阅读

相关数据结构之树的基本概念

本部分主要介绍树的相关知识，将分为3篇博文介绍。本文将着重介绍二叉树的一些基本概念，以及在其基础上的一些特殊的树形式：满二叉树、完全二叉树、线索二叉树、二叉排序树、平衡二叉树

╰+攻爆jí腚メ/ 2022年02月23日 04:56/ 0 赞/ 255 阅读