The greatest mistake you can make in life is to be continually fearing you will make one

Saturday, 20 February 2010

Binay Tree

  • A binary tree is a tree in which no node can have more than two children.These children are described as left child and right child of the parent node.
  • A binary tree T is defined as a finite set of nodes such that

    1. T is empty (ie) T has no nodes called the null tree or empty tree.
    2. There is a specially designated node called the root of the tree, and the remaining nodes are partitioned in to two disjointed sets T1 and T2,each of which is a binary tree.T1 is called the left subtree and T2 is called the right subtree.
  • Example of a binary tree is shown in figure 1

  • In the above binary tree A is the root node of the binar tree.B is the left child of A and C is the right child of A. So A is the parent node of B and C. B and C are the children of A.
  • If a node has no child then its called a leaf node. In the above example nodes D,H,I,F,J are leaf nodes
  • For a binary tree the maximum number of nodes at level i will be 2i considering root node is at level 0.
  • If K is the depth of the tree then the maximum number of nodes that the tree can have is 2K-1
Strictly binary tree:
  • The tree is said to be strictly binary tree, if every non-leaf node in a binary tree has non-empty left and right sub trees
  • (ie) every node in the strictly binary tree contains either no children or 2 children.
  • figure 1 is not a strictly binary tree because node G has only one child
  • A strictly binary tree with n leaves always contains 2n-1 nodes. The strictly binary tree in the below figure has 5 leaves such as D,E,F,H,I. here the tree has 2*5-1 ie 9 nodes.The tree contains 9 nodes only.So in strictly binary tree given the number of leaves we can easily find the totla number of nodes in the tree.
  • Strictly binary tree is also called 2-tree or extended binary tree.

    • The main application of a 2-tree is to represent any algebraic expression such as [E=(a+b)/((c-d)*e)]using binary operation.

    No comments:

    Post a Comment