c++ - 如果我们知道父子之间的连接,如何递归地将元素插入到 n 个数组树结构中?
问题描述
假设A是根,它的孩子是B,C,D,而且我们知道B有一个孩子E。我的问题是如果我们知道它们之间的连接,如何递归地插入元素而不是逐个元素地添加元素?
class Node {
public:
string key;
vector<Node*> child;
// constructor
Node(string data)
{
key = data;
}
};
//main
Node* root = new Node("A");
(root->child).push_back(new Node("B"));
(root->child).push_back(new Node("C"));
(root->child).push_back(new Node("D"));
(root->child[0]->child).push_back(new Node("E"));
解决方案
您可以在树上递归移动并在找到父节点时添加您的元素。
考虑这个函数:
bool insert(string s, string t, Node * root) { // will return true is success
if (root->key == s) { // found the parent -> insert the new node
(root->child).push_back(new Node(t));
return true;
}
bool ans = false;
for( int i =0; i< (root->child).size();i++){
ans |= insert(s, t, root->child[i]); recursive call to all the children
}
return ans;
}
现在在主要使用它时:
int main()
{
Node* root = new Node("A");
cout << "status adding B to A: " << insert("A", "B", root) << endl; // return true
cout << "status adding E to G: " << insert("G", "E", root) << endl; // return false
cout << "status adding E to B: " << insert("B", "E", root) << endl; // return true
return 0;
}
希望有帮助!
推荐阅读
- python - AttributeError:模块'numpy'没有属性'array
- mysql - MySQL server requested caching_sha2_password for a user with standard password
- php - 使用 Sendmail 驱动程序发送邮件不起作用且没有错误 Laravel 5.5
- visual-studio-code - 有没有办法在 Vscode 中美化 curl 命令?
- ruby - 如何在 ruby 中测试目录读取和寻址方法?
- c# - 通过 OpenFileDialog 打开第二个文件时,图表绘制几条线
- search - IPFS 搜索文件机制
- typescript - 使用对象文字的键作为 Typescript 类型?
- c# - 使用 EPPLUS 查找和替换所有字符串
- php - 如何使用redbeans php将数据存储在数据库中