c++ - 从未知结构 C++ 构造树(非二进制)结构

Question

我需要根据传递给我的结构动态地将子节点添加到树的特定分支。例如，我有这样的结构:

  struct my_struct
  {
  int a;
  int b;
  char c;
  }

在我的函数中，移动到所需的节点后，我应该能够将子节点添加到特定节点，如下所示:

                  root
                   |
      son------daughter----another_son
       |
   a---b--c

我的树节点结构如下:

struct tree{
   string name;
   int child_count;
   int value;
   vector< tree* > child;
};

因为我想稍后更新这些变量中的每一个，所以我想为结构中的每个变量分离出节点。由于结构可以在我不知情的情况下更新，我希望逻辑与结构无关。

Answer 1

好吧，我可以建议一种方法，而不必太深入细节。我会设置类似于以下代码的内容。基本上有一个通用结构允许某种简化的内省(introspection)，通过在子结构中重新定义两个纯虚拟方法，该算法将能够将结构“树化”为子节点。最后你会发现一个树“导航”的例子。好吧，这只是一个非常简单的示例，绝不可以认为它是详尽无遗的，您会注意到它没有为更复杂的结构实现任何类型的树递归。无论如何，我不知道选择结构而不是类来处理所有这些的原因。想一想!

#include <vector>
#include <string>
#include <iostream>

// Allowed data types
enum MyTypes {
    INT,
    DOUBLE,
    NODATA
};

// Base source struct
struct MyBaseStruct {
    std::vector <std::string> ids;
    virtual MyTypes getType(std::string id) = 0;
    virtual void *getPointer(std::string id) = 0;
};

// Example of used struct
struct MyStructA: MyBaseStruct {
    int a;
    double b;
    MyStructA();
    MyTypes getType(std::string id);
    void *getPointer(std::string id);
};

MyStructA::MyStructA()
{
    ids.push_back("a");
    ids.push_back("b");
}

MyTypes MyStructA::getType(std::string id)
{
    if (id == "a")
        return INT;
    else if (id == "b")
        return DOUBLE;
    return NODATA;
}

void *MyStructA::getPointer(std::string id)
{
    if (id == "a")
        return static_cast <void *> (&a);
    else if (id == "b")
        return static_cast <void *> (&b);
    return 0;
}

struct MyTreeNode {
    std::string id;
    MyTypes type;
    void *pointer;
    std::vector <MyTreeNode *> children;
    void addChildren(MyBaseStruct &data);
};

void MyTreeNode::addChildren(MyBaseStruct &data)
{
    std::vector <std::string>::const_iterator i(data.ids.cbegin());
    while (i != data.ids.cend()) {
        MyTreeNode *newNode= new MyTreeNode;
        newNode->id= (*i);
        newNode->type= data.getType(*i);
        newNode->pointer= data.getPointer(*i);
        children.push_back(newNode);
        i++;
    }
}

int main(int /*argc*/, char * /*argv[]*/)
{
    MyStructA a;
    a.a= 1;
    a.b= 12.34;

    MyTreeNode treeRoot;
    treeRoot.id= "root of my tree";
    treeRoot.type= NODATA;
    treeRoot.pointer= 0;
    treeRoot.addChildren(a);

    // Example of tree navigation
    std::vector <MyTreeNode *>::const_iterator i(treeRoot.children.cbegin());
    while (i != treeRoot.children.cend()) {
        std::cout << (*i)->id << ": ";
        if ((*i)->pointer) {
            if ((*i)->type == INT) {
                std::cout << *(static_cast <int *> ((*i)->pointer)) << "\n";
            }
            if ((*i)->type == DOUBLE) {
                std::cout << *(static_cast <double *> ((*i)->pointer)) << "\n";
            }
        }
        i++;
    }
}

如果你有时间，你也可以考虑编写一种变体类来处理不同类型的数据，避免在多个地方强制转换你的值。