Implementing Tree

[ghozan]

Hi all,

I am new to C++ especially Visual C++.
I am facing a heavy task here, so I would like to ask for some opinions.
If I want to build a tree, where each node can have unlimited number of children.
Then I can add a new node, delete a node or a subset of the tree.
And then I need to traverse the tree quickly using DFS.
Is there any way of doing this? Should I use linked list?
Please help. Thanks.

Regards,
Agus

[Ganon11]

You should use a regular set of TreeNodes, where each Node has a pointer to each of its children. Since you can have an unlimited number of children for each node, you can't use two separate variables called left and right - you will have to use some dynamic storage class like vector or linked list.

[JosAH]

You should use a regular set of TreeNodes, where each Node has a pointer to each of its children. Since you can have an unlimited number of children for each node, you can't use two separate variables called left and right - you will have to use some dynamic storage class like vector or linked list.

Alternatively you can use a node with its data in it, a pointer to its leftmost
child and a pointer to the node's sibling on the right. You could add a pointer
to its parent (quite handy to have sometimes). The node itself would be
a bit more lightweight while it still allows you to traverse the entire tree quite
efficiently.

kind regards,

Jos

[weaknessforcats]

If you are actually using C++, then why write tree code???

Use the std::map or std::multimap templates for key/value situations.

Use the std::set ot std::multiset for sets of values only.

The C++ Standard Library is designed to avoid having to code the common data structures over and over and over...

[ghozan]

class CTTreeNode //transaction tree node
{
 public:
 
  CTTreeNode();
  CTTreeNode(int s, CTTreeNode *p);
  ~CTTreeNode();
 
  int id;
  int count;
 
  set<CTTreeNode> *children;    
  CTTreeNode *parent;
 
  bool operator< (const CTTreeNode  &tn) const {return id < tn.id;}  
};
 
class CTTree  //transaction tree
{
public:
    CTTree();
    virtual ~CTTree();
    void processTransaction(Transaction *t);
 
    set<CTTreeNode> *root;    
};
 
CTTreeNode::CTTreeNode()
{
  count = 0;
  parent = 0;
  id = 0;
  children = 0;
}
 
CTTreeNode::~CTTreeNode()
{
 
}
 
CTTreeNode::CTTreeNode(int s, CTTreeNode *p)
{
    id = s;
    parent = p;
 
    count = 0; 
    children = 0;
}
 
CTTree::CTTree()
{
    root = new set<CTTreeNode>;
    CTTreeNode rootnode(0, 0);
    rootnode.children = new set<CTTreeNode>();
    root->insert(rootnode);
}
 
CTTree::~CTTree()
{
    set<CTTreeNode>::iterator it;
    for(it = root->begin(); it != root->end(); it++) {
        if(it->children != 0)
            delete it->children;
    }
    delete root;
}
 
void CTTree::processTransaction(Transaction *t)
{
    set<CTTreeNode>::iterator it;    
    set<CTTreeNode>* nodes = root->begin()->children;
    CTTreeNode *current = 0;
 
    for(int depth=0; depth < t->length; depth++) { 
            it = nodes->insert(CTTreeNode(t->t[depth], current)).first;//because insert check first
      it->count++;
      current = &(*it);
      if(it->children==0) 
          it->children = new set<CTTreeNode>;  
      nodes = it->children;
    }  
}
 
void CTTree::print(FILE* out)
{
    set<CTTreeNode>::iterator it = root->begin();
    printRecur(it, out);
}
 
void CTTree::printRecur(set<CTTreeNode>::iterator it, FILE* out)
{
    fprintf(out, "%d, %d\n", it->id, it->count);
    //cout << it->id << ", " << it->count << endl;
 
    set<CTTreeNode> *children = it->children;
    for(set<CTTreeNode>::iterator itC=children->begin(); itC != children->end(); itC++)
            printRecur(itC, out);
}
 

I have tried to implement the tree using std::set like the above definitions.
But when I tried to delete an element of the set, It gave error (the program
hang. This is the procedure which I used to traverse the tree and if a spesific
condition met the element will be removed.

void CTMmine::DeleteNodeRecur(set<CTTreeNode>::iterator it, int mSup, set<CElement> *relist)
{
    bool inRelist;
    bool child = HasChild(it);
    int tmpId = it->id;
 
    if (!child)
    {
        inRelist = FindNodeInRelist(relist, tmpId);
        if (!inRelist && (it->count<mSup))
        {
            cout << "deleted1 : " << it->id << "*, mSup : " << mSup << endl;
            fprintf(out, "deleted1 : %d*, mSup : %d\n", it->id, mSup);
            try 
            {
                m_pTransactionTree->root->erase(it);
            }
            catch (CException* e)
            {
                e->Delete();
            }
        }
    }
    else
    {
        set<CTTreeNode> *children = it->children; 
        set<CTTreeNode>::iterator itC = children->begin();
        while (itC != children->end())
        {
            cout << "delete children : " << itC->id << ", count : " << itC->count << endl;
            fprintf(out, "delete children : %d, count : %d\n", itC->id, itC->count);
            DeleteNodeRecur(itC, mSup, relist);
            itC++;
        }
        inRelist = FindNodeInRelist(relist, it->id);
        if (!inRelist && (it->count<mSup)) 
        { 
            cout << "deleted2 : " << it->id << "*, mSup : " << mSup << endl;
            fprintf(out, "deleted2 : %d*, mSup : %d\n", it->id, mSup);
            try 
            {
                m_pTransactionTree->root->erase(it);
            }
            catch (CException* e)
            {
                e->Delete();
            }
        }
    }
}
 

Is there something I have missed? Thanks.