C++：二叉樹 - 從親代載體

Question

刪除我的孩子有這樣的結構：

#include <stddef.h> 
#include <vector> 

typedef int T; 
class tree; 

class node { 
    T info; 
    std::vector<node*> children; 
    friend class tree; 
public: 
    typedef std::vector<node*>::iterator iterator; 
    iterator begin() { 
     return children.begin(); 
    } 
    iterator end() { 
     return children.end(); 
    } 
    T get() { 
     return info; 
    } 
}; 

class tree { 
    node* r; 
    void del(node* v) { 
     if (v == NULL) return; 
     for (node::iterator it = v->begin(); it != v->end(); ++it)  
      del(*it); 
     delete v; 
    } 
public: 
    tree() : r(NULL) { } 
    node* add(T info, node* parent) { 
     node* v = new node; 
     v->info = info; 
     if (parent != NULL) parent->children.push_back(v); 
     else { 
      if (r != NULL) del(r); 
      r = v; 
     } 
     return v; 
    } 
node* add(T info) { 

     return add(info, NULL); 
    } 
    node* root() { return r; } 
    void remove(node* v) { 
     if (r == v) r = NULL; 
     else { /* remove v from the list of children of its parent */ } 
     del(v); 
    } 
}; 

我需要完成的功能從其父母的列表中刪除節點v卸下。爲了有效地這樣做，我會向節點類添加一個指向其父節點的指針，並相應地更新添加函數。 這是我的解決方案 我修改與增加功能：

node* add(T info, node* parent) { 
    node* v = new node; 
    v->info = info; 
    if (parent != NULL) { 
     parent->children.push_back(v); 
     v->parent=parent; } 
    else { 
     if (r != NULL) del(r); 
     r = v; 
     r->parent=null; 
      } 
    return v; 
} 

，我修改刪除功能：

void remove(node* v) { 
     if (r == v) r = NULL; 
     else { 
     v->parent->children.pop_back(v); 
     } 
     del(v); 
    } 

這是概念上是否正確？不幸的是，類vector的pop_back method不允許這種類型的參數，所以這會返回一個錯誤。 這是正確的還是應該使用其他實現？

對不起，我不是很熟悉C++。由於

Answer 1

pop_back刪除Vector中的最後一個元素 - 無論它是...

試試這個：

std::vector<node*>::iterator entry = std::find(v->parent->begin(), v->parent->end(), v); 
if(entry != v->parent->end()) 
    v->parent->erase(entry); 

或更短：

auto entry = std::find(v->parent->begin(), v->parent->end(), v); 
/* ... */ 

變種會使用std ::刪除：

v->parent->erase(std::remove(v->parent->begin(), v->parent->end(), v), v->parent->end()); 

std::remove移除了給定範圍內的v的所有 OCCURENCES（假設它只有一個...）通過移動所有後續元件朝開始位置的適當數量（如果一個元件已被移除，一個位置，如果兩個元素，兩個位置......）並且將迭代器返回到仍然在使用中的最後一個之後的位置。但是，從這裏開始的元素仍然保留在向量（或列表或...）中，因此您必須刪除這些元素，這是由函數vector::erase的第二個變體完成的。概念：有一點對我來說很重要：如果父母爲空，則想要刪除根。但是，如果root擁有孩子本身呢？你會在del函數中遞歸地刪除它們嗎？你確定你真的想替換已經包含的整個樹嗎？可能最好是的孩子呢？

但是現在不要把它理解爲「你應該這樣做」 - 這只是一個推薦的想法 - 但我不知道你的要求，所以這取決於你自己決定......只有一個重要的事情：不要忘了刪除節點的孩子，如果你刪除它，否則你有內存泄漏...

除此之外，你的概念乍一看對我來說很好...

編輯：回答您的評論的問題：適當的析構函數應該是這樣的：

~node() 
{ 
    for(node* n : children) 
    { 
     delete n; 
    } 
} 

這會遞歸地刪除所有子節點的所有節點。所有你需要做的，以清除整棵樹是

delete r; 
r = nullptr; 

e。 g .:

void clear() 
{ 
    delete r; 
    r = nullptr; 
} 
~tree() 
{ 
    clear(); 
} 

我認爲這不是你的意圖，但是如果你的節點被插入到多個子載體中，你將陷入深重的麻煩！

因此，如果您計劃稍後重新租用節點，請記住從其父列表中刪除節點。如果你想保留一些子節點，當然你需要先把它們從樹中移出。

Answer 2

其實我做這樣的事情：

~tree() 
{ 
    for(node::iterator it=r->children.begin(); it!=r->children.end(); ++it) 
    { 
     (*it)->info=NULL; 
     node* tmp= new node; 
     tmp=(*it); 
     delete tmp; 
    } 
    r->info=NULL; 
    delete r; //Dealloco la memoria riservata ad r 
}