Graph + Tree Features Flashcards
(18 cards)
Trees
A tree is a connected form of a graph.
Node (tree)
An item in the tree
Root Node (tree)
top node in the tree
Edge/arc/branch (tree)
Connects two nodes together
Root (tree)
A single node with no incoming nodes
Child (tree)
A node with incoming edges
Parent (tree)
A node with outgoing edges
Subtree (tree)
Subsection of a tree consisting of a parent and all the children of a parent
Leaf (tree)
A node with no children
Binary Tree
Type of tree which each node has a maximum of two children.
Benefit of a binary tree
Easy to search through
Pre-order traversal
Root node, left subtree, right subtree.
outline the tree and follow it
In-order traversal
Left subtree, Root node, Right Subtree.
go as left as you can, take note, back track take note go as left
Post-order traversal
left subtree, right subtree, root node
deepest first and retreat
Graph
set of vertices/nodes connected by edges
Directed Graph
The edges can only be traversed in one direction.
Undirected Graph
The edges can be traversed in both directions.
Weighted Graph
A cost is attached to each edge.
