Tree Data Structure - I

-

Trees



  1. The data is organised in a hierarchial manner.
  2. Terminology:
    1. Node
    2. Edges
    3. Parent Node
    4. Child Node
    5. Leaf Node
    6. Level
    7. Height
    8. Siblings
    9. Path
      There exists only one path between any two nodes
    10. Ancestor: Any node z is ancestor of x if z lies in the path between root node and x
    11. Descedant: Nodes which are not ancestors to x are the descendant to x.
    12. Subtree: The root of subtree is usually used to name that subtree
    13. Degree
    14. Forest
  3. Definition of a tree
  4. Binary Tree
    An empty tree can be a binary tree
  5. Similar trees: If same struture
  6. Copies: Same struccture and same contents
  7. Properties:
    1. Max no of nodes on any level x is 2x
    2. Max no of nodes in a tree with a heoght h is 2h-1
    3. The minimum number of nodes possible in a binary tree of height h is h.
    4. If a binary tree contains n nodes, then its maximum heoght possible is log2(n+1)
    5. Total number of nodes= total no of edges+1
  8. Strictly Binary Tree:
    Degree is either 0 or 2
    Properties:
    1. A strictly binary tree with n non leaf nodes has (n+1) leaf nodes.
    2. A strictly binary tree with n leaf nodes has 2n-2 nodes( n leaf nodes + n-1 non leaf nodes)
  9. Extended Binary Tree: In a binary tree, each empty subtree is replaced by a special node i.e.., adding special nodes to leaf nodes and nodes with a single child.
  10. The trees which a minimum number of nodes are called skew trees.

Comments

Post a Comment

Popular

Traversal In A Binary Tree - Tree -3

-
Image
Traversal In Binary Tree Traversing a binary tree means visiting each node of the tree exactly once. At each node : N : Visit the node L : Traverse its left subtree R : Traverse its right subtree These actions can be performed in any order... (3! = 6 different ways of ordering the three tasks.) Different orders: NRL NLR LNR LRN RNL RLN But we follow the convention which states left subtree to be traversed before right sub tree. Thus we are left with three orders: NLR , LNR and LRN The orders are named according the position of the node i.e., position of N in the order. pre : NLR in  : LNR post : LRN PRE ORDER TRAVERSAL: ( NLR ) N : Visit the node L : Traverse the left subtree R : Traverse the right subtree IN ORDER TRAVERSAL: ( LNR ) L : Traverse the left subtree N : Visit the node R : Traverse the right subtree ...
Read more

Tree data structure - 2

-
Image
Trees - 2 Types: Strictly binary tree: Degree is every node either 0 or 2. Full Binary tree: Degree of every node is 2. Complete Binary Tree:A binary tree in which every level , exccept possibly the last , is completely filled and all nodes are as far left as possible. Array Representation of binary tree: Also called as sequential representation or linear representation We use 1D array Store the data with indexed 1 i.e., root node at Array[1](Even we can use 0 based index ) If a node is at index k in the array, its left child is at index 2k and right child at index 2k+1. If a node at index k then its parent is at index floor(k/2) The size of array needed to store a tree of height h is 2 h -1 Linked list representation : struct node { struct node *left; struct node *right; int data; } This structure can be used for the binary tree. Self referential structure where first and second...
Read more

Pre Order Traversal In Binary Tree

-
Image
Pre Order Traversal In Binary Tree Its NLR ordered traversal. The order goes this way: N: visit the node L: Traverse the left sub tree. R: Traverse the right sub tree. Lets check with an example. Consider the following example. Visit the node 1 Traverse the left sub tree of node 1 Visit the node 2 Traverse the left sub tree of node 2 Visit the node 4 Traverse the right sub tree of node 2 Visit the node 5 Traverse the right sub tree of node 1 Visit the node 3 Traverse the left subtree of node 3 Visit the node 6 Traverse the right sub tree of node 3 Visit the node 7 On completing the traversal we get the pre order if we follow the bolded nodes. Pre Order: 1 , 2 , 4 , 5 , 3 , 6 , 7
Read more