Overview
- Tree
- Degree,Leafnode
- Parent-child node
- Ancestors and Descendants
- Level number Height
Tree
- A tree is defined as a finite set of one or more data items (nodes) ,such that :
- There is a special node called the root node of the tree
- The remaining nodes are partitioned into n≥o disjoint subsets ,each of which is itself a tree, and they are called subtrees
What Is A Tree In Real World?
- A tree is a non-linear data structure ,which is used to represent hierarchical relationship existing among several data items
Degree
- The number of subtrees of a node is called its degree.
Leaf Node
- A node with degree zero is
called leaf. - The leaf nodes are also called
terminal nodes .
Parent -children
- If R is a root node and its subtrees are T1,T2,T3 and root of the subtrees are R1,R2,R3,then R1,R2,R3 are called children of R and R is called parent od R1,R2,R3
Siblings & Degree of Tree
- children of the same parent are called Siblings
- The degree of the tree is maximum degree of the nodes in the tree
Ancestors and Descendants
- The ancestors of a node are all the nodes along the path from the root to that node .
- The descendants of a node are all the nodes along the path from node to terminal node.
Level Number
- Each node is assigned a level
number. - The root node of the tree is
assigned a level number 0. - Every other node assign a
level number which is one more than the level number of its parent.
Level Number:
Generation
- Nodes with the same level number are said to belong to the same
Height or Depth
- The height or depth of a tree is the maximum number of nodes in a branch
- A line drawn from a node to its
children is called an edge - Sequence of consecutive edges is called path
- Path ending in a leaf is called a branch