Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

Tree

Posted on 1999-07-27
21
Medium Priority
?
289 Views
Last Modified: 2010-04-02
please check the site www.cs.unr.edu/~sharan/problem.html
for descrption and code
0
Comment
Question by:vicky_s
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 9
  • 7
  • 4
  • +1
21 Comments
 
LVL 7

Expert Comment

by:KangaRoo
ID: 1201138
If the search for an element results in an iterator, you can use that iterator to insert, before or after, that position using STL list::insert(iterator, const T&).
To insert after, increment the iterator.
0
 

Author Comment

by:vicky_s
ID: 1201139
Thx for the info....Thats ok! but how do U specify the iterator to traverse down the tree to the second level. My iterator works fine with the first level where it uses the list insert to operate but what if I wanna insert a node at the second level to a leaf.
I guess when U define the iterators they are just pointers to the front and back of the list so they are lmtd to that list???

0
 
LVL 2

Expert Comment

by:VEngineer
ID: 1201140
I think I have a pretty cool way to solve your problem and hopefully easy to understand too.  I'm using some mathematical fact that a TREE is a GRAPH with specific properties and a cool data structure to make this possible..  two questions I have for you:
1.  Is this a school assignment?

2.  How do you know how many children a leaf is supposed to have, or is it unrestricted?  I'm not familiar with the term mway tree.

0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:vicky_s
ID: 1201141
This is for my theisis!!! at school. The children are basically contained in the STL list so there is virtually no end to the list(as its a doubly linked list which dynamically grows). What we are doing here is that once the first level of the tree is constructed with n nodes we can make any one of the nodes as parent for the next level of tree.
For eg the root node is "R" and the nodes pointing to it are "C1,C2,C3,C4" then what we want is when  we can call the insert_after/insert_before  function ,it  searches for the desired node where we want to insert a new  node suppose it searches C3(thru iterator which is already defined in the list) and instead of growing the stl list it adds a new node  "C5" and makes "C3" its parentnode. Now we can call the "STL LIST" insert function at adds and grows the list and more childrens are born at that level(note the pointer to those children point back to their parent C3).
And so on the tree is built.
Its a bit tricky to find a leaf coz we will have to define two iterators for the tree one will be a tree_iterator that comes to the list and then we can use the list iterators to walk back and forth in the list(since we have built in iterators for the stl list)
ANY SUGGESTIONS ARE HIGHLY WELCOME THX...........
0
 
LVL 2

Expert Comment

by:VEngineer
ID: 1201142
Yeah - I think I can see a way to do it that is more intuitive... I'm also working on a thesis, so I know where you are coming from - currently, I am writing a laboratory manual for a data representation course... so this would be pretty cool.

The way I would think about it is what you have so far - define the interface for the tree.  Instead of using a list to represent the structure, I'd use two sets to make a directed graph.  First, an STL set of nodes (essentially same as tree nodes), an a STL set of edges (to represent the links between the nodes).  Of course, both nodes and edges can carry data in them.

So in your example, I'd insert root R into the node set, then insert C1, C2, C3, C4 into the node set.  Then, I'd insert edges (R, C1), (R, C2), (R, C3), (R, C4) into the edge set.  That gives you the original tree.  So if the user want to insert C5 as a child of C3, I'd insert C5 into the node set, then insert the edge (C3, C5) into the edge set.  Keeping track of parents and children is pretty easy since in-neighbors of a node are parents, and out-neighbors of a node are children.

You can then define an iterator that would then start at root R, then find all the out-neighbors of R (all the level 2 nodes) by traversing the edge set.  To find the third level nodes, you would construct a set by finding all the out-neighbors of the depth = 2 nodes.

I guess this whole concept is somewhat difficult to explain, but it is pretty novel.  Most books tell you how to represent a graph by using a matrix, which is dumb since you can't expand a matrix easily and it eats computing time and memory like crazy... this represetation of a graph is cleaner, more flexible, and closer to the definition of a graph.

I can elaborate more if you want to take this offline and onto email.  Who knows, we might be able to do some kind of partnership on our theses.
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 1201143
I still don't think everything is clear, since you still don't seem to have a policy for inserting items or traversing the list.

