Tree representation and traversal

Send Close Add comments: (status displays here)

Got it! This site uses cookies. You consent to this by clicking on "Got it!" or by continuing to use this website.nbsp; Note: This appears on each machine/browser from which this site is accessed.

Tree representation and traversal

by RS admin@ycp.powersoftwo.org

1. Tree representation and traversal

2. Tree representation

3. Logical expression

This page looks at how logical expressions can be represented and traversed using JavaScript code.

The (fully parenthesized) logical expression is as follows.

( X & Y ) | ( ( ! X ) & ( ! Y ) )

4. Code conventions

The following code examples use the following.

A dictionary to look up the symbol name for a given operator name.
A prefix tree representation of the above logical expression.
The name "op1" is for a unary operator. The type and one argument follows.
The name "op2" is for a binary operator. The type and two argument follow.

Note: All tree lists are the same, but could not be easily separated for this page.

5. Code examples

The following code examples are provided.

Prefix: line by line
Infix: line by line
Postfix : line by line
Prefix: text string
Infix: text string
Postfix: text string

Study each one to understand how it works.

6. JavaScript code

Here is the JavaScript code.

var opDict1 = {
	"not" : "!",
	"and" : "&",
	"or" : "|",
	"xor" : "^",
	"eql" : "="
	};
var treeList1 = [
	"op2",
	"or",
	[
		"op2",
		"and",
		["var", "x"],
		["var", "y"],
		],
	[
		"op2",
		"and",
		[
			"op1",
			"not",
			["var", "x"],
			],
		[
			"op1",
			"not",
			["var", "y"],
			],
		]
	];

function prefixLineTraverse(tree1) {
	var type1 = tree1[0];
	if (type1 == "op1") {
		var op1 = tree1[1];
		var opName1 = opDict1[op1];
		var right1 = tree1[2];
		console.log("(\n");
		console.log(opName1+"\n");
		prefixLineTraverse(right1);
		console.log(")\n");
		}
	else if (type1 == "op2") {
		var op2 = tree1[1];
		var opName2 = opDict1[op2];
		var left1 = tree1[2];
		var right1 = tree1[3];
		console.log("(\n");
		console.log(opName2+"\n");
		prefixLineTraverse(left1);
		prefixLineTraverse(right1);
		console.log(")\n");
		}
	else if (type1 == "var") {
		var name1 = tree1[1];
		console.log(name1+"\n");
		}
	else if (type1 == "int") {
		var value1 = tree1[1];
		console.log(value1+"\n");
		}
	}
console.log("prefix:\n");
prefixLineTraverse(treeList1);

7. JavaScript output

Here is the output of the JavaScript code.

prefix:

(

|

(

&

x

y

)

(

&

(

!

x

)

(

!

y

)

)

)

8. JavaScript code

Here is the JavaScript code.

var opDict1 = {
	"not" : "!",
	"and" : "&",
	"or" : "|",
	"xor" : "^",
	"eql" : "="
	};
var treeList1 = [
	"op2",
	"or",
	[
		"op2",
		"and",
		["var", "x"],
		["var", "y"],
		],
	[
		"op2",
		"and",
		[
			"op1",
			"not",
			["var", "x"],
			],
		[
			"op1",
			"not",
			["var", "y"],
			],
		]
	];

function infixLineTraverse(tree1) {
	var type1 = tree1[0];
	if (type1 == "op1") {
		var op1 = tree1[1];
		var opName1 = opDict1[op1];
		var right1 = tree1[2];
		console.log("(\n");
		console.log(opName1+"\n");
		infixLineTraverse(right1);
		console.log(")\n");
		}
	else if (type1 == "op2") {
		var op2 = tree1[1];
		var opName2 = opDict1[op2];
		var left1 = tree1[2];
		var right1 = tree1[3];
		console.log("(\n");
		infixLineTraverse(left1);
		console.log(opName2+"\n");
		infixLineTraverse(right1);
		console.log(")\n");
		}
	else if (type1 == "var") {
		var name1 = tree1[1];
		console.log(name1+"\n");
		}
	else if (type1 == "int") {
		var value1 = tree1[1];
		console.log(value1+"\n");
		}
	}
console.log("infix:\n");
infixLineTraverse(treeList1);

9. JavaScript output

Here is the output of the JavaScript code.

infix:

(

(

x

&

y

)

|

(

(

!

x

)

&

(

!

y

)

)

)

10. JavaScript code

Here is the JavaScript code.

var opDict1 = {
	"not" : "!",
	"and" : "&",
	"or" : "|",
	"xor" : "^",
	"eql" : "="
	};
var treeList1 = [
	"op2",
	"or",
	[
		"op2",
		"and",
		["var", "x"],
		["var", "y"],
		],
	[
		"op2",
		"and",
		[
			"op1",
			"not",
			["var", "x"],
			],
		[
			"op1",
			"not",
			["var", "y"],
			],
		]
	];

