Как вставить элементы в структуру массива n рекурсивно, если мы знаем связь между родителем и потомком? - PullRequest
Новая
       41

Как вставить элементы в структуру массива n рекурсивно, если мы знаем связь между родителем и потомком?

0 голосов
/ 27 ноября 2018

Дано, что 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"));

1 Ответ

0 голосов
/ 28 ноября 2018

Вы можете рекурсивно перемещаться по дереву и добавлять свой элемент, когда найдете родительский узел.

Рассмотрим эту функцию: 

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;
}

Надеюсь, что поможет!

...