However, what I think you want is an iterator for your tree.

The following code illustrates this (I see why you were talking about stacks at last).  You can then implement most other functions such as insert in terms of iterators.  I use the STL find algorithm in this example to demonsttate that the code compiles OK.

The code, especially in operator++ is not perfect, but you could tidy it up as an excersise.

#include <list>
#include <stack>
#include <iostream>
#include <algorithm>

using namespace std;

#pragma warning(disable:4786)

template<class T>
struct MWayListNode {
public:
    MWayListNode(const T& value)
        : _value(value) {}
    T _value;
    list<MWayListNode<T>* > _children;
};

template <class T>
class MWayList {
public:
    MWayList(const T& value) {
        _root = new MWayListNode<T>(value); }

    bool contains(const T& value);       
    void insert(const T& value) {
        InsertNode(_root, value); }
public:
    class iterator {
    public:
        iterator(MWayListNode<T>* root = 0)
            : current(root), currentPos(0)
        {
            if (current) {
                currentPos = new list<MWayListNode<T>* >::iterator(current->_children.begin());
                currentList = &current->_children;
            }
        }

        T& operator*() {
            return current->_value;
        }

        const T& operator*() const {
            return current->_value;
        }

        iterator& operator++() {
            if (current)
            {
                // Children Exist, so iterate into the children
                if (*currentPos != currentList->end() && 
                    !current->_children.empty())
                {
                    // Increment it so we don't come back to this position
                    ++(*currentPos);
                    iteratorStack.push(currentPos);
                    listStack.push(currentList);
                    currentList = &current->_children;
                    currentPos = new list<MWayListNode<T>* >::iterator(currentList->begin());
                    current = *(currentList->begin());
                } else {
                    // There are no more children, so do we have a sibling?
                    if (*currentPos != currentList->end())
                        ++(*currentPos);

                    if (*currentPos != currentList->end())
                    {
                        // We have a sibling, so just reset the current Item
                        current = **currentPos;
                    }
                    else
                    { // No sibling
                        delete currentPos;
                        if (iteratorStack.empty()) {
                                // Stack is empty, so we are at the end
                            current = 0;
                        } else {
                                // Go back up a level
                            currentPos = iteratorStack.top();
                            currentList = listStack.top();
                            iteratorStack.pop();
                            listStack.pop();
                            ++(*this);
                        }
                    }
                }
            }
            return *this;
        }

        iterator operator++(int) {
            iterator temp = *this;
            ++*this;
            return temp;
        }

        bool operator==(const iterator& rhs) const {
            return current == rhs.current;
        }

        bool operator!=(const iterator& rhs) const {
            return current != rhs.current;
        }
    private:
        list<MWayListNode<T>* >* currentList;
        list<MWayListNode<T>* >::iterator*  currentPos;
        MWayListNode<T>* current;
        stack<list<MWayListNode<T>* >::iterator*> iteratorStack;
        stack<list<MWayListNode<T>* >*> listStack;
    };

    iterator begin() const { return iterator(_root); }
    iterator end() const { return iterator(); }
private:
    void InsertNode(MWayListNode<T>*& root, const T& value);
    MWayListNode<T>* find(MWayListNode<T>* root, const T& value);
    MWayListNode<T>* _root;
};

template <class T>
bool MWayList<T>::contains(const T& value)
{
    return find(_root,value) != 0;
}

template <class T>
MWayListNode<T>*
MWayList<T>::find(MWayListNode<T>* root, const T& value)
{
    if (root == 0 || root->_value == value)
        return root;

    list<MWayListNode<T>*>::iterator i = root->_children.begin();
    while (i != root->_children.end())
    {
        MWayListNode<T>* result = find(*i,value);
        if (result)
            return result;
        ++i;
    }
    return 0;
}

template <class T>
void
MWayList<T>::InsertNode(MWayListNode<T>*& root,
                        const T& value)
{
    if (root == 0)
    {
        root = new MWayListNode<T>(value);
    }
    else
    {
        // Just Insert in the first element of the list
        if (!root->_children.empty())
        {
            InsertNode(root->_children.front(), value);
        }
        else
        {
            MWayListNode<T>* item = new MWayListNode<T>(value);
            root->_children.push_front(item);
            item = root->_children.front();
        }
    }
}

