使用队列插入n叉树

Question

我有一个简单的 n 元（最多 3 个子节点），其中插入的第一个节点将是根节点。之前，我添加任何其他节点，如果满足条件，我必须搜索树并从先前插入的节点作为子节点插入。我的插入方法对于第一次插入和后续插入都超载了。

我能够使用此方法插入第一个节点：

void Tree::AddSkill(char* name, char* desc, int level)
{
    Skill s(name, desc, level);
    Node * newNode = new Node(s);
    //newNode->aSkill = Skill(name, desc, level);

    newNode->parent = NULL;
    for (int i = 0; i<CHILD_MAX; i++)
    {
        newNode->children[i] = NULL;
    }

    if (this->root == NULL)
    {
        this->root = newNode;
    }
    else
    {
        this->root->parent = newNode;
        newNode->children[0] = this->root;
        this->root = newNode;
    }
}

我在随后插入到树中时遇到了一些问题，这是我到目前为止的代码：

void Tree::AddSkill(char* name, char* desc, int level, char* parentName)
{
    if (this->root == NULL)
    {
        cout << "Error: no nodes in tree.\n";
        return;
    }

    Node* node = NULL;
    Skill s(name, desc, level);
    Node * child = new Node(s);
    while (root != NULL)
    {
        if (strcmp(child->aSkill.GetName(), parentName) == 0)
        {
            for (int i = 0; i < CHILD_MAX; i++)
            {
                if (node->children[i] == NULL)
                {
                    child->aSkill = s;
                    child->parent = node;
                    node->children[i] = child;
                    return;
                }
            }
        }
    }
}

当我通过 VS Debugger 运行代码时，第二个 AddSkill 方法中的 while 循环无限重复。我不太确定我做错了什么或我需要实施什么概念，我们将不胜感激。

P.S。这是作业（不确定合适的标签是什么）。

更新：我尝试使用队列实现重载 AddSkill()。这是我尝试过的。

void SkillTree::AddSkill(char* name, char* desc, int level, char* parentName)
{
    if (this->root == NULL)
    {
        cout << "Error: no nodes in tree.\n";
        return;
    }  
    queue<Node*> q;
    q.push(this->root);
    while (!q.empty())
    {
        Node * n = q.front();
        q.pop();    
        if (strcmp(n->aSkill.GetName(), parentName) == 0)
        {
            for (int i = 0; i<CHILD_MAX; i++)
            {
                if (n->children[i] == NULL)
                {
                    Skill s(name, desc, level);
                    Node * child = new Node(s);
                    //When I comment out the next 3 lines, program does not crash. Not sure what the problem is here.
                    child->aSkill = s;
                    child->parent = n;
                    n->children[i] = child;
                    return;
                }
            }
            return;
        }
        for (int i = 0; i<CHILD_MAX; i++)
        {
            if (n->children[i] != NULL)
            {
                q.push(n->children[i]);
            }
        }
    }
}

技能Class

#include <iostream>
#include "Skill.h"
Skill::Skill()
{
    name = NULL;
    desc = NULL;
    level = 0;
}

Skill::Skill(char* name, char* desc, int level) : level(level), name(new char[strlen(name) + 1]), desc(new char[strlen(desc) + 1])
{
    strcpy_s(this->name, (strlen(name) + 1), name);
    strcpy_s(this->desc, (strlen(desc) + 1), desc);
}

Skill::Skill(const Skill& aSkill)
{
    this->name = new char[strlen(aSkill.name) + 1];
    strcpy_s(this->name, (strlen(aSkill.name) + 1), aSkill.name);

    this->level = aSkill.level;

    this->desc = new char[strlen(aSkill.desc) + 1];
    strcpy_s(this->desc, (strlen(aSkill.desc) + 1), aSkill.desc);
}

Skill& Skill::operator=(const Skill& aSkill)
{
    if (this == &aSkill)
        return *this;
    else
    {
        delete[] name;
        delete[] desc;

        name = new char[strlen(aSkill.name) + 1];
        strcpy_s(name, (strlen(aSkill.name) + 1), aSkill.name);

        desc = new char[strlen(aSkill.desc) + 1];
        strcpy_s(name, (strlen(aSkill.desc) + 1), aSkill.desc);

        level = aSkill.level;

        return *this;
    }
}

Skill::~Skill()
{
    delete[] name;
    delete[] desc;
}

char* Skill::GetName() const
{
    return name;
}
char* Skill::GetDesc() const
{
    return desc;
}
int Skill::GetLevel() const
{
    return level;
}

