[入门必看]数据结构5.4：树、森林

9月前作者：H3T 分类：Toy博客阅读(38) 违法举报

这篇具有很好参考价值的文章主要介绍了[入门必看]数据结构5.4：树、森林。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

第五章树与二叉树

小题考频：30
大题考频：8

5.4 树、森林

难度：☆☆☆

知识总览

5.4.1 树的存储结构

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

5.4.2 树、森林与二叉树的转化

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

5.4.3 树和森林的遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

5.4.1 树的存储结构

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

树的逻辑结构

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

树是一种递归定义的数据结构
一棵树要么是空树，要么至少有一个根结点，根结点的下方可能有零棵或多棵互不相交的子树。

二叉树：一个分支结点最多只能有两棵子树
树：一个分支结点可以有多棵子树

如何用顺序存储来存储树这种数据结构？

回顾：二叉树的顺序存储

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

二叉树的顺序存储：按照完全二叉树中的结点顺序，将各结点存储到数组的对应位置。数组下标反映结点之间的逻辑关系

顺序存储二叉树时，结点编号会和完全二叉树对应。
那么这种思路能否推广到普通的树？

如何实现树的顺序存储？

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

由于每个分支结点的子树数量不确定，所以没有与之对应的“完全树”，单纯依靠数组下标无法判断结点之间的逻辑关系。

可以发现树中，除了根结点外，其他任意结点都有且只有一个双亲结点（父结点）。

思路：用数组顺序存储各个结点。每个结点对应一个数组下标，在其中保存数据元素、指向双亲结点（父结点）的“指针”

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

树的存储1：双亲表示法

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

数组元素中，包含两个字段，第一个字段表示数据元素，第二个字段用一个int型变量指明双亲在数组中的下标是多少。
用刚才定义的结构体声明一个数组。
最后记录结点的总数。

拓展：双亲表示法存储“森林”

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

双亲表示法的优缺点

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

优点：找双亲（父结点）好
缺点：找孩子难，要遍历整个数组
应用场景：找父亲多，找孩子少，Eg.并查集

树的存储2：孩子表示法

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

在每个数组在链表元素中，保留一个链表头指针，如果其有孩子，在链表中保存所有孩子结点的编号

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

孩子表示法是顺序存储+链式存储结合
一个数组元素中包含data和一个链表CTNode的指针，链表结点中保存孩子的编号以及指向下一个链表结点的指针。
用刚才定义的结构体CTBox声明一个数组，存储各结点的信息。
并记录结点总数和根的位置。

拓展：孩子表示法存储“森林”

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

用孩子表示法存储森林，需要记录多个根的位置

孩子表示法的优缺点

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

优点：找孩子好
缺点：找双亲（父结点）难，要遍历整个数组
应用场景：找孩子多，找父亲少，Eg.服务流程树【办理业务请按1】

树的存储3：孩子兄弟表示法

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

链式实现
结构体包含数据，和两个指针，第一个指针指向第一个孩子，第二个指针指向右边一个兄弟【类似二叉树结点的定义】
采用二叉链表实现

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

根结点是A，左指针指向B，右指针指向NULL；
C是B的右边第一个兄弟结点，连到B的右指针，D结点连到C的右指针；
E是B的第一个孩子，连到B的左指针；
F是E的右边第一个兄弟结点，连到E的右指针，G结点连到F的右指针，H连到G的右指针，I连到H的右指针，J连到I的右指针；
K是E的第一个孩子，连到E的左指针。

孩子兄弟表示法形态和二叉树类似。

拓展：孩子兄弟表示法存储“森林”

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

把树根C看做B的兄弟，连到B右指针上，以此类推。

5.4.2 树、森林与二叉树的转化

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

树->二叉树的转换

用孩子兄弟表示法存储树或者森林的时候会呈现出和二叉树类似的形态。
树、森林与二叉树的转换本质上就是画出用孩子兄弟表示法表示的树和森林。

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

