【C/C++ 数据结构 】树的 四种表示方法

简介: 【C/C++ 数据结构 】树的 四种表示方法

树的4种方式方法

树是一种非常重要的数据结构,在计算机科学和许多其他领域中都有广泛的应用。下面我将为你详细介绍你提到的四种树的表示方法。

1. 树形表示法 (Tree Diagram)

树形表示法是一种直观的表示方法,它将树结构画出来,每个节点都表示为一个盒子,而节点之间的关系则通过线来表示。这种表示法直观易懂,常用于教学和概念说明。

2. 嵌套集合表示法 (Nested Set Model)

嵌套集合表示法是一种将树结构存储在关系数据库中的方法。每个节点都有两个值:左值和右值。对于树中的任意一个节点,其子树中所有节点的左值都大于该节点的左值,右值都小于该节点的右值。这种方法便于快速查询树结构中的数据,但更新操作较为复杂。

嵌套集合表示法(Nested Set Model)是一种在关系数据库中存储和查询树形结构的有效方法。为了使用这种表示法,每个节点都被分配了两个值:左值(left value)和右值(right value)。这两个值遵循以下规则:

1. 左值和右值的分配规则:
  • 每个节点的左值都小于其右值。
  • 对于任意节点,其所有子节点的左值都大于该节点的左值,其所有子节点的右值都小于该节点的右值。
  • 对于树中的任意两个不同的节点,其左值和右值的范围不会重叠。
2. 如何分配左值和右值:
  • 从树的根节点开始,初始化一个计数器(通常从1开始)。
  • 对于每个节点,先分配左值(即当前计数器的值),然后增加计数器。
  • 递归地对该节点的所有子节点执行相同的操作。
  • 当所有子节点都处理完后,为该节点分配右值(即当前计数器的值),然后增加计数器。
3. 查询操作:
  • 要找到一个节点的所有后代,可以查询所有左值大于该节点左值且右值小于该节点右值的节点。
  • 要找到一个节点的所有祖先,可以查询所有左值小于该节点左值且右值大于该节点右值的节点。
4. 更新操作:
  • 更新操作相对复杂,因为当插入或删除节点时,可能需要更新大量节点的左值和右值。

这种表示法的优点是查询操作非常快速,尤其是在查找所有后代或所有祖先的情况下。但是,更新操作可能会比较慢,因为它可能涉及到更新大量的左值和右值。

3. 凹形表示法 (Indented List)

凹形表示法是一种文本表示方法,通过缩进的层级来表示节点之间的父子关系。每个节点占一行,子节点相对于父节点有一定数量的缩进。这种方法简单直观,常用于配置文件和简单的数据表示。

4. 广义表表示法 (Generalized List)

广义表是一种递归定义的数据结构,它可以是一个原子元素,也可以是一个表。在树的表示中,每个节点可以是一个原子元素,也可以是一个包含其他节点的列表。这种表示法非常灵活,但解析起来较为复杂。

这四种表示方法各有优缺点,适用于不同的场景和需求。树形表示法直观易懂,适合于教学和概念说明;嵌套集合表示法适用于存储在关系数据库中,便于快速查询;凹形表示法简单直观,适用于配置文件和简单数据表示;广义表表示法灵活但解析复杂,适用于需要高度灵活性的场景。

树的表示方法示例

好的,我将以一个简单的二叉树为例,来展示这几种表示法。

假设我们有如下的二叉树:

A
   / \
  B   C
 / \
D   E

1. 树形表示法 (Tree Diagram)

A
   / \
  B   C
 / \
D   E

在树形表示法中,我们直接将树结构画出来,每个节点都表示为一个盒子,而节点之间的关系则通过线来表示。

2. 嵌套集合表示法 (Nested Set Model)

假设我们有如下的二叉树:

A
   / \
  B   C
 / \
D   E
正确的嵌套集合表示法 (Nested Set Model) 示例:
1 A (1, 10)
2 B (2, 7)
3 D (3, 4)
4 E (5, 6)
5 C (8, 9)

在这个例子中:

  • A 的左值是 1,右值是 10。
  • B 的左值是 2,右值是 7。
  • D 的左值是 3,右值是 4。
  • E 的左值是 5,右值是 6。
  • C 的左值是 8,右值是 9。
规则解释:
  • 每个节点的左值都小于其右值。
  • 对于任意节点,其所有子节点的左值都大于该节点的左值,其所有子节点的右值都小于该节点的右值。
  • 左值从 1 开始,对树进行深度优先遍历,每访问一个节点,就分配一个左值,然后再分配一个右值。
  • 在这个例子中,我们首先访问 A,分配左值 1。然后我们访问 B,分配左值 2。接着我们访问 D,分配左值 3 和右值 4。回到 B,分配右值 7。然后是 E,分配左值 5 和右值 6。回到 A,分配右值 10。最后是 C,分配左值 8 和右值 9。

这样,我们就能看到,所有子节点的左值和右值都在其父节点的左值和右值之间。这也解释了为什么左值和右值不是连续的,因为它们是根据树的结构和遍历顺序来分配的。

3. 凹形表示法 (Indented List)
A
  B
    D
    E
  C

在凹形表示法中,我们通过缩进的层级来表示节点之间的父子关系。每个节点占一行,子节点相对于父节点有一定数量的缩进。

4. 广义表表示法 (Generalized List)
(A, (B, (D, E), C))

在广义表表示法中,每个节点可以是一个原子元素,也可以是一个包含其他节点的列表。在这个例子中,A是根节点,它有两个子节点B和C。B又有两个子节点D和E。

这四种表示法各有其特点,适用于不同的场景和需求。树形表示法直观易懂,嵌套集合表示法适用于存储在关系数据库中,凹形表示法简单直观,广义表表示法灵活但解析复杂。

结语

在我们的编程学习之旅中,理解是我们迈向更高层次的重要一步。然而,掌握新技能、新理念,始终需要时间和坚持。从心理学的角度看,学习往往伴随着不断的试错和调整,这就像是我们的大脑在逐渐优化其解决问题的“算法”。

这就是为什么当我们遇到错误,我们应该将其视为学习和进步的机会,而不仅仅是困扰。通过理解和解决这些问题,我们不仅可以修复当前的代码,更可以提升我们的编程能力,防止在未来的项目中犯相同的错误。

我鼓励大家积极参与进来,不断提升自己的编程技术。无论你是初学者还是有经验的开发者,我希望我的博客能对你的学习之路有所帮助。如果你觉得这篇文章有用,不妨点击收藏,或者留下你的评论分享你的见解和经验,也欢迎你对我博客的内容提出建议和问题。每一次的点赞、评论、分享和关注都是对我的最大支持,也是对我持续分享和创作的动力。

目录
相关文章
|
5天前
|
算法 测试技术 C++
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(下)
|
5天前
|
C++ 容器
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
【C++】map&set的底层结构 -- AVL树(高度平衡二叉搜索树)(上)
|
1天前
|
存储 C++ 索引
c++数据结构
c++数据结构
10 3
|
3天前
|
存储 算法 C++
c++算法学习笔记 (8) 树与图部分
c++算法学习笔记 (8) 树与图部分
|
4天前
|
存储
数据结构(树)
数据结构(树)
12 1
|
6天前
|
存储 分布式数据库
【数据结构】树和二叉树
【数据结构】树和二叉树
|
7天前
|
存储 移动开发 算法
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构(下)
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构
20 0
|
7天前
|
机器学习/深度学习 算法 搜索推荐
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构(上)
数据结构与算法⑩(第四章_上)树和二叉树和堆的概念及结构
12 0
|
8天前
|
存储
数据结构-树的介绍、树的定义和基本术语
树是一种非线性的数据结构,是以分支关系定义的层次结构,比如人类社会中的族谱、及各种机制、组织的关系都可以用树形象的表示。重点学习二叉树的存储和相关操作,还要讨论树、森林、二叉树的转换关系。
14 0
|
11天前
|
C语言 C++
C++|运算符重载(2)|运算符重载的方法与规则
C++|运算符重载(2)|运算符重载的方法与规则