void main()
{
    MWayList<char> ml('a');
    ml.insert('b');
    ml.insert('c');
    ml.insert('d');

    MWayList<char>::iterator i = ml.begin();
    while (i != ml.end())
    {
        cout << *i << endl;
        ++i;
    }

    MWayList<char>::iterator j = std::find(ml.begin(), ml.end(), 'c');
    cout << *j << endl;
}


0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 1201144
BTW, the iterator works on a depth first kind of algorithm.  You may want to modify this or provide alternative iterators.
0
 

Author Comment

by:vicky_s
ID: 1201145
Hey Jason thx for that info. By the way we have defined a special class for the iterators by your code that can go to the siblings of a children. But you know something we are just growing the list by your method we are not progressing to the second level of the tree. As U can see from your main function when U call the insert fn it just inserts in the list and the list grows, what if I wanna add children second generations)to node a or b .
Please check the site www.cs.unr.edu/~sharan/problem.html and follow the link for mwaytree
Thx a lot!!!!!!!!!!!!!!!!!!!!! for all your help
0
 
LVL 2

Expert Comment

by:VEngineer
ID: 1201146

Ok, I posted some code that I did.. check it out..

http://www.people.virginia.edu/~kjh7r/graph/

GRAPH, EDGE, and NODE are things I wrote before, then MWAYTREE and driver.cpp are new...  I haven't tried running it yet, but I've done something similar and it has worked.  Take a look and see if you can understand it.  The GRAPH class is not fully functional - and it's not templated right now, but that is trivial compared to the task of managing the children in this tree..


0
 
LVL 2

Expert Comment

by:VEngineer
ID: 1201147
any luck at all?
0
 

Author Comment

by:vicky_s
ID: 1201148
Hey VEnginner thx for that reply Ur methodlogy though is good for specifyin the tree but if I wanna make this tree a mway search tree I won't be able to do that.
If its possible can U post a sketch of the represented Data strcut of yours at Ur web site.
I haven't had much time to gothru the detials U sent me as I had a presentation but I REALLY!!!!!!appreciate Ur kind hlp. IT would be of great help if U can give me a sketch of the struct (did U look at my image of the tree its present at www.cs.unr.edu/~sharan/problem.html
Thx a lot!!
reply asap
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 1201149
I have enhanced the example I gave before.  If you are still interested I will post it.

The data structure seems to be a bit unpleasant in use, and I am not entirely happy with the code I have.  One of the problems is that the data structure is not entirely self-consistant because the root is a single node, whereas the rest of the structure contains lists of nodes.  It may be better to have a list of nodes at the root too.

