Unit 3: Data Structure

Unit 3: Data Structure

Pre-order traversal (depth first search):
Order - root, traverse the left sub-tree then traverse the right sub-tree

Binary trees and traversal
Pre-order traversal

Order - Traverse left sub-tree, node, then traverse right sub-tree.

Binary trees and traversal
In-order traversal

Order - Traverse left sub-tree, then traverse right sub-tree, then the node.

Binary trees and traversal
Post-order traversal

Draw

A binary tree structure is designed to contain strings and uses the following rules:

• The left pointer indicates the condition “earlier or at the same position in the alphabet”

• The right pointer indicates the condition “later in the alphabet”

Construct a binary tree using these rules and the data entered in the following order: Goat, Duck, Fox, Bear, Ant, Cat, Leopard, Owl, Mayfly, Insect, Jaguar, Emu.

You may use the initial letters if you wish.

Fill in the Blanks

Fill in the Blanks

Fill in the Blanks

Draw

Draw a representation of a binary tree using the data items: Smith, Jones, Ahmed, Lewis, Thomas, Brown

Categorize

Options (8)

Clone a tree

Count the number of leaves

Convert expression tree to prefix notation

Sort/search a binary tree

Accept traversing alphabetically

Deleting / Undo a binary tree

Stack-based programming

Convert postfix notation to expression tree

Match the examples to each of the pre/in/post order methods

pre-order

in-order

post-order

Stacks are: Last in, first out (LIFO) data structures.

Pushing: Adding data to the stack.

Popping: Taking data off the stack.

Stacks

Queues are: First in, first out (FIFO) data structures.

Queues

Fill in the Blanks

Open Ended

Explain the differences between stack and queue data structures [4 marks]

Draw

b) i) [2]

Draw

b) ii) [2]

Drag and Drop

Explain the difference between searching for an item in an ordered list compared with searching an unordered list.



When searching an ​

Placeholder

list the search can be ​

Placeholder

when an item ​

Placeholder

than the search value (or less than) is reached.

When searching an ​

Placeholder

list the search ​cannot be terminated until the ​

Placeholder

item has been reached.

Drag these tiles and drop them in the correct blank above

ordered

terminated

greater

unordered

last

first

less