Russian Qt Forum

Привет, друзья!
На днях впервые столкнулся с необходимостью использования представления дерева.
Причём в моей задаче потребовалось имея несколько узлов первого уровня обратиться к БД, запросить и построить все вложенные узлы.
За основу класса узла я взял класс из примера Simple Tree Model Example.

C++ (Qt)
#ifndef TREENODE_H
#define TREENODE_H
 
#include <QVariant>
 
class TreeNode
{
public:
    explicit TreeNode(const QList<QVariant> &data, TreeNode *parent = nullptr);
    ~TreeNode();
 
    TreeNode *parent() const;
    int parentCount() const;
    bool hasNextBrother() const;
    TreeNode *nextBrother() const;
 
    TreeNode *child(int id) const;
    TreeNode *firstChild() const;
    TreeNode *lastChild() const;
 
    void appendChild(TreeNode* node);
    void clearChildren();
 
    int childrenCount() const;
    bool hasChildren() const;
    int columnsCount() const;
 
    QVariant data(int column) const;
    void appendData(QVariant data);
 
    int row() const;
 
private:
    TreeNode *parentNode;
    QList<QVariant> nodeData;
    QList<TreeNode*> nodeChildren;
};
 
#endif // TREENODE_H
 

C++ (Qt)
#include "treenode.h"
#include <algorithm>
 
TreeNode::TreeNode(const QList<QVariant> &data, TreeNode *parent)
    : parentNode(parent),
      nodeData(data)
{
}
 
TreeNode::~TreeNode()
{
    qDeleteAll(nodeChildren);
}
 
TreeNode *TreeNode::parent() const
{
    return parentNode;
}
 
int TreeNode::parentCount() const
{
    const TreeNode *deepNode = this;
    int result = 0;
    while(deepNode != nullptr){
        deepNode = deepNode->parent();
        ++result;
    }
    return result;
}
 
bool TreeNode::hasNextBrother() const
{
    if (parentNode == nullptr){
        return false;
    }
 
    if (this != parentNode->lastChild()){
        return true;
    }
    else{
        return false;
    }
}
 
TreeNode *TreeNode::nextBrother() const
{
    auto thisNodeIterator = std::find(parentNode->nodeChildren.begin(), parentNode->nodeChildren.end(), this);
    return *(thisNodeIterator + 1);
}
 
TreeNode *TreeNode::child(int id) const
{
    return nodeChildren[id];
}
 
TreeNode *TreeNode::firstChild() const
{
    return nodeChildren.first();
}
 
TreeNode *TreeNode::lastChild() const
{
    return nodeChildren.last();
}
 
void TreeNode::appendChild(TreeNode *node)
{
    node->parentNode = this;
    nodeChildren << node;
}
 
void TreeNode::clearChildren()
{
    qDeleteAll(nodeChildren);
    nodeChildren.clear();
}
 
int TreeNode::childrenCount() const
{
    return nodeChildren.count();
}
 
bool TreeNode::hasChildren() const
{
    return !nodeChildren.isEmpty();
}
 
int TreeNode::columnsCount() const
{
    return nodeData.count();
}
 
QVariant TreeNode::data(int column) const
{
    return nodeData[column];
}
 
void TreeNode::appendData(QVariant data)
{
    nodeData << data;
}
 
int TreeNode::row() const
{
    if (parentNode == nullptr){
        return 0;
    }
 
    return parentNode->nodeChildren.indexOf(const_cast<TreeNode*>(this));
}
 
 

Ну и сам класс-обходчик:

C++ (Qt)
#ifndef TREEWALKER_H
#define TREEWALKER_H
 
class TreeNode;
 
class TreeWalker
{
public:
    explicit TreeWalker(TreeNode* rootNode);
 
    bool next();
    TreeNode *currentNode() const;
 
private:
    bool nextChild();
    bool nextBrother();
    bool nextParent();
 
private:
    TreeNode *root;
    TreeNode *currentNode_;
};
 
#endif // TREEWALKER_H
 

C++ (Qt)
#include "treewalker.h"
#include "treenode.h"
 
TreeWalker::TreeWalker(TreeNode *rootNode)
    : root(rootNode),
      currentNode_(rootNode)
{
 
}
 
bool TreeWalker::next()
{
    return nextChild() ||
            nextBrother() ||
            nextParent();
}
 
