Data Structures and algorithm - What to do to add a Child(node) in a Tree

Question

I have this Exercise in Data Structures and Algorithms and I want to add a child in the tree. There are some comments in the function which explain what i need to do but i cant figure it out. Also i need to have a better understanding about Iterators that's why am a bit confused.

Tree.cpp

#include "Tree.h"

PositionList::PositionList(): n(0), header(new Node), trailer(new Node) {           // constructor
    header->next = trailer;         // have them point to each other
    trailer->prev = header;
}

int PositionList::size() const          // list size
    { return n;   }

bool PositionList::empty() const            // is the list empty?
    { return (n == 0); }

void PositionList::insert(const PositionList::Iterator& p, Position* pos) {
    Node* w = p.v;              // p's node
    Node* u = w->prev;              // p's predecessor
    Node* v = new Node;             // new node to insert
    v->position = pos;
    v->next = w;  w->prev = v;          // link in v before w
    v->prev = u;  u->next = v;          // link in v after u
    n++;

}

void PositionList::insertFront(Position* pos) { // insert at front
    insert(begin(), pos);

}

void PositionList::insertBack(Position* pos)    // insert at rear
    { insert(end(), pos); }

void PositionList::erase(const Iterator& p) {   // remove p
    Node* v = p.v;              // node to remove
    Node* w = v->next;              // successor
    Node* u = v->prev;              // predecessor
    u->next = w;  w->prev = u;          // unlink p
    delete v;                   // delete this node
    n--;                    // one fewer element
}

void PositionList::eraseFront()         // remove first
    { erase(begin()); }

void PositionList::eraseBack()          // remove last
    { erase(--end()); }

PositionList::Iterator PositionList::begin() const  // begin position is first item
   { return Iterator(header->next); }

PositionList::Iterator PositionList::end() const    // end position is just beyond last
   { return Iterator(trailer); }

PositionList::Iterator::Iterator(Node* u)       // constructor from Node*
      { v = u; }

//PositionList::Iterator::Iterator()        // constructor that does nothing
//      {  }

Position::Position(Elem elem) : parent(NULL)  {
    this->elem = elem;
}

Position& PositionList::Iterator::operator*()       // reference to the position
      { return *(v->position); }

// compare positions
bool PositionList::Iterator::operator==(const Iterator& p) const
      { return v == p.v; }

bool PositionList::Iterator::operator!=(const Iterator& p) const
      { return v != p.v; }

// move to next position
PositionList::Iterator& PositionList::Iterator::operator++()
      { v = v->next; return *this; }

// move to previous position
PositionList::Iterator& PositionList::Iterator::operator--()
      { v = v->prev; return *this; }

Elem& Position::operator*() {
    return elem;
}

Position& Position::getParent() const {
    return *parent;
}


void Position::setParent(Position* pos) {
    this->parent = pos;
}

PositionList& Position::getChildren() {
    return children;
}




void Tree::addChild(Position* parent, Position* pos) {
    // add pos as a child of parent.
    // point pos's parent pointer to parent.
    // add pos to the PositionList positions of the tree.
    // TODO
}






