4.2.5 Trees

Question 1

Define Trees.

Answer 1

A data structure that uses a set of linked nodes to form a hierarchical structure starting at a root node.
Each node is a child/sub-node of a parent node.

Question 2

What describes a tree?

Answer 2

• a connected, undirected graph with no cycles.
• only one possible path between any two nodes

Question 3

What does connected mean in terms of trees?

Answer 3

It means that there is a path from any node, and there is no node, or set of nodes that is disconnected from the others.

Question 4

What is a cycle in terms of trees?

Answer 4

A cycle is where a number of vertices (at least 3) are connected in a closed chain.

Question 5

What is the root node?

Answer 5

The only node in a rooted tree without a parent node.
If the tree has a root, it is a rooted tree.

Question 6

What are the parts of a tree?

Answer 6

Branch - a path from the root to an end point
Leaf node - a node where no branches are branching from that node. Found at the bottom of the tree.

Edges = nodes - 1

Question 7

What are the parts of a rooted tree?

Answer 7

A tree with one node that has been designated as the root.
The root is the only node with no parent, and all the other nodes are descendants of the root.

Question 8

What are some examples of rooted trees?

Answer 8

• stores data that has an inherent hierarchical structure
• an OS may use tree for directories, files and folders in its file management system.

Question 9

What is a Binary Tree?

Answer 9

A rooted tree where every node has at most 2 child nodes.

Question 10

How is a binary tree ordered?

Answer 10

In ascending order, left subtree have values lower than the root, nodes of the right subtree have values that are higher than the root.

Question 11

What are uses of binary trees?

Answer 11

• binary search tree
• used in compilers to build syntax trees
• speed up searching
• express algebraic and Boolean expressions