TreeNode *TreeWalker::currentNode() const
{
    return currentNode_;
}
 
bool TreeWalker::nextChild()
{
    if(!currentNode_->hasChildren()){
        return false;
    }
 
    currentNode_ = currentNode_->firstChild();
    return true;
}
 
bool TreeWalker::nextBrother()
{
    if (!currentNode_->hasNextBrother()){
        return false;
    }
 
    currentNode_ = currentNode_->nextBrother();
    return true;
}
 
bool TreeWalker::nextParent()
{
    while(!currentNode_->hasNextBrother() && currentNode_ != root){
        currentNode_ = currentNode_->parent();
    }
 
    if (currentNode_ == root){
        return false;
    }
 
    currentNode_ = currentNode()->nextBrother();
    return true;
}
 

Пример работы класса создаёт в каждой подпапке ещё папку с содержащимся в ней итемом. После производится печать иерархии.

C++ (Qt)
#include "treenode.h"
#include "treewalker.h"
#include <iostream>
 
void initRoot(TreeNode *root){
    TreeNode *folder1 = new TreeNode({"Folder1", "Folder1Data"});
    folder1->appendChild(new TreeNode({"Folder1", "subfolder1"}));
    folder1->appendChild(new TreeNode({"Folder1", "subfolder2"}));
    folder1->appendChild(new TreeNode({"Folder1", "subfolder3"}));
 
    TreeNode *folder2 = new TreeNode({"Folder2", "Folder2Data"});
    folder2->appendChild(new TreeNode({"Folder2", "subfolder1"}));
    folder2->appendChild(new TreeNode({"Folder2", "subfolder2"}));
    folder2->appendChild(new TreeNode({"Folder2", "subfolder3"}));
 
    TreeNode *folder3 = new TreeNode({"Folder3", "Folder3Data"});
    folder3->appendChild(new TreeNode({"Folder3", "subfolder1"}));
    folder3->appendChild(new TreeNode({"Folder3", "subfolder2"}));
    folder3->appendChild(new TreeNode({"Folder3", "subfolder3"}));
 
    TreeNode *folder4 = new TreeNode({"Folder4", "Folder4Data"});
    folder4->appendChild(new TreeNode({"Folder4", "subfolder1"}));
    folder4->appendChild(new TreeNode({"Folder4", "subfolder2"}));
    folder4->appendChild(new TreeNode({"Folder4", "subfolder3"}));
 
 
    root->appendChild(folder1);
    root->appendChild(folder2);
    root->appendChild(folder3);
    root->appendChild(folder4);
}
 
void printTree(TreeNode* root){
    TreeWalker treeWalker(root);
    do{
        const TreeNode* currentNode = treeWalker.currentNode();
        const int parentCount = currentNode->parentCount();
 
        for (int i = 0; i < parentCount - 1; ++i){
            std::cout << '|';
        }
        if (parentCount != 0){
            std::cout << '+';
        }
        std::cout << currentNode->data(0).toString().toStdString()
                  << ' '
                  << currentNode->data(1).toString().toStdString()
                  << '\n';
 
    }while(treeWalker.next());
}
 
int main()
{
    TreeNode root({"Header1", "Header2"});
    initRoot(&root);
 
    TreeWalker treeWalker(&root);
 
    while(treeWalker.next()){
        const QString &description = treeWalker.currentNode()->data(1).toString();
 
        if (description.startsWith("subfolder")){
            treeWalker.currentNode()->appendChild(new TreeNode({description, "subsubfolder"}));
        }
        else if (description == "subsubfolder"){
            treeWalker.currentNode()->appendChild(new TreeNode({description, "item"}));
        }
    }
 
    printTree(&root);
    return 0;
}
 

Надеюсь не перемудрил. Код выкладываю для того, чтобы другие могли его использовать в своих проектах а также для критики.

Недавно тоже возился с деревьями, и как-то ничего готового под рукой не нашлось. Сделал так

C++ (Qt)
struct CNode {
 CNode * mParent, * mChild, * mNext;
// содержательные данные - или наоборот, данные хранят указатели на CNode
}; 
 
std::list <CNode> tree; 
 

Теперь обход всех - просто перебор std::list. Обход детей заданного нода включая cуб-детей (offsprings) - тоже итератор по std::list с условием CNode::HasGrandParent. Остальные переборы обычным while. "Корней" дерева может быть сколько угодно.