gpt4 book ai didi

c++ - 使用队列插入n叉树

转载 作者:行者123 更新时间:2023-11-30 05:40:06 25 4
gpt4 key购买 nike

我有一个简单的 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 调试器运行代码时,第二个 AddSkill 方法中的 while 循环不断重复。我不太确定我做错了什么或我需要实现什么概念,我们将不胜感激。

附言这是作业(不确定合适的标签是什么)。

更新:我尝试使用 Queue 实现重载的 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]);
}
}
}
}

技能等级

#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 实现中注释掉一段代码,我不会收到任何错误。

最佳答案

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

在第二个AddSkill()您打算将新节点作为父技能的子节点插入。方法似乎是:

  • 检查树中至少有一个节点(初始if)
  • 遍历树找到父节点(while 循环)
  • 如果找到父级,则找到第一个空的子级以插入新技能(内部 for 循环)

有什么问题?

你的算法有几个缺陷:

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

如何解决?

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

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

这里有一些代码(抱歉,我用 char* 替换了 string 并使用了 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使用共享指针而不是原始指针。

关于c++ - 使用队列插入n叉树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31909338/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com