Linked List Tree

This is a discussion on Linked List Tree within the C++ Programming forums, part of the General Programming Boards category; I'm having a bit of trouble with making a "tree" representation of a linked list. That is, a root pointer ...

  1. #1
    People Love Me
    Join Date
    Jan 2003
    Posts
    412

    Linked List Tree

    I'm having a bit of trouble with making a "tree" representation of a linked list. That is, a root pointer points to two or more other pointers, and they point to 2 or more OTHER pointers, and it branches out from there. I'd prefer to do this over the "train" representation of all the pointers pointing to each other in a line, and having to traverse through the whole list to get to certain 'nodes'.

    I just don't know how to make the 'root' pointer point to MORE than one object.

    Code:
    #include <iostream>
    using namespace std;
    
    struct Animal{
           int Age;
           Animal *next;    //Pointer to the next Animal object
           
           /*Constructor that initially sets ages to 15 and new pointers to 0*/
           Animal():Age(15),next(0){cout<<"Just an animal created.\n";}
           virtual void Act(){};                //Not very important
    };
    struct Cat: public Animal{
           Cat(){cout<<"Kitty created.\n";}
           void Act(){cout<<"Meow!";};
    };
    struct Dog: public Animal{
           Dog(){cout<<"Doggy created.\n";}
           void Act(){cout<<"Woof!";};
    };
    
    int main(void){
        Animal *root = new Animal;    //Create pointer to new Animal
        root->next = new Dog;         /*Pointer in new Animal goes to a new Dog 
    (But how can I have this point to BOTH a Dog and a CAT?*/
    
        cin.get();
        return 0;
    }
    I'm not the best with linked lists...I don't really know how to create base pointers that can point to several other pointers. How's this done?

  2. #2
    Carnivore ('-'v) Hunter2's Avatar
    Join Date
    May 2002
    Posts
    2,879
    A tree is of this structure:
    Code:
    struct Node
    {
       int data1;
       char data2;
       string data3;
    
       Node* left;
       Node* right;
    };
    But how can I have this point to BOTH a Dog and a CAT?*/
    Have 2 pointers, and point one to a Dog and one to a Cat.

    Linked lists are completely different from trees. Binary trees will generally have no inbuilt mechanism by which to move from one branch to another, but can only travel down one branch to a leaf at the end. Linked lists have only one linear path to the end. The thing is, trees aren't very well suited to traversing all elements, and it is in fact relatively difficult to do so; they are much better for searching etc. Linked lists are better for do-this-to-everything-in-the-list operations.
    Just Google It. √

    (\ /)
    ( . .)
    c(")(") This is bunny. Copy and paste bunny into your signature to help him gain world domination.

  3. #3
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Make the Act() method a pure virtual function by adding =0; to the end rather than brackets.

    Write a main() function that asks the user for input, either a dog or a cat. If the user wants a dog, give 'em a dog, and vice versa.

    You can do this by declaring a linked list to be full of Animals and then filling with child classes of Animals as you please.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

  4. #4
    People Love Me
    Join Date
    Jan 2003
    Posts
    412
    Another question: is there any way to limit the amount of confusing syntax like this?

    Code:
    root->next->next->next->next->next->next->next->next->Data;
    //or.....
    root->right->left->right->left->right->left->right->left->Data;
    Last edited by Krak; 05-17-2005 at 12:01 PM.

  5. #5
    Senior Member joshdick's Avatar
    Join Date
    Nov 2002
    Location
    Phildelphia, PA
    Posts
    1,146
    Yes. Keep a pointer to the current node you're working with, and traverse the list so that all you have to do is q->Data.

    It's inadvisable to have code like you posted, because it assumes you have a certain number of elements in your linked list or tree. If you do not, you'll end up dereferencing a null pointer, causing bad things to happen.
    FAQ

    "The computer programmer is a creator of universes for which he alone is responsible. Universes of virtually unlimited complexity can be created in the form of computer programs." -- Joseph Weizenbaum.

    "If you cannot grok the overall structure of a program while taking a shower, you are not ready to code it." -- Richard Pattis.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Following CTools
    By EstateMatt in forum C Programming
    Replies: 5
    Last Post: 06-26-2008, 10:10 AM
  2. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  3. problem with structures and linked list
    By Gkitty in forum C Programming
    Replies: 6
    Last Post: 12-12-2002, 05:40 PM
  4. Template Class for Linked List
    By pecymanski in forum C++ Programming
    Replies: 2
    Last Post: 12-04-2001, 08:07 PM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21