一文教你了解树和森林
发布日期:2021-06-29 14:17:48
浏览次数:3
分类:技术文章
本文共 823 字,大约阅读时间需要 2 分钟。
前言
这是我听老师讲课做的笔记。
作者:RodmaChen 关注我的csdn博客,更多数据结构与算法知识还在更新
树和森林
一.树的存储结构
1.双亲表示法
解释:-1代表没有双亲
问题:找双亲简单,找孩子麻烦
2.孩子表示法
左边是顺序存储右边是链式存储(指针域指向孩子)
3.孩子兄弟表示法(重点)
(1)左指针指向该节点的第一个孩子
(2)右指针指向该节点的下一个兄弟
相当于就是将树转换成二叉树
二.树的遍历
- 先序遍历树若树T非空,则: ①先访问根结点 ②然后依次先根遍历根的各子树;
先:ABCEFGD
- 后序遍历树若树非空,则: ①后根遍历根的各子树 ②访问根结点
后:BEGFCDA
总结:树的先序和后序的序列跟它转换成二叉树后的先序和中序的序列是一样的
三.森林
1.定义
森林是零棵或多棵不相交的树的集合(通常是有序集合)。
2.森林与二叉树的转换
①将森林中的每棵树转换成相应的二叉树。
②第一棵二叉树不动,从第二棵二叉树开始,依次把后一棵二叉树的根结点作为前一棵二叉树根结点的右孩子, 当所有二叉树连在一起后,所得到的二叉树就是由森林转换得到的二叉树。
3.森林的遍历
(1) 先序遍历
若森林非空,则可按下述规则遍历之:
①访问森林中第一棵树的根结点;
②先序遍历第一棵树中根结点的子树森林
③先序遍历除去第一棵树之后剩余的树构成的森林。
如上图:ABCDEFGHIJ
(2)后序遍历
若森林非空,则可按下述规则遍历之:
①后序遍历森林中第一棵树的根结点的子树森林;
②访问第一棵树的根结点;
③后序遍历除去第一棵树之后剩余的树构成的森林。
如上图:BCDAFEHJIG
注意:
① 先序遍历森林等同于先序遍历该森林对应的二叉树
② 后序遍历森林等同于中序遍历该森林对应的二叉树
四.边学边练
作者:RodmaChen
本人博客: 本人b站求关注: 转载说明:跟我说明,务必注明来源,附带本人博客连接。
请给我点个赞鼓励我吧
转载地址:https://chenyunzhi.blog.csdn.net/article/details/106713723 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月26日 07时52分24秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
SpringBoot + WebSocket 实现前后端的收发消息
2019-04-29
SpringBoot 整合 JWT 实现统一认证
2019-04-29
SpringBoot 使用 CompletableFuture 实现非阻塞异步编程
2019-04-29
即刻就业:本科毕业如何快速高薪就业?
2019-04-29
JAVA中的浮点数与二进制
2019-04-29
JAVA笔记(二)--Java初始
2019-04-29
JAVA笔记(三)--变量及运算符
2019-04-29
JAVA笔记(四)--三大结构语句
2019-04-29
JAVA语言基础(五)--数组
2019-04-29
JAVA项目案例详解带代码
2019-04-29
JAVA九种排序算法详解
2019-04-29
JAVA笔记(六)面向对象--类和对象
2019-04-29
JAVA笔记(十一)面向对象--多态
2019-04-29
webpack打包错误:Invalid configuration object. Webpack has been initialised using a configuration object
2019-04-29
TypeError: this.getOptions is not a function
2019-04-29
el-table 二维数组合并行
2019-04-29
js获取当月的天数
2019-04-29
多个相邻的盒子外边框合并的问题
2019-04-29
js实现复制功能
2019-04-29