Tree Flashcards

1
Q

What is a tree

A

an abstract data type that stores elements hierarchically, not linearly

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

what is the root element?

A

an element without a parent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

what are the associations of non-root elements

A

one parent and zero or more children elements

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Formal definition of tree

A

Define tree T as a set of nodes
1) If T is nonempty, it has a special node, called the root of T , that has no parent.
2) Each node v of T different from the root has a unique parent node w; every node with parent w is a child of w.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

What is a sibling node in a tree

A

two nodes with the same parent

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

What is a leaf node

A

a node with no children

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

what is another name for a leaf node

A

external node

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

What is an edge in a tree

A

An edge of tree T is a pair of nodes (u,v) such that u is the parent of v

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

What is a path in a tree

A

A path of T is a sequence of nodes such that any two consecutive nodes in the sequence form an edge.

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

What is the depth of a position of a tree?

A

The number of ancestors of the position, excluding the position itself

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

What is the depth of the root a of tree?

A

Zero

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

Recursive algorithm to find the depth of a tree

A

If root return 0 otherwise return depth of parent + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

What is the height of a position of a tree?

A

The maximum of the depths of its leaf positions

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

What is a recursive algorithm to get the depth of the position of a tree?

A

If leaf return 0, otherwise return max of height of children + 1

How well did you know this?
1
Not at all
2
3
4
5
Perfectly