Russian Qt Forum
Май 23, 2024, 21:28 *
Добро пожаловать, Гость. Пожалуйста, войдите или зарегистрируйтесь.
Вам не пришло письмо с кодом активации?

Войти
 
  Начало   Форум  WIKI (Вики)FAQ Помощь Поиск Войти Регистрация  

Страниц: [1]   Вниз
  Печать  
Автор Тема: Обход дерева  (Прочитано 5121 раз)
__Heaven__
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 2130



Просмотр профиля
« : Ноябрь 24, 2015, 16:00 »

Привет, друзья!
На днях впервые столкнулся с необходимостью использования представления дерева.
Причём в моей задаче потребовалось имея несколько узлов первого уровня обратиться к БД, запросить и построить все вложенные узлы.
За основу класса узла я взял класс из примера 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;
}
 

Надеюсь не перемудрил. Код выкладываю для того, чтобы другие могли его использовать в своих проектах а также для критики.
« Последнее редактирование: Ноябрь 24, 2015, 17:45 от __Heaven__ » Записан
Igors
Джедай : наставник для всех
*******
Offline Offline

Сообщений: 11445


Просмотр профиля
« Ответ #1 : Ноябрь 25, 2015, 10:25 »

Недавно тоже возился с деревьями, и как-то ничего готового под рукой не нашлось. Сделал так
Код
C++ (Qt)
struct CNode {
CNode * mParent, * mChild, * mNext;
// содержательные данные - или наоборот, данные хранят указатели на CNode
};
 
std::list <CNode> tree;
 
Теперь обход всех - просто перебор std::list. Обход детей заданного нода включая cуб-детей (offsprings) - тоже итератор по std::list с условием CNode::HasGrandParent. Остальные переборы обычным while. "Корней" дерева может быть сколько угодно.
Записан
Страниц: [1]   Вверх
  Печать  
 
Перейти в:  


Страница сгенерирована за 0.176 секунд. Запросов: 22.