function postfixLineTraverse(tree1) {
	var type1 = tree1[0];
	if (type1 == "op1") {
		var op1 = tree1[1];
		var opName1 = opDict1[op1];
		var right1 = tree1[2];
		postfixLineTraverse(right1);
		console.log(opName1+"\n");
		}
	else if (type1 == "op2") {
		var op2 = tree1[1];
		var opName2 = opDict1[op2];
		var left1 = tree1[2];
		var right1 = tree1[3];
		postfixLineTraverse(left1);
		postfixLineTraverse(right1);
		console.log(opName2+"\n");
		}
	else if (type1 == "var") {
		var name1 = tree1[1];
		console.log(name1+"\n");
		}
	else if (type1 == "int") {
		var value1 = tree1[1];
		console.log(value1+"\n");
		}
	}
console.log("postfix:\n");
postfixLineTraverse(treeList1);

11. JavaScript output

Here is the output of the JavaScript code.

postfix:

x

y

&

x

!

y

!

&

|

12. JavaScript code

Here is the JavaScript code.

var opDict1 = {
	"not" : "!",
	"and" : "&",
	"or" : "|",
	"xor" : "^",
	"eql" : "="
	};
var treeList1 = [
	"op2",
	"or",
	[
		"op2",
		"and",
		["var", "x"],
		["var", "y"],
		],
	[
		"op2",
		"and",
		[
			"op1",
			"not",
			["var", "x"],
			],
		[
			"op1",
			"not",
			["var", "y"],
			],
		]
	];

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;
	}
console.log("prefix:\n");
var text1 = prefixTextTraverse(treeList1);
console.log("\t"+text1+"\n");

13. JavaScript output

Here is the output of the JavaScript code.

prefix:

	( | ( & x y ) ( & ( ! x ) ( ! y ) ) )

14. JavaScript code

Here is the JavaScript code.

var opDict1 = {
	"not" : "!",
	"and" : "&",
	"or" : "|",
	"xor" : "^",
	"eql" : "="
	};
var treeList1 = [
	"op2",
	"or",
	[
		"op2",
		"and",
		["var", "x"],
		["var", "y"],
		],
	[
		"op2",
		"and",
		[
			"op1",
			"not",
			["var", "x"],
			],
		[
			"op1",
			"not",
			["var", "y"],
			],
		]
	];

function infixTextTraverse(tree1) {
	var type1 = tree1[0];
	var text1 = "";
	if (type1 == "op1") {
		var op1 = tree1[1];
		var opName1 = opDict1[op1];
		var right1 = tree1[2];
		text1 = "( " + opName1 + " " + infixTextTraverse(right1) + " )";
		}
	else if (type1 == "op2") {
		var op2 = tree1[1];
		var opName2 = opDict1[op2];
		var left1 = tree1[2];
		var right1 = tree1[3];
		text1 = "( " + infixTextTraverse(left1) + " " + opName2 + " " + infixTextTraverse(right1) + " )";
		}
	else if (type1 == "var") {
		var name1 = tree1[1];
		text1 = name1;
		}
	else if (type1 == "int") {
		var value1 = tree1[1];
		text1 = value1;
		}
	return text1;
	}
console.log("infix:\n");
var text1 = infixTextTraverse(treeList1);
console.log("\t"+text1+"\n");

15. JavaScript output

Here is the output of the JavaScript code.

infix:

	( ( x & y ) | ( ( ! x ) & ( ! y ) ) )

16. JavaScript code

Here is the JavaScript code.

var opDict1 = {
	"not" : "!",
	"and" : "&",
	"or" : "|",
	"xor" : "^",
	"eql" : "="
	};
var treeList1 = [
	"op2",
	"or",
	[
		"op2",
		"and",
		["var", "x"],
		["var", "y"],
		],
	[
		"op2",
		"and",
		[
			"op1",
			"not",
			["var", "x"],
			],
		[
			"op1",
			"not",
			["var", "y"],
			],
		]
	];

function postfixTextTraverse(tree1) {
	var type1 = tree1[0];
	var text1 = "";
	if (type1 == "op1") {
		var op1 = tree1[1];
		var opName1 = opDict1[op1];
		var right1 = tree1[2];
		text1 = postfixTextTraverse(right1) + " " + opName1;
		}
	else if (type1 == "op2") {
		var op2 = tree1[1];
		var opName2 = opDict1[op2];
		var left1 = tree1[2];
		var right1 = tree1[3];
		text1 = postfixTextTraverse(left1) + " " + postfixTextTraverse(right1) + " " + opName2;
		}
	else if (type1 == "var") {
		var name1 = tree1[1];
		text1 = name1;
		}
	else if (type1 == "int") {
		var value1 = tree1[1];
		text1 = value1;
		}
	return text1;
	}
console.log("postfix:\n");
var text1 = postfixTextTraverse(treeList1);
console.log("\t"+text1+"\n");

17. JavaScript output

Here is the output of the JavaScript code.

postfix:

	x y & x ! y ! & |

18. End of page

by RS admin@ycp.powersoftwo.org