Как вставить элементы в структуру массива 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;
}
Надеюсь, это поможет!
Другие решения
Других решений пока нет …