int main() {

    map<Elem, Position*> mapWithPositions;


    mapWithPositions["/user/rt/courses"] = new Position("/user/rt/courses");

    mapWithPositions["cs016/"] = new Position("cs016/");
    mapWithPositions["cs252/"] = new Position("cs252/");

    mapWithPositions["grades8K"] = new Position("grades8K");
    mapWithPositions["homeworks/"] = new Position("homeworks/");
    mapWithPositions["programs/"] = new Position("programs/");
    mapWithPositions["projects/"] = new Position("projects/");
    mapWithPositions["grades3K"] = new Position("grades3K");

    mapWithPositions["hw1"] = new Position("hw1");
    mapWithPositions["hw2"] = new Position("hw2");
    mapWithPositions["hw3"] = new Position("hw3");
    mapWithPositions["pr1"] = new Position("pr1");
    mapWithPositions["pr2"] = new Position("pr2");
    mapWithPositions["pr3"] = new Position("pr3");
    mapWithPositions["papers/"] = new Position("papers/");
    mapWithPositions["demos/"] = new Position("demos/");

    mapWithPositions["buylow"] = new Position("buylow");
    mapWithPositions["sellhigh"] = new Position("sellhigh");
    mapWithPositions["market"] = new Position("market");

    Tree tree(mapWithPositions);

    cout << "\nPre-order: ";
    tree.preorderPrint(tree.getRoot());

    cout << "\nPost-order: ";
    tree.postorderPrint(tree.getRoot());

    cout << "\nDepth of market: " << tree.depth(*mapWithPositions["market"]);
    cout << "\nDepth of sellhigh: " << tree.depth(*mapWithPositions["sellhigh"]);
    cout << "\nDepth of hw2: " << tree.depth(*mapWithPositions["hw2"]);
}

Tree.h

#ifndef TREE_H_
#define TREE_H_

#include <iostream>
#include <string>
#include <map>
#include <stdlib.h>

using namespace std;

typedef string Elem;

class Position;

class PositionList {                // node-based list
  private:
    struct Node {               // a node of the list
          Position *position;               // element value
          Node* prev;               // previous in list
          Node* next;               // next in list
    };

  public:
    class Iterator {                // an iterator for the list
        public:
          Position& operator*();            // reference to the element
          bool operator==(const Iterator& p) const; // compare positions
          bool operator!=(const Iterator& p) const;
          Iterator& operator++();           // move to next position
          Iterator& operator--();           // move to previous position
          Position& operator->();           // get pointer
          friend class PositionList;            // give NodeList access
        private:
          Node* v;                  // pointer to the node
          Iterator(Node* u);            // create from node
          Iterator();          // does nothing
     };

  public:
    PositionList();                 // default constructor
    int size() const;               // list size
    bool empty() const;             // is the list empty?
    Iterator begin() const;         // beginning position
    Iterator end() const;           // (just beyond) last position
    void insertFront(Position* pos);        // insert at front
    void insertBack(Position* pos);     // insert at rear
    void insert(const Iterator& p, Position* pos); // insert pos before p
    void eraseFront();              // remove first
    void eraseBack();               // remove last
    void erase(const Iterator& p);      // remove p
    void printAllPositions();

  private:                  // data members
    int     n;                  // number of items
    Node*   header;             // head-of-list sentinel
    Node*   trailer;                // tail-of-list sentinel
};


class Position {                // a node position
  public:
    Position(Elem elem);
    Elem& operator*();              // get element
    Position& getParent() const;            // get parent
    void setParent(Position* pos); // set parent
    PositionList& getChildren();        // get node's children

    bool isRoot() const;            // root node?
    bool isExternal() const;            // external node?
  private:
    Elem elem;
    Position* parent;
    PositionList  children;
};

class Tree{
  public:
    //Tree();
    Tree(map<Elem,Position*>&);
    int size() const;               // number of nodes
    bool empty() const;             // is tree empty?
    Position& getRoot() const;          // get the root
    void setRoot(Position* root);
    int depth(const Position& pos) const;
    int height() const;
    void preorderPrint(Position& pos) const;
    void postorderPrint(Position& pos) const;
    void addChild(Position* parent, Position* pos);

  private:
    Position* root;
    PositionList* positions;
};



#endif /* TREE_H_ */

Any advice would be appreciated !!

Answer 1

to add a child to a tree in your 'Tree::addChild' method, you need to make the 'parent' node the parent of the 'pos' node, insert 'pos' into the 'children' list of the 'parent' node. add 'pos' to the tree's overall 'positions' list. in your code, iterators are used in methods like 'insert' and 'erase' to specify where you want to insert or remove nodes. understanding how to move forward (++) or backward (--) with iterators will help you navigate and modify the list.