Computing - Trees
AQA Computer Science 2022
Tree definitions
What is the definition of the root of a tree?
The only node that doesn’t have a parent node.
What is the definition of a subtree?
The tree formed when you think of a child as its own rooted tree.
Constructing and storing binary trees
When constructing a binary tree for strings, how should you sort the tree?
Strings alphabetically before a root should go on the left, strings after should go on the right.
To store a binary tree, what three things should you store for each node?
- The left pointer
- The right pointer
- The data itself
Tree traversal
Why is traversal best done recursively?
Any node with children can be thought of the root of a subtree.
What are the three depth-first traversal strategies?
- Pre-order
- Post-order
- In-order
What’s another way to think about post-order traversal?
A bottom-up traversal.
What’s the easy way to perform a traversal algorithm by hand?
Trace around the tree visiting dots as specified by the traversal method.
look like?
look like?
look like?
What is special about in-order traversal?
It receives the data according to its inherent sequence.
If you use in-order traversal on an alphabetically sorted tree, what is special about the result?
The nodes are visited in alphabetical order.
Array representations of trees
In a representation of a tree as three arrays, what do the three arrays represent?
- Data
- Left pointers
- Right pointers
In a representation of a tree as one array, what does the array contain?
Classes/records with data and left/right pointers attached.