数据结构——有向无环图描述表达式
——本节内容为Bilibili王道考研《数据结构》P65视频内容笔记。
一、定义
有向无环图：若一个有向图中不存在环，则称为有向无环图，简称DAG图（Directed Acyclic Graph），如下图所示；
二、问题描述
1.之前学习过用树的形式来表示一个表达式，比如下面这棵树：
2.不难发现上面这棵树其中有很多部分可以合并，合并完后变为：
3.一般会给出一个算术表达式，让我们来求出所需要的最少的顶点个数，下面给出解答步骤；
三、解题步骤
1.例如题目给出：
2.第一步：把各个操作数不重复地排成一排，如下图：
3.第二步：标出各个运算符的生效顺序（先后顺序有点出入无所谓），如下图：
4.第三步：按顺序加入运算符，注意“分层”，如下图：
5.第四步：从底向上逐层检查同层的运算符是否可以合体，如下图：
四、特殊例子
下一篇：
堆排序的基本概念和基本思路