Trees/Tree traversals Flashcards
Which order do you traverse the tree with Pre Order?
Visit, Left, Right
Which order do you traverse the tree with In Order?
Left, Visit, Right
Which order do you traverse the tree with Post Order?
Left, Right, Visit
What are some real life uses of tree data structures?
- manipulating hierarchical data (such as folder structures /OS may use for file directories)
- making information easy to search (binary search trees)
- manipulating sorted lists of data
What type of graph is a tree?
A connected, undirected graph with no cycles
What is a rooted tree?
A tree that has a designated node as the root of the tree
What is the definition of a binary search tree?
A rooted tree, that has a maximum of two children per node
What is the definition of an edge?
It connects to nodes
What is the definition of the root node?
The only node that has no incoming edges
What is the definition of a child node?
The set of nodes that have the same parent
What is the definition of a parent node?
A node is a parent of all the nodes it connects with outgoing edges
What is the definition of a subtree?
- The set of nodes and edges comprised of a parent and all descendants of the parent.
- A subtree may also be a leaf
What is the definition of a leaf node?
A node that has no children
What is a binary search tree used for?
To store data that is inputted in a random order automatically
What is an advantage of using a binary search tree?
Data can be traversed easily to search and extract data
How can a binary search tree be implemented?
implement three arrays:
one for the node itself
one for the node to the left
one for the node to the right
How could we indicate there’s no child node in a space in an array?
store -1 in an empty space
Where is the dot in a pre-order traversal?
On the left
Where is the dot in a post-order traversal?
On the right
Where is the dot in a in-order traversal?
On the bottom
