Added postorder tree traversal

nem035 · nem035 · commit 75115bfe9142 · 2016-06-03T23:29:29.000-04:00
diff --git a/algorithm/tree/binary_tree_traversal/desc.json b/algorithm/tree/binary_tree_traversal/desc.json
@@ -16,6 +16,7 @@
   ],
   "files": {
     "inorder": "Traverse Binary Tree Inorder",
+    "postorder": "Traverse Binary Tree Postorder",
     "preorder": "Traverse Binary Tree Preorder"
   }
 }
diff --git a/algorithm/tree/binary_tree_traversal/postorder/code.js b/algorithm/tree/binary_tree_traversal/postorder/code.js
@@ -0,0 +1,24 @@
+var index = 0;
+
+function inorder ( root , parent ) {
+	if (root === -1) {
+		logger._print( 'No more nodes. Backtracking.' )._wait ();
+		return;
+	}
+
+	logger._print( 'Reached ' + root);
+	treeTracer._visit ( root , parent )._wait ();
+
+	logger._print ( ' Going left from ' + root )._wait ();
+	inorder(T[root][0], root);
+
+	logger._print ( ' Going right from ' + root )._wait ();
+	inorder(T[root][1], root);
+
+	logger._print( 'Printing ' + root);
+	treeTracer._leave ( root );
+	arrayTracer._notify ( index++, root )._wait();
+}
+
+inorder ( 5 ); // node with key 5 is the root
+logger._print( 'Finished' );
diff --git a/algorithm/tree/binary_tree_traversal/postorder/data.js b/algorithm/tree/binary_tree_traversal/postorder/data.js
@@ -0,0 +1,32 @@
+var G = [ // G[i][j] indicates whether the path from the i-th node to the j-th node exists or not
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
+    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0]
+];
+
+
+var T = [ // mapping to G as a binary tree , [i][0] indicates left child, [i][1] indicates right child
+        [-1,-1],
+        [ 0, 2],
+        [-1,-1],
+        [ 1, 4],
+        [-1,-1],
+        [ 3, 8],
+        [-1, 7],
+        [-1,-1],
+        [ 6,10],
+        [-1,-1],
+        [ 9,-1]
+];
+
+var treeTracer = new DirectedGraphTracer( " Binary Tree Traversal Inorder ")._setTreeData ( G, 5 );
+var arrayTracer = new Array1DTracer( " Binary Tree Print Inorder ")._setData ( new Array(T.length).fill( '-' ) );
+var logger = new LogTracer ( " Log ");

Original file line number	Diff line number	Diff line change
`@@ -16,6 +16,7 @@`
`16`	`16`	`],`
`17`	`17`	`"files": {`
`18`	`18`	`"inorder": "Traverse Binary Tree Inorder",`
	`19`	`+ "postorder": "Traverse Binary Tree Postorder",`
`19`	`20`	`"preorder": "Traverse Binary Tree Preorder"`
`20`	`21`	`}`
`21`	`22`	`}`