UNIT 3.
TREE
Ø
Tree – a tree is recursively defined asset of one or more node where one node
is designated as the root of the tree and all the remaining nodes can be
partitioned into non – empty set each of which is a sub-tree of the root.
OR
Ø A
tree is a collection of nodes connected by directed (or undirected) edges. A
tree is a nonlinear data structure, compared to arrays, linked
lists, stacks and queues which are linear data structures. A tree can be empty
with no nodes or a tree is a structure consisting of one node called the root and
zero or one or more sub trees. A tree has
following general properties:
- One node is distinguished as a root;
- Every node (exclude a root) is connected by a
directed edge from exactly one other node; A direction
is: parent -> children
A is a parent of B, C, D,
B is called a child of A.
on the other hand, B is a parent of E, F, K
B is called a child of A.
on the other hand, B is a parent of E, F, K
Basic properties of tree (tree terminology) –
1. Root – first node of the tree.
2. Node – each data item in a tree.
3. Degree – number of sub tree of a node.
4. Degree
of node – maximum degree of node in a
given tree.
5. Terminal
node – a node in a tree which has a
zero degree.
6. Non
terminal node – any node except root node and
whose degree is not zero.
7. Edge – line that connect node.
8. Path – sequence of consecutive edge from source to
destination.
9. Depth – maximum level of any node in a given tree from
root node to terminal node.
ü
Full binary tree – a binary tree is full if every node has 0 or 2 children. We can also
say a full binary tree is a binary tree in which all node except leaves has two
children.
Full
binary tree
A complete binary tree is a tree, which is completely filled,
with the possible exception of the bottom level, which is filled from left to
right. A complete binary tree of the height h has between 2h and
2(h+1)-1 nodes. 
Complete
binary tree