Реализация Solid Tree C++ ntree

Question

Я знаю, что этот вопрос задан раньше, особенно на этом веб-сайте, но я видел сотни ответов, которые просто не удовлетворяли моей потребности. Приношу свои извинения за задание такого родового вопроса.

Мне нужна реализация дерева для создания возможных состояний платы для шахматной игры, которую я реализую на C++. Так вот требование:

• только один руководитель узла,
• Несколько (неизвестное количество) дочерние узлы,
• Неизвестной (динамическая) высота дерева
• Дерево не будет сбалансированным, некоторые ветви могут быть отрезаны

Вот данные, которые я хочу хранить:

// A tree's contents will only be composed of this variable 
ChessModelConstants::ChessPiece m_gameBoard[8][8]; 

typedef char PieceType, PieceColor; 

    //Variable is as follows 
    struct ChessPiece { 
    // A simple Constructor with default values 
    ChessPiece(PieceType pieceType = ChessModelConstants::TYPE_EMPTY, 
       PieceColor pieceColor = ChessModelConstants::COLOR_WHITE) : 
       m_pieceType(pieceType), m_pieceColor(pieceColor) 
    { 
    } 

    // Members 
    PieceType m_pieceType; 
    PieceColor m_pieceColor; 
}; 

Где я могу найти/реализовать такое дерево? Я бы хотел сказать, что Boost для меня сейчас не вариант. Любые STL или надежная ручная реализация сделают все возможное. Заранее спасибо.

PS: Я нашел this сайт, который я сейчас изучаю.

Answer 1

Если я правильно понял вас, вам нужно что-то вроде этого?

template<typename T> 
class TreeItem 
{ 
public: 
    TreeItem<T> (T data) 
     : m_data (data) 
    { 
    } 

    TreeItem<T> (const TreeItem& item) 
     : m_data (item.m_data) 
    { 
     m_children = item.m_children; 
    } 

    TreeItem<T>& AddChild (TreeItem<T>& item) 
    { 
     m_children.push_back (item); 
     return *m_children.rbegin(); 
    } 

    TreeItem<T>& AddChild (T data) 
    { 
     m_children.push_back (TreeItem<T>(data)); 
     return *m_children.rbegin(); 
    } 

    std::vector<TreeItem<T> >& GetChildren() 
    { 
     return m_children; 
    } 

    T& GetData() 
    { 
     return m_data; 
    } 

private: 
    T m_data; 
    std::vector<TreeItem<T> > m_children; 
}; 

// usage example 
ChessBoard emptyBoard; 

TreeItem<ChessBoard> root (emptyBoard); 
root.AddChild (emptyBoard).AddChild(emptyBoard);