如何在 n-way 树中获取 child？

Question

我有一个使用 std::vector 实现的 n-way 树。节点 class 仅包含指向根元素的指针，而 Link class 具有指向其自身的 std::vector 指针。我在创建 link 时为每个 link 命名，但是当我尝试使用 link 的名称在此树中定位节点时却出现分段错误。我也意识到我的函数 GetLink() 没有做任何错误检查，我尝试了几件事但他们没有工作所以如果可能的话任何关于如何在这种情况下实现它的建议都会非常有用赞赏。这是我的代码：

// in node.h
class Node {
public:
 // constructors
 // fuctions
private:
 Link *root;
};

// in link.h
class Link {
public:
//EDIT: added vector initialization in the constructor
 Link() : my_links(0) { }
 // some functions
 // EDIT: example of making the tree
 bool Load(token) {
 // parsing code based on token
   else if (strcmp (temp, "link") == 0)
   {
        Link* lnk = new Link ();
        lnk->Load (token);
        lnk->Init ();
        AddChild (lnk);
        lnk->m_parent = this;
   }
    // some more parsing code
 }
 void Link::AddChild (Link* pChild)
 {
   my_links.push_back(pChild);
 }

 Link* Link::GetLink(char* str)  // this is the function that is the problem.
 {
   if (strcmp(name, str) == 0)
   {
     return this;
   }

   for (int i=0; i < (int) my_links.size(); i++)
   {
    //Edit: added check for NULL ptr
     if (my_links[i] == NULL)
     {
        fprintf (stderr, "\n\t Couldn't find link\n\n");
        break;
     } 
     //Edit: typo corrected
     return my_links[i]->GetLink(str);
   }
 }

private:
 char name[256];
 Link* m_parent;
 std::vector<Link*> my_links;
};

// in main.cpp
static Node* node;
static Link* link;
main()
{
  char *str = "link_3";
  link = node->GetLink(str);
  printf("\n found link: %s", link->GetName());
  retrun 0;
}

编辑：将早期代码重写为 MCVE

#include <cstdio>
#include <vector>
#include <cstring>

class Link {
public:
//EDIT: added vector initialization in the constructor
 Link() : my_links(0)
 {
   m_parent = NULL;
 }

 void SetParent(Link* pParent)
 {
   m_parent = pParent;
 }

 // EDIT: example of making the tree
 bool Load(char *str)
 {
        unsigned int len;
        Link* lnk = new Link ();
        len = strlen(str);
        strcpy(name, str);
        lnk->SetParent(this);
        AddChild (lnk);
        return true;
 }

 void AddChild (Link* pChild)
 {
   my_links.push_back(pChild);
 }

 Link* GetLink(char* str)  // this is the function that is the problem.
 {
   if (strcmp(name, str) == 0)
   {
     return this;
   }

   for (int i=0; i < (int) my_links.size(); i++)
   {
    //Edit: added check for NULL ptr
     if (my_links[i] == NULL)
     {
        fprintf (stderr, "\n\t Couldn't find link\n\n");
        break;
     }
     //Edit: typo corrected
     return my_links[i]->GetLink(str);
   }
   fprintf(stderr, "\n\t Cannot get link\n\n");
   return 0;
 }

 char* GetName()
 {
   return name;
 }

private:
 char name[256];
 Link* m_parent;
 std::vector<Link*> my_links;
};


class Node {
public:
 Node()
 {
    root = NULL;
 }

 bool Load (char *str)
 {
    unsigned int len;
    root = new Link();  // here is where the error occurs
    len = strlen(str);
    strcpy(name, str);
    return true;
 }

 void AddChild (char *str)
 {
   root->Load(str);
 }

 Link* GetRoot()
 {
   return root;
 }

private:
 char name[256];
 Link *root;
};

static Node* node;
static Link* lnk;
int main()
{
  node->Load((char*)"I am root");
  node->AddChild((char*)"I am child 1");
  node->AddChild((char*)"I am child 2");
  node->AddChild((char*)"I am child 3");
  char *str = (char*)"I am child 2";
  lnk = node->GetRoot()->GetLink(str);
  printf("\n found link: %s", lnk->GetName());
  return 0;
}

