DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Results 1 to 7 of 7

Thread: code for Binary tree using linked list

  1. #1
    Join Date
    Nov 2006
    Posts
    4

    code for Binary tree using linked list

    Hi,
    I want to have code of implementing simple Binary tree using linked list in C or C++ language.

  2. #2
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    should be lots to look at in books and on the web ... but how about you coming up with it yourself? You need to keep track of pointers/reference to three nodes (parent, two children). What methods do you need?

  3. #3
    Join Date
    Dec 2003
    Posts
    3,366
    what does that mean? you want to implement a tree INTO a list (this is normally done into an array instead, for massive performance gains) ? Or you just want to make a tree, which is somewhat like a linked list? The former is going to be one slow, worthless data structure, but its doable of course.

  4. #4
    Join Date
    Nov 2006
    Posts
    4
    Quote Originally Posted by jonnin
    what does that mean? you want to implement a tree INTO a list (this is normally done into an array instead, for massive performance gains) ? Or you just want to make a tree, which is somewhat like a linked list? The former is going to be one slow, worthless data structure, but its doable of course.
    Hi Jonnin,
    Actually I read in a book that we can implement Simple Binary Tree using linked list.whatever is the basic method please tell me.Or we have to do it explicitly that is we have to explicitly keep track of the parent and children .Whatever is the method please tell me.

  5. #5
    Join Date
    Dec 2004
    Location
    San Bernardino County, California
    Posts
    1,468
    jonnin's point is that it is far easier to implement a binary tree backed by an array - if it is a 0 based array, the children are at 2i+1 and 2i+2, where i is the index of the parent. Very fast storage for a search tree, heap, red-black tree, or other binary tree. Now, if you have been asked/assigned/just want to implement it using a linked list, that's a different matter.

  6. #6
    Join Date
    Nov 2006
    Posts
    4
    Quote Originally Posted by nspils
    jonnin's point is that it is far easier to implement a binary tree backed by an array - if it is a 0 based array, the children are at 2i+1 and 2i+2, where i is the index of the parent. Very fast storage for a search tree, heap, red-black tree, or other binary tree. Now, if you have been asked/assigned/just want to implement it using a linked list, that's a different matter.
    Hi,
    All right .so please send me the code to implement Binary tree by using Arrays.

  7. #7
    Join Date
    Dec 2003
    Posts
    3,366
    what he said, you just make a large array & instead of a pointer in your tree "node" you have an array index (integer) using the formula root = zero, child = parent index *2+left or parent index * 2 + right where left == 1 and right == 2. All the other code is exactly the same for your tree.

    You can do the exact same thing with a vector, valarray, linked list or any other container. But for something like a linked list, where you have to start at the top and seek each item iteratively, its "worthless". Vector or valarray would be fine but they are slightly less efficient than the pure array, normal programs would not notice the performance hit, real-time code might.

Similar Threads

  1. C++ linked list project
    By boyracer87 in forum C++
    Replies: 0
    Last Post: 05-08-2006, 09:13 AM
  2. Require code for shuffling a list
    By ray in forum C++
    Replies: 3
    Last Post: 02-03-2006, 08:24 AM
  3. Java Doubly Circular Linked List
    By xsouldeath in forum Java
    Replies: 1
    Last Post: 11-28-2005, 12:19 AM
  4. .NET equals Efficiency
    By Kevin in forum .NET
    Replies: 150
    Last Post: 03-04-2002, 06:40 PM
  5. Good Editorial by Russell Jones
    By Robert G in forum .NET
    Replies: 84
    Last Post: 02-08-2001, 03:38 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center