Trees/Preorder - Revision history

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

2019-10-09T03:58:53Z

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

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

	The implementation of preorder traversal is implemented in the linked binary tree class [[Binary Trees/LinkedBinTree]] using the following methods:		The implementation of preorder traversal is implemented in the linked binary tree class [[Binary Trees/LinkedBinTree]] using the following methods:
	* A public method that takes no parameters, <code>preorder()</code>, returning an iterator over each node in pretraversal order: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/LinkedBinTree.java#L362		* A public method that takes no parameters, <code>preorder()</code>, returning an iterator over each node in pretraversal order: https://git.charlesreid1.com/cs/java/src/master/trees/LinkedBinTree.java#L362
	* A public method that takes one parameter, a position, <code>preorder(p)</code>, returning an iterator over each node in the subtree rooted at p in pretraversal order: https://charlesreid1.com~~:3000~~/cs/java/src/master/trees/LinkedBinTree.java#L369		* A public method that takes one parameter, a position, <code>preorder(p)</code>, returning an iterator over each node in the subtree rooted at p in pretraversal order: https://git.charlesreid1.com/cs/java/src/master/trees/LinkedBinTree.java#L369
	* 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#L376		* 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#L376

	All the work is done by the last method, and that method doesn't actually do much work - it just adds the current node to the list, and then iterates over the children and calls itself recursively on each child.		All the work is done by the last method, and that method doesn't actually do much work - it just adds the current node to the list, and then iterates over the children and calls itself recursively on each child.

Admin: /* Flags */

2017-09-07T15:46:28Z

Flags

← Older revision		Revision as of 15:46, 7 September 2017
Line 62:		Line 62:

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

Admin at 15:45, 7 September 2017

2017-09-07T15:45:49Z

← Older revision		Revision as of 15:45, 7 September 2017
Line 55:		Line 55:
	=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=

Admin: /* Related Pages */

2017-09-07T12:24:10Z

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

	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]]

Admin: /* Flags */

2017-09-07T12:21:34Z

Flags

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

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

	[[Category:Recursion]]		[[Category:Recursion]]

Admin at 12:20, 7 September 2017

2017-09-07T12:20:30Z

@@ Line 51: / Line 51: @@
+	}
 </pre>
 =Flags=

Admin: /* Implementation */

2017-06-12T12:50:00Z

Implementation

← Older revision		Revision as of 12:50, 12 June 2017
Line 34:		Line 34:

	All the work is done by the last method, and that method doesn't actually do much work - it just adds the current node to the list, and then iterates over the children and calls itself recursively on each child.		All the work is done by the last method, and that method doesn't actually do much work - it just adds the current node to the list, and then iterates over the children and calls itself recursively on each child.


			<pre>
			/** Utility method for pre-order tree traversal. */
			private void preorderSubtree(Position<E> p, List<Position<E>> snapshot) {
			// Base case is, no children, no loop.
			// Recursive case is, this will be called on child nodes.

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

			// 2. Recurse through children
			for(Position<E> c : children(p)) {
			preorderSubtree(c,snapshot);
			}
			}
			</pre>

	=Flags=		=Flags=

Admin: /* Implementation */

2017-06-12T12:49:36Z

Implementation

← Older revision		Revision as of 12:49, 12 June 2017
Line 33:		Line 33:
	* 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#L376		* 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#L376

	All the work is done by the last method, and that method doesn't actually do much work - it just adds the current node to the list, and then iterates over the children and calls itself on each child.d		All the work is done by the last method, and that method doesn't actually do much work - it just adds the current node to the list, and then iterates over the children and calls itself recursively on each child.


	=Flags=		=Flags=

Admin at 12:49, 12 June 2017

2017-06-12T12:49:22Z

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

	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 preorder traversal is implemented in the linked binary tree class [[Binary Trees/LinkedBinTree]] using the following methods:
			* A public method that takes no parameters, <code>preorder()</code>, returning an iterator over each node in pretraversal order: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java#L362
			* A public method that takes one parameter, a position, <code>preorder(p)</code>, returning an iterator over each node in the subtree rooted at p in pretraversal order: https://charlesreid1.com:3000/cs/java/src/master/trees/LinkedBinTree.java#L369
			* 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#L376

			All the work is done by the last method, and that method doesn't actually do much work - it just adds the current node to the list, and then iterates over the children and calls itself on each child.d


	=Flags=		=Flags=

Admin: /* Preorder traversal in trees */

2017-06-11T19:41:39Z

Preorder traversal in trees

← Older revision		Revision as of 19:41, 11 June 2017
Line 1:		Line 1:
	=Preorder traversal in trees=		=Preorder traversal in trees=

	Preorder traversal is a depth-first recursive tree traversal algorithm that can be defined and applied recursively to [[Trees]]. The children do not necessarily need to be ordered - the order refers to the order of depth (bottom-up or top-down) and not order of children. In [[Binary Trees]] an [[Inorder ~~Traversal~~]] can be defined that relies on the convention that in a sorted binary tree the left side comes before the right side.		Preorder traversal is a depth-first recursive tree traversal algorithm that can be defined and applied recursively to [[Trees]]. The children do not necessarily need to be ordered - the order refers to the order of depth (bottom-up or top-down) and not order of children. In [[Binary Trees]] an [[Inorder]] traversal can be defined that relies on the convention that in a sorted binary tree the left side comes before the right side.

	==Recursive definition==		==Recursive definition==