Implementation of adjacency table of SQLite database storage directory structure 2-construction of directory tree

Catalog

  One 、 summary

Two 、 Database storage directory structure adjacency table

3、 ... and 、 Tree building

1、 data structure

2、 Code implementation build tree

Four 、QTreeWidget Show tree

---

  One 、 summary

         Storage directory structure （ Trees ） It's a common problem , There are many solutions . The main methods are adjacency tables 、 Advanced adjacency list 、 Improved preorder tree traversal 、 recursive query 、 Enumerate paths 、 Nested sets 、 Closure table, etc .

Two 、 Database storage directory structure adjacency table

         The first and most elegant method we will try is called “ Adjacency table model ” or “ Recursive method ”. This is a good method , Because you only need a simple function to traverse your tree . In our food store , The adjacency table looks like this :

​         As you can see , In the adjacency table method , You saved the of each node “ Parent node ”. We can see ‘Pear’ yes ‘Green’ The son of , yes ‘Fruit’ My son, wait . The root node “Food” No parent value . For the sake of simplicity , I use “title” Value to identify each node . Of course , In a real database , You will use the number of each node id.

3、 ... and 、 Tree building

1、 data structure

      Recently, I want to set multiple string information in a field of the database , How to intercept one of the strings ？ Need to get the parentID This property performs the corresponding operation .

struct dirpro
{
    char type;
    char opType;
    char parentID[32];
    char rerserved[128-32-1-1];
    
};

struct DirProNode
{
    int id;
    std::string name;
    std::string parId;
    QLinkedList<DirProNode> children;
};

struct DirInfo
{
    int id;
    std::string name;
    dirpro pro;
};

2、 Code implementation build tree

DirProNode getTree()
{

   std::vector<DirInfo> vInfos =getdirproFromDb();// Read all directory information from the database 
   
   DirProNode root;// The root node 
   root.id=-1; 
   root.parId="NULL";
   root.name="root";
   int nsize=vInfos.size();
   std::map<std::string,DirProNode*> mapDirThink;
   std::vector<bool> vecMark;
   vecMark.resize(nsize);
   for(int i=0;i<nsize;++i)
   {
     vecMark[i]=false;
   }

  while(true)
  {
   int ncount=0;
    for(int i=0;i<nsize;++i)
   {  
    if(vecMark[i])
     {continue;}
     DirProNode dirproNode;
     if(convert(vInfos[i],dirproNode)
     {
       
       if(dirproNode.parId=="NULL" || dirproNode.parId.isEmpty())
       {
         root.children.push)back(dirproNode);
         mapDirThink[QString::number(dirproNode.id).c_str()]=&(root.children.back());
         ncount++;
         vecMark[i]=true;
       }
       else
       {
         mapDirThink[dirproNode.parId]->children.push_back(dirproNode);
         mapDirThink[QString::number(dirproNode.id).c_str()]=&(root.children.back());
         ncount++;
         vecMark[i]=true;
  
       }
      
     }
     else
     {
       vecMark[i]=false;
     }
     }
     if(ncount==0)
     {break;}
  }
   
    return root;
}

Four 、QTreeWidget Show tree

          With DirProNode This data structure , We can use preorder traversal to build the directory structure and QTreeWidget Intermediate display .