Page 104 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Unit 5: Trees

Consider the tree given in Figure 5.3: Notes

Figure 5.3

A

B C D

G H I E F

The degree of each node of the tree:
Node Degree
A 3
B 3
C 2
D 0
E 0
F 0
G 0
H 0
I 0
The degree of the tree: Maximum (Degree of all the nodes) = 3
The level of nodes of the tree:

Node Level
A 1
B 2
C 2
D 2
E 3
F 3
G 3
H 3
I 3

Task In figure 5.1 calculate the degree of a true.

5.2 Binary Tree

A binary tree is a special tree where each non-leaf node can have atmost two child nodes. Most
important types of trees which are used to model yes/no, on/off, higher/lower, i.e., binary
decisions are binary trees.
Recursive Defi nition: “A binary tree is either empty or a node that has left and right sub-trees that are
binary trees. Empty trees are represented as boxes (but we will almost always omit the boxes)”.

LOVELY PROFESSIONAL UNIVERSITY 99