Some students had trouble with the tree traversal question on the exam. It was suggested you start with the notes, such as at
Tree representation and traversal .
The question is repeated here.
Given a tree in prefix form and only containing variables and the NAND "
!&" binary operator, write a tree traversal routine in a programming language of your choice (except JavaScript) to do an output or transformation which will be one of the following.
output a prefix representation
output an infix representation
output a postfix representation
Note: The tree traversal code should be based on the JavaScript tree traversal code covered in class (and in the notes), except that this problem is simplified in that both integer literals and unary operators are omitted in this problem.
Here is the code for the prefix traversal that prints the prefix expression.
function prefixTextTraverse(tree1) {
var type1 = tree1[0];
var text1 = "";
if (type1 == "op1") {
var op1 = tree1[1];
var opName1 = opDict1[op1];
var right1 = tree1[2];
text1 = "( " + opName1 + " " + prefixTextTraverse(right1) + " )";
}
else if (type1 == "op2") {
var op2 = tree1[1];
var opName2 = opDict1[op2];
var left1 = tree1[2];
var right1 = tree1[3];
text1 = "( " + opName2 + " " + prefixTextTraverse(left1) + " " + prefixTextTraverse(right1) + " )";
}
else if (type1 == "var") {
var name1 = tree1[1];
text1 = name1;
}
else if (type1 == "int") {
var value1 = tree1[1];
text1 = value1;
}
return text1;
}
The question states (and it was repeated in class) that you only need to handle the
var nodes and the
op2 node and only for the NAND operator "
!&".
So the above code simplifies to the following, where the
opDict1 can be omitted since the only operator is "
!&" and the else part can only contain a
var.
function prefixTextTraverse(tree1) {
var type1 = tree1[0];
var text1 = "";
if (type1 == "op2") {
var opName2 = "!&";
var left1 = tree1[2];
var right1 = tree1[3];
text1 = "( " + opName2 + " " + prefixTextTraverse(left1) + " " + prefixTextTraverse(right1) + " )";
}
else {
var name1 = tree1[1];
text1 = name1;
}
return text1;
}
The above could be then converted to the desired language.
However, the above can be simplified to the following by renaming and removing/combining assignment statements. (Some students made this improvement).
function traverse(tree1) {
if (tree1[0] == "op2") {
return "( &! " traverse(tree1[2]) + " " + traverse(tree1[3]) + " )";;
}
else {
return tree1[1];
}
}
From this point, the easiest languages into which to translate this code would probably be Python, PHP, or Lua.
Note: The tree in list form is in JSON so most languages would accept this tree with a suitable call to the JSON library in that language. (But that was not required for this problem).
