# Difference between revisions of "Trees/Preorder"

### From charlesreid1

(→Flags) |
m (Replacing charlesreid1.com:3000 with git.charlesreid1.com) |
||

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 | + | * 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 | + | * 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 | + | * 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. |

## Latest revision as of 03:58, 9 October 2019

## Contents

# 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.

## Recursive definition

(See also: Recursion)

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 preorder traversal is the heuristic utilized in a "greedy" Traveling Salesperson Problem TSP algorithm. See also: https://charlesreid1.github.io/ (several blog posts documenting implementations and profiling TSP code in Java).

Here is an example of a preorder traversal pseudocode:

define public function preorder( tree ) preorder_subtree( tree, root, 0 ) define private function preorder_subtree( tree, position, depth) perform visit action on position for child in position.children(): preorder_subtree(tree, child, depth+1)

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,
`preorder()`

, 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,
`preorder(p)`

, 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://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.

/** 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); } }

# Related Pages

Graphs:

- Graphs#Graph Traversals
- Graphs/Depth First Traversal
- Graphs/Breadth First Traversal
- Graphs/Euler Tour
- Graphs/Euler Circuit

Traversals on trees:

Breadth-first search and traversal on trees:

Depth-first search and traversal on trees:

OOP design patterns:

# Flags

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |