我们应该如何构造以下“前缀”顺序表达式的二进制树?
(-* / 8 + 5 1 4 + 3-5 / 18 6)
4
伪代码是这样的:
public ExpressionRootNode MakeBinaryTree(expr):
element = next element in expr
if element is a number:
return a leaf node of that number
else: // element is an operator
left = MakeBinaryTree(expr)
right = MakeBinaryTree(expr)
return a binary tree with subtrees left and right and with operator element
//^aka return root
但是,我不太了解如何递归调用该函数来创建所述树。
我尝试查看如何Create a binary tree from an algebraic expression,但无法弄清楚如何回溯到另一个节点。
项目文件:http://pastebin.com/BJiPtDM5,一团糟。
最佳答案
更多伪代码:
abstract class Tree { .... }
class Leave extends Tree { int number; ... }
class Expr extends Tree { Tree left, right; String operation; .... }
public Tree makeBinaryTree(expr):
element = next element in expr
if element is a number:
return new Leave(element)
else: // element is an operator
left = makeBinaryTree(expr)
right = makeBinaryTree(expr)
return new Expr(left, right, element)
Leave / Expr的构造函数应仅根据其参数设置字段。
不过,剩下要做的是一些错误处理。哦,请确保“ expr中的下一个元素”也删除了已经处理过的部分。
给定正确的输入,它将像这样工作:
如果输入只是一个数字,它将返回带有该数字的请假
如果输入的格式为OP L R,它将记住OP,从L生成左子树,从R生成右子树,并将其作为表达式返回。
没有其他输入可能/有效
例:
* + 5 1 7
将导致:
Expr(Expr(Leave(5), Leave(1), "+"), Leave(7), "*")
请注意,这些前缀表达式无法查看“-”是否应为一元否定或二进制减法。因此,您不能为此使用相同的运算符。