trees
how does a tree organise its data
hierarchically
trees
what are the entities ina tree called
nodes
trees
nodes are connected by ….
edges
trees
each node contains a ……
value or data
trees
what are the 3 conditions a tree must be
- connected
- undirected
- no cycles
trees
describe what the following terms mean:
- root node
- parent node
- child node
- leaf node
- root node - the topmost node where it all comes from
- parent node - node that has an edge to a child node
- child node - nodes below a parent node
- leaf node - node with no children
trees
what is a binary tree
tree data structure where each node has at most two children
trees
what are the two nodes referred to as in a binary tree
left node, right node
trees
draw a binary tree for the following data:
Rose, Jasmine, George, Naomi, trever, Stanley
Rose
/ \
Jsmine Trevor
/ \ /Stanley
George Naomi
cant really do it
trees
what is a tree traversal
process that visits all the nodes in a tree
trees
give the 3 different types of traversal
- preorder - parent first, then left and right
- inorder - visit the left, then parent, then right
- postorder - visit left, right, parent
trees
whats the trick when performing a traversal
pre post
in
graphs
what is a labelled graph
graph with values on the edges
graphs
what is a labelled graph sometimes called
weighted graph
graphs
what is a directed graph
it is directed. the edges have arrows on them
graphs
explain how to create an adjacency matrix
if two vertices are connected, then a 1 is placed at the positions in the m,atrix. else its a 0
graphs
explain how to create an adjacency list
specifiy the vertices that are adjcent to each vertex
graphs
when is a list more suitable than an adjacency matrix
when the graph is sparse
