Tree構造を表現したクラス

お題

• ["親id","子id","孫id","ひ孫id",...] という可変長のidの組み合わせが複数インプットされる。
• 親のidに子のidが結びつくようにする。同じ親idの子が複数あれば、子は同じ親に結びつくようにする。

例えば、入力が、 [1,2,3] [1,4] [5,6] [1,2,7] である場合、以下のツリー構造となるように。

1--2--3
 |  `-7
 `-4
5--6

解答例

CNode.h

class CNode {
public:
    /**
     * 指定された id の Node を作る。
     */
    CNode(
        const char *id);

    virtual ~CNode();

    /**
     * Node の id を返す。
     */
    ::std::string getID();

    /**
     * 指定した childID の子Nodeが存在しなければ、子Nodeを作成し子Nodeを返す。
     * 指定した childID の子Nodeが存在していれば、既に存在する子Nodeを返す。
     */
    CNode *createChildIfNotExist(
        const char *childID);

    /**
     * 子Node の一覧を返す。
     */
    const ::std::vector<CNode *> &getChildren();

private:
    ::std::string fID;
    ::std::vector<CNode *> fChildren;
};

main.cpp

    CNode *root = new CNode("root");
    for (int i = 0; i < kNumOfIDs; i++) {
        ::std::vector< ::std::string > ids = split(kIDs[i]); // idsの要素はid "1" とか "2" とか。
        CNode *cur = root;
        for (::std::vector< ::std::string >::const_iterator itr = ids.begin(); itr != ids.end(); itr++) {
            cur = cur->createChildIfNotExist(itr->c_str());
        }
    }

入力と結果

static const char *const kIDs[] = 
{"4,3,6"
,"2,7"
,"0,1"
,"2,5"
,"0,8"
};

 $ ./a.out 
 root
   4
      3
         6
   2
      7
      5
   0
      1
      8