数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会研究
时尚研究
法律研究数据结构中构建表达式树的算法
表达式树
表达式树用于将要操作的值放在叶节点上，并将操作符放在叶节点将对其进行操作的内部节点上。
示例
4 + ((7 + 9) * 2) 的表达式树如下所示
构建表达式树的算法
令 T 为表达式树。
If T is not NULL:
If T->data is an operand:
return T.data
A = solve(T.left)
B = solve(T.right)
--> Calculate operator for 'T.data' on A and B, and call recursively,
return calculate(A, B, T.data)
如何构建表达式树？
要为给定的表达式构建表达式树，我们通常使用栈数据结构。
最初，我们遍历给定的后缀表达式并按照如下步骤进行操作 -
- 如果我们在给定的表达式中获取到一个操作数，则将其压入栈中。它将成为表达式树的根。
- 如果一个操作符在表达式中获取到两个值，则将其作为其子级添加到表达式树中，并将其压入当前节点。
- 重复步骤 1 和步骤 2，直至完成对给定表达式的遍历。
- 现在检查每个根节点是否仅包含操作数，并且每个子节点是否仅包含值。
更新于：23-2-2021
8K+ 浏览量
广告