4.2.5 - FoDS (Tree) Flashcards
(12 cards)
1
Q
What is a tree
A
A connected, undirected graph with no cycles
2
Q
True or False:
A tree must have a root
A
False
3
Q
What is a cycle
A
A sequence of vertices and edges that can start and end on the same vertex
4
Q
What are 2 examples of trees
A
- Rooted trees
- Binary trees
- Binary search trees
5
Q
What is a rooted tree
A
A tree in which one vertex has been designated as a root, creating parent-child relationships between nodes
6
Q
What is a binary tree
A
A rooted tree in which each node has at most 2 children
7
Q
What is a common application of a binary tree
A
A binary search tree
8
Q
What is a root
A
A node with no parents
9
Q
What is a leaf
A
A node with no children
10
Q
What is a branch
A
An edge connecting nodes
11
Q
Explain the structure of binary trees
A
- Each node has a left and right pointer and data
- A left/right pointer is a reference to the location of the left/right child
- A pointer with no value means there is no child in either the left or the right direction
12
Q
What is the advantage of binary trees
A
Efficient sorting, searching and retrieval of data
