数据结构和算法 - 如何在树中添加子节点（节点）

Question

我有这个数据结构和算法练习，我想在树中添加一个子项。该函数中有一些注释解释了我需要做什么，但我无法弄清楚。另外，我需要更好地了解迭代器，这就是为什么我有点困惑。

树.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"]);
}

树.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_ */

如有任何建议，我们将不胜感激！

Answer 1

要在“Tree::addChild”方法中将子节点添加到树中，您需要将“parent”节点设置为“pos”节点的父节点，将“pos”插入“parent”节点的“children”列表中' 节点。将“pos”添加到树的整体“位置”列表中。在您的代码中，迭代器在“插入”和“擦除”等方法中使用，以指定要插入或删除节点的位置。了解如何使用迭代器向前移动 (++) 或向后移动 (--) 将帮助您导航和修改列表。