lundi 4 juillet 2016

level Order add to n-ary tree

I am tasked with creating a level-order add to a n-ary tree specifically in this manner. Consecutive numbers should be added as children to the first empty node. for example the sequence 1, 3,4,5,8,9,10,15 should create a tree with 1 as root, 3,4,5 as children. 8,9,10 would be children of 3, 15 would be a child of 4.

If the next number is 16 it would be a child of 4 as well, if it is 17 or higher it would go to 5.

below is my non working code. It seems to be correctly doing... something when it hits an empty node or a node with consecutive numbers but then it crashes.

void levelOrderAdd (TreeNode* t,int num)
{

   // store siblings of each node in a queue so that they are
   // visited in order at the next level of the tree
   queue<TreeNode *> q;
   TreeNode *p;


   // initialize the queue by inserting the root in the queue
   q.push(t);

   // continue the iterative process until the queue is empty
   while(!q.empty())
   {

      // delete front node from queue and output the node value
      p = q.front();
      q.pop();



     // Add new Node if node is empty, or node is the next consecutive number.

      if(p->children.empty())
          {
              cout<<"true";
              p->children.push_back(new TreeNode(p,num));
              return;
          }
      else if(p->children[p->children.size()-1]->idNumber==num-1)
          {
              cout<<"hi2";
              p->children.push_back(new TreeNode(p,num));
              return;
          }


      if(!p->children.empty()){



      for (int i = 0; i < t->children.size(); ++i)
          {
          q.push(p->children[i]);   // descend

          }

      }
      //else
      //{
        //  p->children.push_back(new TreeNode(p,num));
        //  return;
      //}

   }

}

below is the code for the treenode constructor

TreeNode(TreeNode *t, int num)
{
    this->parent=t;
    this->idNumber=num;
    vector<TreeNode*> children;

}

Any ideas what's going wrong here?

Aucun commentaire:

Enregistrer un commentaire