Section 7 Chapter 42 - Trees

Question 1

Tree

Answer 1

Connected, undirected graph with no cycles

Question 2

Rooted tree

Answer 2

A tree where one vertex has been designated as the root

Question 3

Node

Answer 3

Contains the data and are connected together via edges

Question 4

Edge

Answer 4

Connects two nodes

Question 5

Root

Answer 5

The only node with no parent. All other nodes are descendants of the root

Question 6

Child

Answer 6

node A is a child of node B is they have a direct connection and node B is closer to the root than node A.

Question 7

Parent

Answer 7

Node A is a parent of node B if they are directly connected and node A is closer to the root

Question 8

Subtree

Answer 8

The set of nodes and edges comprised of a parent and its descendants

Question 9

Leaf

Answer 9

A node that has no children

Question 10

Binary tree

Answer 10

A rooted tree where each node has at most two children

Question 11

Binary search tree

Answer 11

A binary tree that holds the items in such a way that a binary search can be conducted on the tree very easily

Question 12

How to construct a binary search tree

Answer 12

The first item is placed at the root. When a new item is added visit the root, which becomes the current node. At each current node, if the item is less than the value of the node take the branch to the left, otherwise take the branch to the right. Repeat until you attempt to take a branch that does not exist. Add the item as a node in this place

Question 13

The ways to traverse a binary tree (3)

Answer 13

Pre-order
In-order
Post-order

Question 14

How to know what each traversal means

Answer 14

The prefix of each traversals refers to how whether, at each subtree, you consider the parent node first, second or third.

Question 15

Uses for each traversal

Answer 15

Pre-order - producing prefix notation
In-order - binary search
Post-order - produce reverse polish notation