Sorry for the delay, my web access has been down :(
0
 

Author Comment

by:vicky_s
ID: 1201150
Yes Jason please post it thx for the info alwys...
Jason can U look in the skectch of the figure I have posted at the site www.cs.unr.edu/~sharan/problem.html
Can U please add some comments to your code it helps me to understand it better.
Thx a lot I sincerely appreciate it!!
vicky_s
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 1201151
Well here it is, note there are now insert functions that add a node to the child list of a node, in the same list as a node, but after it or in the same list as a node but before it.

Note there also a PrintTree function that may help.  Hopefully the output from this is self evident, but ask if you need help.

#include <list>
#include <stack>
#include <iostream>
#include <algorithm>
#include <cassert>

using namespace std;

#pragma warning(disable:4786)

template<class T>
struct MWayListNode {
public:
    MWayListNode(const T& value)
        : _value(value) {}
    T _value;
    list<MWayListNode<T>* > _children;
};

template <class T>
class MWayList {
public:
    MWayList() {
        _root = new MWayListNode<T>(0); }

    bool contains(const T& value);       
    bool empty() { return root->_children.empty(); }
    void PrintTree() { PrintTree(_root); cout << endl;}
public:
    class iterator {
    public:
        iterator(MWayListNode<T>* root = 0)
            : currentPos(0), currentList(0), currentItem(0),
              _root(root) {
            if (_root) {
                currentPos = new list<MWayListNode<T>* >::iterator(root->_children.begin());
                currentList = &root->_children;
                ++(*this);
            }
        }

        T& operator*() {
            return currentItem->_value;
        }

        const T& operator*() const {
            return currentItem->_value;
        }


        iterator& operator++() {
            if (currentPos)
            {
                if (*currentPos == currentList->end())
                {
                    delete currentPos;
                    if (iteratorStack.empty()) {
                        // Stack is empty, so we are at the end
                        currentPos = 0;
                        currentItem = _root;
                    } else {
                        // Go back up a level
                        currentPos = iteratorStack.top();
                        currentList = listStack.top();
                        iteratorStack.pop();
                        listStack.pop();
                        currentItem = **currentPos;
                        ++(*currentPos);
                    }
                }
                        // Children Exist, so iterate into the children
                else if (!(**currentPos)->_children.empty())
                {
                    iteratorStack.push(currentPos);
                    listStack.push(currentList);
                    currentList = &(**currentPos)->_children;
                    currentPos = new list<MWayListNode<T>* >::iterator(currentList->begin());
                    ++(*this);  // continue to the bottom
                } else {
                                // There are no children, so
                                // use this item and move to the sibling
                    currentItem = **currentPos;
                    ++(*currentPos);
                }
            }
            return *this;
        }

        iterator operator++(int) {
            iterator temp = *this;
            ++*this;
            return temp;
        }

        bool operator==(const iterator& rhs) const {
            return currentPos == rhs.currentPos;
        }

        bool operator!=(const iterator& rhs) const {
            return currentPos != rhs.currentPos;
        }
    private:
        friend class MWayList<T>;
        MWayListNode<T>* GetCurrent() { return currentItem; }
        list<MWayListNode<T>* >::iterator GetListPos() {
            return *currentPos;
        }
        list<MWayListNode<T>* >& GetList() {
            return *currentList;
        }
       
        list<MWayListNode<T>* >* currentList;
        list<MWayListNode<T>* >::iterator*  currentPos;
        MWayListNode<T>* currentItem;
        MWayListNode<T>* _root;
        stack<list<MWayListNode<T>* >::iterator*> iteratorStack;
        stack<list<MWayListNode<T>* >*> listStack;
    };

    iterator begin() const { return iterator(_root); }
    iterator end() const { return iterator(); }

    void addToChildList(MWayList<T>::iterator& i, const T& value);
    void addAfter(MWayList<T>::iterator& i, const T& value);
    void addBefore(MWayList<T>::iterator& i, const T& value);
   
    iterator find(const T& value);
private:
    void PrintTree(MWayListNode<T>* root);
    MWayListNode<T>* _root;
};



template <class T>
bool MWayList<T>::contains(const T& value)
{
    return find(_root,value) != end();
}

template <class T>
MWayList<T>::iterator
MWayList<T>::find(const T& value)
{
    return std::find(begin(), end(), value);
}

// This method adds a child to a nodes child list
template <class T>
void
MWayList<T>::addToChildList(MWayList<T>::iterator& i, const T& value)
{
    i.GetCurrent()->_children.push_back(new MWayListNode<T>(value));
}

// Add a child in the same list as the current node but
// after it
template <class T>
void
MWayList<T>::addAfter(MWayList<T>::iterator& i, const T& value)
{
    list<MWayListNode<T>* >& ml = i.GetList();

    list<MWayListNode<T>* >::iterator lp = i.GetListPos();
    ml.insert(lp,new MWayListNode<T>(value));
}

// Add a child in the same list as the current node but
// before it
template <class T>
void
MWayList<T>::addBefore(MWayList<T>::iterator& i, const T& value)
{
    list<MWayListNode<T>* >& ml = i.GetList();
    list<MWayListNode<T>* >::iterator& lp = i.GetListPos();
    ml.insert(--lp, new MWayListNode<T>(value));
}

template <class T>
void
MWayList<T>::PrintTree(MWayListNode<T>* root)
{
    if (root != 0)
    {
        bool first = true;
        cout << "[";
        list<MWayListNode<T>* >::iterator i = root->_children.begin();
        while (i != root->_children.end())
        {
            if (!first)
            {
                cout << ",";
            }
            cout << (*i)->_value;      
            if (!(*i)->_children.empty())
            {
                cout << ",";
                PrintTree(*i);
            }
            first = false;
            ++i;
        }
        cout << "]";
    }
}


void main()
{
    MWayList<char> ml;
    MWayList<char>::iterator i = ml.begin();
    ml.addToChildList(i,'b');
    ml.addToChildList(i,'a');
    ml.addToChildList(i,'d');
    i = ml.find('b');
    ml.addToChildList(i,'c');
    i = ml.find('c');
    ml.addAfter(i,'e');
    i = ml.find('c');
    ml.addBefore(i,'f');
    i = ml.find('f');
    ml.addToChildList(i,'g');
    ml.PrintTree();
}

0
 

Author Comment

by:vicky_s
ID: 1201152
Jason I am relly puzzled that if U add the node to the child U grow the list not the tree. For building up the tree U will have to add nodes to the parentnode(which might be children for the root). So that were I am totally helpless. I wanna build the tree insert node function will grw the list not the tree.
Can U please let me know that detail please
Thx again for UR precious help!!!!!!!
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 1201153
No say we are at the root:

the root is a node that has:

a value and a list of children.

so we have:       (Value, NULL Child List)

to add a child, you would add an item to the child list:

       (Value, ( Value, NULL Child List) )

this would now be a tree with two levels.  Now we have choices, you can either add a sibling which would look like:

 (Value, (Value, NULL Child List, Value, NULL ChildList))

or you could have added a child to the new items child list:

(Value, (Value, (Value, NULL ChildList)))


the difference between adding a sibling and adding a child is that when you add a sibling to a node, it goes in the same list as that node, but when you add a child it goes in the nodes child list.
0
 

Author Comment

by:vicky_s
ID: 1201154
Dear jason thx for the info! I get Ur explanation, So for inserting the sibling do we  have to call the std::insert algorithm???
0
 

Author Comment

by:vicky_s
ID: 1201155
Hey jason sorry to bother U so much with this question. I went thru Ur code in detail what U r doing is that U are first building up the tree by inserting child to the rootnode. My question is suppose from Ur code as U calladdChildlist(b) what if I want to add a child at b so that b will become the parent of that child list. I guess this portion of the code is not explained,althu Ur code is simply the best!!
Thx for all Ur helps and prompts answers
Did U had a chance to go thru the sketch I have put at www.cs.unr.edu/~sharan/problem.html If U have time can U please look at that code
Thx
vicky_s
0
 
LVL 9

Expert Comment

by:jasonclarke
ID: 1201156
Yes, I did look at the picture.

if i is an iterator that points to a node.

addChildList(i, newnode) will make newnode a child of the item.

So, say you wanted to create a list that looked like:

     a
     |
     b
     |
    c d

you would do:

    MWayList<char> ml;
    MWayList<char>::iterator i = ml.begin();
    ml.addToChildList(i,'a');
    i = ml.find('a');
    ml.addToChildList(i,'b');
    i = ml.find('b');
    ml.addToChildList(i,'c');
    i = ml.find('c');
    ml.addAfter(i,'d');
    ml.PrintTree();


0
 

Author Comment

by:vicky_s
ID: 1201157
Hey jason I salute U you are really great. Thx for all your help and advisements it mattered a lot to me...

Best Regards.....
vicky_s
0
 
LVL 9

Accepted Solution

by:
jasonclarke earned 600 total points
ID: 1201158
I guess I should answer then?
0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Errors will happen. It is a fact of life for the programmer. How and when errors are detected have a great impact on quality and cost of a product. It is better to detect errors at compile time, when possible and practical. Errors that make their wa…
C++ Properties One feature missing from standard C++ that you will find in many other Object Oriented Programming languages is something called a Property (http://www.experts-exchange.com/Programming/Languages/CPP/A_3912-Object-Properties-in-C.ht…
The goal of the video will be to teach the user the difference and consequence of passing data by value vs passing data by reference in C++. An example of passing data by value as well as an example of passing data by reference will be be given. Bot…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.

670 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question