Pages

Saturday 13 February 2010

Tree Data Structure


Introduction:
  • 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)
          This is a tree contains a set of nodes {A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S},with node A as a root node and the remaining nodes partitioned in to 3 disjointed sets {B,E,F,L,M,N},{C,G,H,O} and {D,I,J,K,P,Q,R,S}.Each of these sets is a tree because each satisfies the tree definition.
  • Example of a structure that is not a tree
  
              This also contains a set of nodes {A,B,C,D,G,H,I,E,F} with node A as a root node but this is not a tree because the node E is shared. so we cant subdivide the nodes in to disjointed sets.

Tree Terminologies:

Node:
  • Each data item in a tree is called a node.
  • Node specifies the data information and links to other data items
Root:
  • Root is the first node in the tree
  • Node A is the root node in the tree example
Degree of a Node:
  • 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
Degree of a Tree:
  • 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
Leaf Node (or) Terminal Node:
  • 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
Level of a 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 (or)Height of a tree:
  • 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)





  

    16 comments:

    1. its really useful 2 all

      ReplyDelete
    2. I actually don’t even know generate income wound
      up below, but I imagine this article is astonishing. I personally don’t realize what you do nonetheless certainly you
      are likely to be a popular digg, if you aren't previously.
      Here is my webpage - Treatment Of Genital Warts

      ReplyDelete
    3. Hi there colleagues, how is everything, and what you want to say about this article, in my view its truly awesome designed for me.


      Also visit my web blog ... Orgumodelleri.th9.co

      ReplyDelete
    4. With havin so muсh written content ԁo yоu ever run
      into any іssuеs of plagoriѕm or copyright infringement?
      My websіte has a lot of complеtely unique content Ι've either written myself or outsourced but it looks like a lot of it is popping it up all over the internet without my permission. Do you know any techniques to help stop content from being ripped off? I'd
      truly аppгeciate it.

      My webpage: chatroulette website utilizes

      ReplyDelete
    5. Hello There. I found your blog using msn. This is a really well written article.
      I'll make sure to bookmark it and come back to read more of your useful info. Thanks for the post. I'll certainly comeback.


      Feel free to visit my page - stourport on severn worcestershire

      ReplyDelete
    6. Hello! I cоuld haνe swoгn I've been to this website before but after browsing through some of the post I realized it's new to me.
      Anyhοw, I'm definitely glad I found it and I'll be boοkmarkіng and checκing back оften!


      My wеblοg chatroulette

      ReplyDelete
    7. Неy! Someone in my Myspace group shareԁ thiѕ ѕіte ωith us so
      I came tο look it oѵer. I'm definitely enjoying the information. I'm
      book-marking and will be tweеting this to mу followers!

      Tеrrific blog and excellent design.

      Feel fгee to visit my web-site: Tratamiento hemorroides

      ReplyDelete
    8. Keеp on worκing, great job!

      Have а lοοk аt my websіte :: just click the following website

      ReplyDelete
    9. It's not my first time to go to see this web page, i am visiting this site dailly and obtain nice information from here daily.

      Look into my webpage; http://iphoneappmarketingtips.com/forum/blog/view/284852/mineral-magnesium-citrate-given-that-laxative

      ReplyDelete
    10. Your ѕtyle is really unique cоmpaгed to other folks I haνe read stuff from.
      Τhank you for ρoѕting when you've got the opportunity, Guess I will just book mark this web site.

      My web site: omegle alternative

      ReplyDelete
    11. It's really very complex in this active life to listen news on Television, therefore I just use internet for that reason, and take the most recent news.

      Here is my web blog - emorroide

      ReplyDelete
    12. Hi there, this weekend is ρlеasant іn suppoгt of me, since thіs occasion i
      аm readіng thіs fantaѕtіc informatіѵe post here аt mу home.


      my web-site :: http://fr8Pals.com/blogs/33764/62143/obtain-absolutely-free-gay-chatr

      ReplyDelete
    13. For latest information you have to pay a visit web and on world-wide-web I found
      this website as a finest site for most up-to-date updates.


      My web site :: Find a Bungalow

      ReplyDelete