如果我们知道 parent 和 children 之间的联系,如何递归地将元素插入到 n 数组树结构中?
How to insert elements to n array tree structure recursively if we know connection between parent and children?
设A为根,其child人为B、C、D
我们还知道 B 有一个 child 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;
}
希望对您有所帮助!
设A为根,其child人为B、C、D 我们还知道 B 有一个 child 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;
}
希望对您有所帮助!