c++ - 如果我们知道父子之间的连接，如何递归地将元素插入到 n 个数组树结构中？

Question

假设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"));

Answer 1

您可以在树上递归移动并在找到父节点时添加您的元素。

考虑这个函数：

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

希望有帮助！