18-数据结构_树-定义和分类

Dear 丶 2021-11-26 07:24 269阅读 0赞

树

# 一, 定义 #

## 1, 专业定义 ##

(1) 有且仅有一个称为根的结点  
(2) 有若干个互不相交的子树  
(3) 子树也是一棵树

## 2, 通俗定义 ##

(1) 树由结点和连线组成  
(2) 每个结点只有一个父结点, 可以有多个子结点  
(3) 但有一个结点例外, 该结点没有父节点, 此结点称为根结点

## 3, 专业术语 ##

![SouthEast][]

(1) 结点(节点)  
(2) 父结点  
(3) 子结点  
(4) 子孙  
(5) 堂兄弟  
(6) 深度  
从根结点到最底层结点的层数, 称之为~.  
根结点为第一层.  
(7) 叶子结点  
没有子结点的结点, 称之为~.  
(8) 非终端结点  
实际上就是 非叶子结点.  
(9) 度  
子结点的个数, 称之为~.  
(10) 树的度  
在所有结点的度中取最大值.

# 二, 分类 #

## 1, 一般树 ##

任意一个结点的子结点的个数不受限制

## 2, 二叉树 ##

(1)定义  
任意一个结点的子结点的个数最多为两个  
子结点的位置不可更改 (二叉树是有序的)  
(2)分类  
①一般二叉树  
②满二叉树  
在不添加树的层级的前提下, 无法在树上增加结点  
即, 每层的结点数都达到了最大  
③完全二叉树  
删除满二叉树最底层最右边 连续的若干个结点,  
此时形成的树称之为~.

用数组存储的树, 必须是完全二叉树

![SouthEast 1][]

![SouthEast 2][]

## 3, 森林 ##

n个互不相交的树的集合  
即, 多个树, 他们的整体称之为森林.  
  
  
三, 存储  
  
  
四, 操作  
  
  
五, 应用

[SouthEast]: /images/20211126/6939d6a1ca3f483ebaa0440806ccbf46.png
[SouthEast 1]: /images/20211126/d7fad4b73a58476f96bc6ec3666f1331.png
[SouthEast 2]: /images/20211126/82b592970283403285de66b76057ba26.png

发表评论取消回复

表情：

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

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

相关阅读

相关数据结构 - 树的分类

文章目录 * 1. 树的分类 * 2. 二叉树 * * * 2.1 AVL Tree * 2.2 R-B Tree * 3...

野性酷女/ 2024年04月20日 09:03/ 0 赞/ 65 阅读

相关【数据结构】之树的定义

定义定义：树（Tree）是n(n>=0）个结点的有限集。n=0时称为空树。在任意一颗非空树中：（1）有且仅有一个特定的称为根（Root）的结点；（2）当n>1时，其余结

超、凢脫俗/ 2023年02月17日 11:21/ 0 赞/ 45 阅读

相关线性和非线性数据结构分类

数据结构按逻辑和存储结构，可以分为不同的类型按逻辑可以分为以下三种： 1.集合

电玩女神/ 2022年07月13日 19:24/ 0 赞/ 202 阅读

相关数据结构——二叉树定义

数据结构——二叉树定义 1、基本概念二叉树是树形结构中一种特殊的树形结构：二叉树中的每个结点至多有2棵子树（即每个结点的度小于等于2），并且两个子树有左右之分，

逃离我推掉我的手/ 2022年06月16日 11:14/ 0 赞/ 251 阅读

相关 C语言数据结构——树的定义

树是n个结点的有限集。n等于0是称为空树，在任意一棵非空树中，有且仅有一个特定的称为根的结；当n>1时，其余节点可分为m（m>0）个互不相交的有限集，其中每个集合本身

我就是我/ 2022年06月15日 12:13/ 0 赞/ 312 阅读

相关 18_树的子结构

> 输入两棵二叉树A，B，判断B是不是A的子结构 // 第一步判断：查找树A中跟树B根节点的值一样的节点 // root1:A树

客官°小女子只卖身不卖艺/ 2022年06月07日 02:24/ 0 赞/ 173 阅读

相关数据结构之二叉树的定义和性质

通过上一节讲解，我们知道通用树结构是采用双亲孩子表示法模型建立的。每个结点都有一个指向其双亲的指针，每个结点都有若干个指向其孩子的指针。如下图： ![70][]

分手后的思念是犯贱/ 2022年05月31日 09:17/ 0 赞/ 250 阅读

相关数据结构_树的定义及存储结构

树树的特点：不是简单的线性结构，但在确定某种次序之后，具有线性特征。对于树，它集成vector和list的优点，既可以快速插入、删除也可以快速查找。递归定义

比眉伴天荒/ 2022年05月22日 07:38/ 0 赞/ 365 阅读

相关数据结构（五）树的定义

文章目录 1. 树的定义 1. 特征 2. 基本术语 3. 树的表示

红太狼/ 2022年05月14日 14:39/ 0 赞/ 191 阅读

相关 18-数据结构_树-定义和分类

树一, 定义 1, 专业定义 (1) 有且仅有一个称为根的结点 (2) 有若干个互不相交的子树 (3) 子树也是一棵树 2, 通俗定义

Dear 丶/ 2021年11月26日 07:24/ 0 赞/ 270 阅读