所以我有一个二叉树和一个后缀表达式“6 2 * 3 /”将它放在树中的算法是什么?像,
[/]
/ \
[*] [3]
/ \
[6] [2]
所以我有一个二叉树和一个后缀表达式“6 2 * 3 /”将它放在树中的算法是什么?像,
[/]
/ \
[*] [3]
/ \
[6] [2]
要从表达式构造树,假设您正在直接评估它,但构造树而不是计算数字。(这个技巧适用于比后缀表达式更多的东西。)
算法:有一个堆栈来存储中间值(即树),并从左到右检查每个标记:
最后,如果表达式格式正确,那么堆栈上应该只有一棵树,它是树形的整个表达式。
Postfix-to-tree(j){
n <--ALLOCATE_NODE(A[j],NULL,NULL)
Switch
case Postfix[j] is a binary operator
do j <--j-1
right[n] <-- Postfix-to-tree(j)
j <-- j-1
left[n] <--postfix-to-tree(j)
case postfix[j] is a unary operator
do j <-- j-1
right[n] <-- Postfix-to-tree(j)
}