- Trees are flexible,powerful non-linear data structure that can be used to represent data items which has hierarchical relationship
- Tree is an ideal data structure for representing hierarchical data.
- Tree can be defined as a finite set of one or more data items(ie nodes) such that
(a) There is a special node called the root of the tree
(b) The remaining nodes are partitioned in to n disjointed set of nodes each of which is a subtree.
- Example of a tree(figure 1)
- Example of a structure that is not a tree
- Each data item in a tree is called a node.
- Node specifies the data information and links to other data items
- Root is the first node in the tree
- Node A is the root node in the tree example
- Degree of a node is the number of subtrees of a node in a given tree.
- In figure1degree of node A is 3,degree of node B is 2,degree of node C is 2,degree of node D is 3 and degree of node j is 4
- The Degree of a tree is the maximum degree of node in a given tree.
- In figure1 node j has maximum degree as 4,all the other nodes have less or equal degree so the degree of the tree in figure 1 is 4
- A node with degree 0 is called a leafnode
- ie a node with no subtrees or children is called leafnode.
- In figure1 nodes L,M,N,O,H,I,P,Q,R,S,K are leaf nodes
- Any node whose degree is non-zero is called non-terminal node
- The tree is structured in different levels.
- The root node is always at level 0.Then its immediate children are at level 1and their immediate children are at level 2 and so on up to the terminal nodes
- ie If a node is at level n, then its children will be at level n+1.
- Depth of a tree is the maximum level of any node in a given tree.
- The depth of a tree in figure 1 is 4.(including level 0)