Flashcards
[Almost Done] Trees | Data Structures - OCR Computer Science A Level
Cards in this deck (8)
- 1What is a (Rooted) Tree?> Type of abstract data structure
> Similar to graphs, with "branches" or edges between each node
> One root note at the top, representing the top of the hierarchical structure
> Nodes at the bottom are known as leaf notes, representing the bottom of the hierarchical structure - 2What are some Examples of Trees being Used?> Hierarchical data, such as folder structures, in OSs
> Making information easy to search for (i.e.: binary trees)
> Manipulating sorted lists of data - 3Define the Following Terms used with Trees: > Node > Edge > Root > Child > Parent > Subtree > Leaf> Node - the data itself contained in the tree
> Edge - connector between two nodes
> Root - top of the hierarchy, the only node with no incoming edges
> Child - set of nodes that have incoming edges from the same node
> Parent - node with outgoing edges to children
> Subtree - set of nodes and edges comprised of a parent and all its descendants
> Leaf - a node with no children - 4What is a Binary Tree?> Rooted tree with a maximum of two children
> Usually used to search for items (when organised in such a fashion) - 5How would you Construct a Binary Search Tree?> Place the first item at the root
> For each item in the list, visit the root, and branch left or right if the value is less than or greater than the root respectively
> Continue down the branch with the same rule until a leaf node is reached
> Branch down and place the item to the left or right of the leaf node - 6What are the 3 Ways of Traversing a Binary Tree?> Pre-order traversal
> In-order traversal
> Post-order traversal
the names of which refer to whether the root of each subtree has been visited before, between, or after both branches - 7What's the Easy Way of Traversing a Binary Tree?draw lines lmao- it's that simple
> Pre-order traversal - mark the left of each node
> In-order traversal - mark the bottom of each node
> Post-order traversal - mark the right of each node
then draw an outline around the tree, starting to the left of the root node, and ending at the right of it - 8What's the Hard Way of Traversing a Binary Tree?idk lol i forgot
textbook doesn't say
Information
- Description
- A level Computer Science (Data Structures) Flashcards on [Almost Done] Trees | Data Structures - OCR Computer Science A Level, created by Malachy Moran-Tun on 11/10/2021.
- Created by
- Malachy Moran-Tun
- Views
- 2
- History
-
- Created by Malachy Moran-Tun · Oct 6, 2021
- Copied by Malachy Moran-Tun · Oct 11, 2021
- Rating