void Skill::Display(ostream& out)
{
    out << "- " << GetName() << " -- " << GetDesc() << " [Lvl: " << GetLevel() << "]\n";
}

节点：

    Skill aSkill;
    Node* parent;
    Node* children[CHILD_MAX];
    Node() : parent(NULL)
    {
        for (int i = 0; i < CHILD_MAX; i++)
        {
            children[i] = NULL;
        }
    };

    Node(const Skill& n) : aSkill(n), parent(NULL)
    {
        for (int i = 0; i < CHILD_MAX; i++)
        {
            children[i] = NULL;
        }
    };

这里摘自main()

SkillTree student("Student");
    student.Display(cout);

    student.AddSkill("Alphabet","Mastery of letters and sounds",0);
    student.Display(cout);

    student.AddSkill("Reading","The ability to read all manner of written material",1,"Alphabet");
    student.AddSkill("Writing","The ability to put your thoughts on paper",1,"Alphabet");
    student.Display(cout); 
student.AddSkill("Speed Reading Level 1","Read any text twice as fast as normal",5,"Reading");
student.AddSkill("Speed Reading Level 2","Read any text four times as fast as normal",10,"Speed Reading Level 1");
student.AddSkill("Memorization","Memorize average sized texts",10,"Reading");
student.AddSkill("Massive Memorization","Memorize large sized texts",20,"Memorization");
student.AddSkill("Spell Writing","The ability to write spells",5,"Writing");
student.AddSkill("History","The ability to write (and rewrite) history",10,"Writing");
student.AddSkill("Written Creation","The ability to write things into reality",20,"History");
student.Display(cout);

student.Display(cout);调用的两个函数如下

    void Tree::Display(ostream& out)
{
    out << "Skill Tree: " << title << "\n";
    if (this->root == NULL)
    {
        cout << "Empty\n";
        return;
    }
    else
        Display_r(out, this->root, 1);
}

void Tree::Display_r(ostream& out, Node* n, int depth)
{
    for (int i = 0; i<depth; i++)
    {
        out << "  ";
    }
    n->aSkill.Display(out);

    for (int i = 0; i<CHILD_MAX; i++)
    {
        if (n->children[i] != NULL)
        {
            Display_r(out, n->children[i], depth + 1);
        }
    }
}

如果我在 AddSkill() 的 Queue 实现中注释掉一段代码，我不会出错。

Answer 1

在第一个 AddSkill() 中，您将新节点插入树的顶部，使其成为新的根。

在第二个 AddSkill() 中，您打算将新节点作为 parent 技能的 child 插入。方法似乎是：

检查树中至少有一个节点（初始if）
遍历树找到父节点（while循环）
如果找到parent，找到第一个空的child插入新技能（内for循环）

有什么问题？

你的算法有几个缺陷：

你循环 root 不为空。由于此处的树不为空，并且您未删除任何节点，因此此条件将保持为真，从而允许无限循环。
然后检查新 child 的名称是否与 parent 名称相对应。我认为在大多数情况下这将是错误的（否则您将需要一个参数）。所以这将确保循环是无限的。
之后你假设node是当前节点，你将新的child插入到node的children中。此代码未执行。幸运的是：这将是未定义的行为，因为您已将 node 设置为 NULL 并且从未更改此值。

如何解决？

要正确执行此操作，您必须从 root 处的 node 开始，然后检查节点名称是否与 parentname 匹配，如果是，则插入 child 和你一样。

但是还有最后一个问题。比较重要的一个。您的算法结构适用于链表遍历，但不适用于 tree traversal。树遍历算法需要 stack/list 来跟踪所有要探索的分支，或者需要递归方法。

这里是一些代码（抱歉，我用 string 替换了 char* 并使用了 vector<Node*> 而不是 Node*[] )，使用 AddSkill() 的辅助重载来执行递归搜索：

// replaces the former one that you had
void Tree::AddSkill(string name, string  desc, int level, string parentName)
{
    if (root == NULL)
    {
        cout << "Error: no nodes in tree.\n";
        return;
    }
    Skill s(name, desc, level);
    AddSkill(root, s, parentName); 
}

// auxiliary helper
void Tree::AddSkill(Node*node, Skill& s, string& parentName)
{
    if (node->sk.name == parentName) {  // if found, add the new node as childen
        Node * child = new Node(s);
        child->parent = node;
        node->children.push_back(child);
    }
    else {
        for (auto &x : node->children)   // for all the children 
            AddSkill(x, s, parentName);  // search recursively   
    }
}

这里 online demo 使用共享指针而不是原始指针。

使用队列插入n叉树

Insert into n-ary tree using Queue

c++

tree

data-structures