33860363
Description
Flashcards by Malachy Moran-Tun, updated more than 1 year ago
More
| Question | Answer |
| What 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 |
| What 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 |
| Define 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 |
| What is a Binary Tree? | > Rooted tree with a maximum of two children > Usually used to search for items (when organised in such a fashion) |
| How 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 |
| What 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 |
| What'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 |
| What's the Hard Way of Traversing a Binary Tree? | idk lol i forgot textbook doesn't say |
Want to create your own Flashcards for free with GoConqr? Learn more.