树 -> 二叉树转换技巧：
① 先在二叉树中，画一个根结点。
② 按**“树的层序”**依次处理每个结点。

处理一个结点的方法是：如果当前处理的结点在树中有孩子，就把所有孩子结点“用右指针串成糖葫芦”，并在二叉树中把第一个孩子挂在当前结点的左指针下方

Eg1：

A结点：

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论 ----->

B结点：
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论 ----->

C结点：
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

H结点：
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

Eg2.
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

森林->二叉树的转换

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论
思路同上。
注意，第一步：森林中各树的根结点视为兄弟，用右指针串起来。

Eg2.

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

二叉树->树的转换

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论
还原A结点：

以此类推还原。

Eg2.
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

二叉树->森林的转换

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论
原理类似。
注意，先将根节点和一串右指针还原成多棵树的根结点。

Eg2.
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

5.4.3 树和森林的遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

树的逻辑结构

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

有递归特性，可以用递归算法来实现对树的遍历

树的先根遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

访问根结点visit(R)，接下来用while循环来检查其还有没有下一个没有被访问过的子树。
如果有，那么对子树也采取先根遍历的策略。

树的先根遍历序列与这棵树相应二叉树的先序序列相同。

树的后根遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

原理类似，处理完所有子树时访问结点。
树的后根遍历序列与这棵树相应二叉树的后序序列相同。

树的层次遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论
实现思路和二叉树一样，用一个辅助队列来实现

根结点入队：
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论
队头元素出队，该元素的孩子依次入队

重复该过程

尽量横向探索，也叫广度优先遍历。
那么先根遍历和后根遍历，也叫深度优先遍历。

森林的先序遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

森林去掉根结点后各子树又组成森林，森林这种数据结构是和树相互递归定义的
可以用递归的思想来遍历森林

首先，访问森林中第一棵树的根结点B
先序遍历第一棵树中根结点的子树森林，E、F两棵树组成的森林
重复第一步，先访问森林中第一棵树的根结点E
遍历E的两个子树森林，即K、L两棵树组成的森林
遍历完K后，再遍历除了第一棵树K之后的剩余的树构成的森林，即L

效果等同于依次对各个树进行先根遍历
可以对各个子树进行一个先序遍历，然后排出一个完整的序列

另一种方法：转换成与之对应的二叉树：
数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

效果等同于依次对二叉树的先序遍历

森林的中序遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论
同样可以转换成与之对应的二叉树：

效果等同于依次对二叉树的中序遍历

知识回顾与重要考点

5.4.1 树的存储结构

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

双亲表示法：顺序存储，保存父结点下标，易找父，难找孩
孩子表示法：顺序存储，保存孩子链表头指针（顺序+链式），易找孩，难找父
孩子兄弟表示法：二叉链表存储，左孩子右兄弟，形态上和二叉树类似

重要考点：树、森林与二叉树的转换

5.4.2 树、森林与二叉树的转化

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论

本质上就是用孩子兄弟表示法存储树或森林
存储森林时，将每棵树的根结点视为兄弟
Tips：记“本质”，不记方法。方法只是表象，“本质”才是内核。

5.4.3 树和森林的遍历

数据结构森林,# 第5章树与二叉树,数据结构,算法,图论文章来源地址https://www.toymoban.com/news/detail-773487.html

对森林的遍历可以转换成对二叉树的遍历

到了这里，关于[入门必看]数据结构5.4：树、森林的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：如若内容造成侵权/违法违规/事实不符，请点击违法举报进行投诉反馈，一经查实，立即删除！

分享到：

领支付宝红包赞助服务器费用

[数据结构] 树与二叉树

树是由 (n(n geq 0)) 个节点组成的有限集。当 (n = 0) 时，称为空树。任意一棵非空树应满足以下两点：（1）有且仅有一个特定的称为根的节点；（2）当 (n 1) 时，其余节点可分为 (m(m0)) 个互不相交的有限集 (T_1, T_2, dots, T_m) ，其中每个集合本身又是一棵树，称为根的

