binary-tree - Construct binary tree from prefix order expression

Question

How should we construct the binary tree of the following "prefix" order expression?

( - * / 8 + 5 1 4 + 3 - 5 / 18 6 )

Is there any rule to follow for drawing the tree?

Answer 1

伪代码是这样的：

function 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

这里expr保留一个指向下一个元素所在位置的内部指针。