IT博客汇 | 247 - 问，数据库表中的平面结构如何转化为程序中的树形数据结构

247 - 问，数据库表中的平面结构如何转化为程序中的树形数据结构

鸠摩智(everettjf)发表于 2013-01-10 14:58:00

为了实现部门的无限分级需求，一般数据库中的设计如下：

id, parent_id, name

现在，程序中要一次全部展示出这棵部门树。

就是说如何将数据库中平铺开的记录，组合成树。

不知为啥网上也没找到什么资料，或许是我关键词不对，或许是问题太简单了？

考虑了下，使用multimap作为中间辅助转换的容器比较简单。

不知道大家有没有其他做法。

环境：vc++2012 pro

代码如下：

#include "stdafx.h"
#include
#include <string>
#include
#include
#include
#include
#include

using namespace std;

/*
test data below:
tree database(id,parent_id,name):
+a ida,0,a
+c idc,ida,c
+f idf,idc,f
+g idg,idc,g
+d idd,ida,d
+b idb,0,b
+e ide,idb,e
*/

// database row entity
struct DBDepartmentRow
{
string id;
string parent_id;
string name;
DBDepartmentRow(){}
DBDepartmentRow(const string & i,const string & p,const string & n):id(i),parent_id(p),name(n){}
};
typedef shared_ptr DBDepartmentRowPtr;
typedef list DBDepartmentRowPtrList;

class DBDepartmentMock
{
public:
static void SelectAllRows(DBDepartmentRowPtrList & rows)
{
// 假设这里通过数据库获取出的多条记录
rows.push_back(make_shared("ida","0","a"));
rows.push_back(make_shared("idc","ida","c"));
rows.push_back(make_shared("idf","idc","f"));
rows.push_back(make_shared("idg","idc","g"));
rows.push_back(make_shared("idd","ida","d"));
rows.push_back(make_shared("idb","0","b"));
rows.push_back(make_shared("ide","idb","e"));
}
};

///////////////////////////////////////////////////////////////////////
// tree node
struct DepartmentNode;
typedef shared_ptr DepartmentNodePtr;
typedef list DepartmentNodePtrList;
struct DepartmentNode
{
DBDepartmentRow node_data;
DepartmentNodePtrList children;
};

///////////////////////////////////////////////////////////////////////
class DepartmentTreeBuilder
{
public:
static void Convert(const DBDepartmentRowPtrList & rows,DepartmentNodePtr & node)
{
unordered_multimap<string/*parent_id*/,DBDepartmentRowPtr> temp_container;
for(auto iter = rows.begin();iter != rows.end();++iter)
{
temp_container.insert(make_pair((*iter)->parent_id,*iter));
}

stack checking_children;

// the first element is root
node->node_data.id = "0";// for root node
checking_children.push(node);

while(! checking_children.empty())
{
DepartmentNodePtr checking_node = checking_children.top();
checking_children.pop();

// fill children
auto range = temp_container.equal_range(checking_node->node_data.id);
for(auto iter = range.first; iter != range.second; ++iter)
{
DepartmentNodePtr child = make_shared();
child->node_data.id = iter->second->id;
child->node_data.parent_id = iter->second->parent_id;
child->node_data.name = iter->second->name;

checking_node->children.push_back(child);
checking_children.push(child);
}
}
}
};

void PrintDepartmentNode(const DepartmentNode & node)
{
static int level = 0;
++level;

for(int i = 0;i < level;++i)
cout << "-";

cout << node.node_data.id
<< "/" << node.node_data.parent_id
<< "/" << node.node_data.name
<< endl;

for(auto iter = node.children.begin();iter != node.children.end();++iter)
{
PrintDepartmentNode(*(*iter));
}

--level;
}

int _tmain(int argc, _TCHAR* argv[])
{
// select from database
DBDepartmentRowPtrList rows;
DBDepartmentMock::SelectAllRows(rows);

// convert to tree
DepartmentNodePtr node = make_shared();
DepartmentTreeBuilder::Convert(rows,node);

// print
PrintDepartmentNode(*node);

return 0;
}

代码下载

鸠摩智(everettjf) 2013-01-10 22:58 发表评论