Trees/Postorder - Revision history

Admin: Replacing charlesreid1.com:3000 with git.charlesreid1.com

2019-10-09T03:58:42Z

Replacing charlesreid1.com:3000 with git.charlesreid1.com

← Older revision		Revision as of 03:58, 9 October 2019
Line 27:		Line 27:

	The implementation of postorder traversal is implemented in the linked binary tree class [[Binary Trees/LinkedBinTree]] using the following methods:		The implementation of postorder traversal is implemented in the linked binary tree class [[Binary Trees/LinkedBinTree]] using the following methods:
	* A public method that takes no parameters, <code>postorder()</code>, returning an iterator over each node in postorder traversal order: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/LinkedBinTree.java#L397		* A public method that takes no parameters, <code>postorder()</code>, returning an iterator over each node in postorder traversal order: https://git.charlesreid1.com/cs/java/src/master/trees/LinkedBinTree.java#L397
	* A private method that takes two parameters, one position and one Collections object (a list) to store a list of items for the iterator to return back: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/LinkedBinTree.java#L404		* A private method that takes two parameters, one position and one Collections object (a list) to store a list of items for the iterator to return back: https://git.charlesreid1.com/cs/java/src/master/trees/LinkedBinTree.java#L404

	All the work is done by the second method. It is a recursive method that iterates over each child, recursively calling itself on each child, then adds the current node to the list when finished running on each child.		All the work is done by the second method. It is a recursive method that iterates over each child, recursively calling itself on each child, then adds the current node to the list when finished running on each child.

Admin at 15:46, 7 September 2017

2017-09-07T15:46:42Z

← Older revision		Revision as of 15:46, 7 September 2017
Line 48:		Line 48:
	=Related Pages=		=Related Pages=

	~~Preorder, postorder, and in-order traversals on trees:~~		{{TraversalRelated}}
	* [[Trees/Preorder]]
	* [[Binary Trees/Inorder]]
	* [[Trees/Postorder]]

	~~Breadth-first and depth-first traversals on trees:~~
	* [[DFS]]
	* [[BFS]]

	~~Graphs, generalization of tree structures:~~
	* [[Graphs#Graph Traversals]]

	=Flags=		=Flags=
Line 65:		Line 55:

	[[Category:Trees]]		[[Category:Trees]]
			[[Category:Binary Trees]]
	[[Category:Traversal]]		[[Category:Traversal]]
	[[Category:Graphs]]		[[Category:Graphs]]
	[[Category:Algorithms]]		[[Category:Algorithms]]
	[[Category:Recursion]]		[[Category:Recursion]]

Admin: /* Related Pages */

2017-09-07T12:24:13Z

← Older revision		Revision as of 12:24, 7 September 2017
Line 49:		Line 49:

	Preorder, postorder, and in-order traversals on trees:		Preorder, postorder, and in-order traversals on trees:
			* [[Trees/Preorder]]
	* [[Binary Trees/Inorder]]		* [[Binary Trees/Inorder]]
	* [[Trees/Postorder]]		* [[Trees/Postorder]]
Line 58:		Line 59:
	Graphs, generalization of tree structures:		Graphs, generalization of tree structures:
	* [[Graphs#Graph Traversals]]		* [[Graphs#Graph Traversals]]


	=Flags=		=Flags=

Admin: /* Flags */

2017-09-07T12:21:31Z

Flags

← Older revision		Revision as of 12:21, 7 September 2017
Line 63:		Line 63:

	{{TreesFlag}}		{{TreesFlag}}
	~~{{AlgorithmsFlag}}~~
	[[Category:Trees]]		[[Category:Trees]]
	[[Category:~~DFS~~]]		[[Category:Traversal]]
	[[Category:Graphs]]		[[Category:Graphs]]
	[[Category:Algorithms]]		[[Category:Algorithms]]
	[[Category:Recursion]]		[[Category:Recursion]]

Admin: /* Flags */

2017-09-07T12:20:46Z

Flags

← Older revision		Revision as of 12:20, 7 September 2017
Line 45:		Line 45:

	</pre>		</pre>

			=Related Pages=

			Preorder, postorder, and in-order traversals on trees:
			* [[Binary Trees/Inorder]]
			* [[Trees/Postorder]]

			Breadth-first and depth-first traversals on trees:
			* [[DFS]]
			* [[BFS]]

			Graphs, generalization of tree structures:
			* [[Graphs#Graph Traversals]]


	=Flags=		=Flags=

Admin: /* Recursive definition */

2017-06-12T12:52:41Z

Recursive definition

← Older revision		Revision as of 12:52, 12 June 2017
Line 22:		Line 22:

	Because this is an intransitive recursive function - nothing is returned - the base case can remain implicit (if position is an external node, position.children is empty, and the for loop is not run, and an instance of the void recursive method returns).		Because this is an intransitive recursive function - nothing is returned - the base case can remain implicit (if position is an external node, position.children is empty, and the for loop is not run, and an instance of the void recursive method returns).


			==Implementation==

			The implementation of postorder traversal is implemented in the linked binary tree class [[Binary Trees/LinkedBinTree]] using the following methods:
			* A public method that takes no parameters, <code>postorder()</code>, returning an iterator over each node in postorder traversal order: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java#L397
			* A private method that takes two parameters, one position and one Collections object (a list) to store a list of items for the iterator to return back: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java#L404

			All the work is done by the second method. It is a recursive method that iterates over each child, recursively calling itself on each child, then adds the current node to the list when finished running on each child.

			<pre>
			/** Utility method for post-order tree traversal. */
			private void postorderSubtree(Position<E> p, List<Position<E>> snapshot) {
			// 1. Recurse through children
			for(Position<E> c : children(p)) {
			postorderSubtree(c,snapshot);
			}

			// 2. Perform visit action for Position p
			snapshot.add(p);
			}

			</pre>

	=Flags=		=Flags=

Admin: Created page with "=Postorder traversal in trees= Postorder traversal is a depth-first recursive tree traversal algorithm that can be defined and applied recursively to Trees, very similar..."

2017-06-11T19:40:22Z

Created page with "=Postorder traversal in trees= Postorder traversal is a depth-first recursive tree traversal algorithm that can be defined and applied recursively to Trees, very similar..."

New page

=Postorder traversal in trees=

Postorder traversal is a depth-first recursive tree traversal algorithm that can be defined and applied recursively to [[Trees]], very similar to [[Trees/Preorder]] (preorder traversal). Postorder is a bottom-up traversal, where the visit action is performed as the recursive functions return off the stack.

==Recursive definition==

As with any recursive method, this must be split into a base case and a recursive case. The base case is, we've reached an external node - no children. The recursive case is, we call preorder on each child. In this case we don't need an explicit base case and recursive case.

The postorder traversal is the patient, wait-and-see heuristic.

Here is an example of a postorder traversal pseudocode:

<pre>
define public function postorder( tree )
postorder_subtree( tree, root, 0 )

define private function postorder_subtree( tree, position, depth)
for child in position.children():
postorder_subtree(tree, child, depth+1)
perform visit action on position
</pre>

Because this is an intransitive recursive function - nothing is returned - the base case can remain implicit (if position is an external node, position.children is empty, and the for loop is not run, and an instance of the void recursive method returns).

=Flags=

{{TreesFlag}}
{{AlgorithmsFlag}}
[[Category:Trees]]
[[Category:DFS]]
[[Category:Graphs]]
[[Category:Algorithms]]
[[Category:Recursion]]