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

Question

设A为root，其子节点为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"));

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

希望对您有所帮助!