2024年03月09日
浏览(40)
【数据结构】树与二叉树

树是一种非线性的数据结构，它是由n（n=0）个有限结点组成一个具有层次关系的集合。把它叫做树是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。它具有以下的特点：有一个特殊的结点，称为根结点，根结点没有前驱结点除根结点外，其余结点被分

2024年02月11日
浏览(42)
数据结构_树与二叉树

目录 1. 树的基本概念 1.1 树的定义 1.2 基本术语 1.3 树的性质 1.4 相关练习 2. 二叉树的概念 2.1 二叉树的概念及其主要特性 2.2 二叉树的存储结构 2.2.1 顺序存储结构 2.2.2 链式存储结构 2.3 相关练习 3. 二叉树的遍历和线索二叉树 3.1 二叉树的遍历 3.1.1 先序遍历 3.1.2 中序遍历 3.1

2024年02月04日
浏览(45)
【数据结构】树与二叉树（中）

目录前言：一、顺序存储结构：二、堆： 1.堆的性质： 2.堆的性质： 3.堆的实现： Ⅰ.堆的初始化： Ⅱ.堆的插入（含向上调整）： Ⅲ.堆的删除（含向下调整算法）： Ⅳ.取堆顶的数据： Ⅴ.堆中的数据个数： Ⅵ.堆的判空： Ⅶ.堆的销毁：总结：上篇文章中，

2024年02月16日
浏览(45)
数据结构：图文详解树与二叉树（树与二叉树的概念和性质，存储，遍历）

目录一.树的概念二.树中重要的概念三.二叉树的概念满二叉树完全二叉树四.二叉树的性质五.二叉树的存储六.二叉树的遍历前序遍历中序遍历后序遍历树是一种非线性数据结构，它由节点和边组成。树的每个节点可以有零个或多个子节点，其中一个节点被指定为

2024年02月04日
浏览(49)
数据结构与算法——树与二叉树

😊各位小伙伴久等了，本专栏新文章出炉了！！！我又回来啦，接下来的时间里，我会持续把数据结构与算法专栏更新完。 👉树型结构👈 是一类重要的 ✍非线性数据结构，其中以树和二叉树最为常用，直观来看，树是以分支关系定义的层次结构。树型结构在客观世界中

2024年02月11日
浏览(43)
【数据结构与算法】树与二叉树

除了之前我们讲的栈、队列、链表等线性结构，数据结构中还有着一对多的非线性结构 ——— 树。树是有 n 个结点组成的有限集，当n=0时为空树，在任意一颗非空树中，有且仅有一个特定的根结点；当n1时，其余结点又可以分为一棵树，称为根的子树。如下图所示: A为

2023年04月09日
浏览(48)
数据结构与算法——树与二叉树篇详解

树形结构是一种非常重要的非线性结构，树形结构中数据元素之间具有一对多的逻辑关系。 1.1.1 树的定义树是由n(n=0)个结点所构成的有限集合当n=0时，称为空树当n0时，n个结点满足以下条件有且仅有一个称为根的结点其余结点可分为m个互不相交的有限集合，且每一个

2024年02月06日
浏览(50)
【数据结构】24王道考研笔记——树与二叉树

树是n个结点的有限集合，n=0时，称为空树。非空树满足：除了根节点外，任何一个结点都有且仅有一个前驱结点的层次（深度）：从上往下数结点的高度：从下往上数树的高度（深度）：总共有多少层结点的度：有几个孩子（分支）树的度：各节点的度的最大值森林：

2024年02月13日
浏览(47)
数据结构--》解锁数据结构中树与二叉树的奥秘（二）

数据结构中的树与二叉树，是在建立非线性数据结构方面极为重要的两个概念。它们不仅能够模拟出生活中各种实际问题的复杂关系，还常被用于实现搜索、排序、查找等算法，甚至成为一些大型软件和系统中的基础设施。无论你是初学者还是进阶者，

2024年02月08日
浏览(43)