错误我现在在 VS2010 的第 77 行是节点 class 中的 "root = new Link()"，Load() 函数是：

Unhandled exception at 0x012e1bbe in nWayTree.exe: 0xC0000005: Access violation writing location 0x00000100.

Answer 1

您在 MCVE 中收到错误的原因是您从未实例化 node，因此，node->Load((char*)"I am root"); 取消引用未初始化的指针，导致未定义的行为。实际上，当您的程序试图写入它期望 'root' 成员变量所在的内存位置时，您会遇到访问冲突。你可以通过写

来解决这个问题

static Node* node = new Node();

但是，即使修复了这个错误，您的 MCVE 仍然存在语义错误。每次调用 node->AddChild 时都不会添加另一个子节点，而是重命名节点并将新构造的 link （没有名称）分配给节点的 root 成员变量。此外，您的 GetLink() 函数不会递归调用 GetLink() 对所有子项（如果有的话），而只会对第一个子项调用 GetLink() 并且然后 returns 无条件地得到结果（循环最多执行一次）。

另外，Node、Link 和 root 之间的区别对我来说不是很清楚。这是我假设您想要实现的目标，使用尽可能少的附加 C++（与您的示例相比）：

#include <cstdio>
#include <vector>
#include <cstring>

class Node {
private:
    char m_name[256];
    Node* m_parent;
    std::vector<Node*> my_links;
public:
    //EDIT: added vector initialization in the constructor
    Node(const char* name, Node* parent=nullptr) : m_parent(parent), my_links() {
        strcpy(m_name, name);
    }

    void AddChild(const char* childname) {
        my_links.push_back(new Node(childname,this));
    }

    Node* GetNode(const char* str)  {
        if (strcmp(m_name, str) == 0)   {
            return this;
        }
        for (size_t i = 0; i < my_links.size(); i++) 
        { 
            Node* t = my_links[i]->GetNode(str); 
            if (t != NULL) return t; 
        } 
        return NULL; 

    }

    char* GetName() {
        return m_name;
    }
};

Node root((const char*)"I am root");

int main()
{
    root.AddChild("I am child 1");
    root.AddChild("I am child 2");
    root.AddChild("I am child 3");  
    const char *str1 = "I am child 2";
    const char *str2 = "I am child 1 of child 2 of root";
    root.GetNode(str1)->AddChild(str2);
    Node* node = root.GetNode(str2);
    if (node == NULL) {
        printf("Link not found");
    } else
    {
        printf("\n found link: %s", node->GetName());
    }
}

这是一个 "modern c++ style" 版本（并不是说它特别好）：

编辑：我刚刚意识到您使用的是 VS2010，它将无法编译以下示例，因为它使用了一些 c++11 和 c++14（当前的 c++ 标准）功能。但是，您可以使用 VS2013 的免费版本构建它，并且应该能够使用任何最新版本的 g++ 和 clang++ 构建它（您必须添加标志 '-std=c++14' 或类似标志）。

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

using namespace std;

class Node {
private:
    string m_name;
    Node* m_parent;
    vector<unique_ptr<Node>> my_links;

public: 
    Node(const string& name, Node* parent = nullptr) : 
        m_name(name),
        m_parent(parent), 
        my_links()
    {}

    void AddChild(const string& childname) {
        my_links.push_back(make_unique<Node>(childname, this));
    }

    Node* GetNode(const string& str)  {
        if (m_name == str)  {
            return this;
        } 
        for (auto& e:my_links) 
        { 
            Node* t = e->GetNode(str);
            if (t != nullptr) return t; 
        } 
        return nullptr;         
    }

    string GetName()    {
        return m_name;
    }
};

Node root("I am root");

int main()
{
    root.AddChild("I am child 1");
    root.AddChild("I am child 2");
    root.AddChild("I am child 3");
    string str1("I am child 2");
    string str2("I am child 1 of child 2 of root");
    root.GetNode(str1)->AddChild(str2);
    Node* node = root.GetNode(str2);
    if (node == nullptr) {
        cout <<"Link not found";
    } else  {
        cout << "found link: "<< node->GetName();
    }
}

如何在 n-way 树中获取 child？

How to get a child in an n-way tree?

c++

tree