ネイリーツリーを削除するには？各ノードにも親ポインタがあります

Question

ノードの構造は以下のとおりです。

struct node 
{ 
    int data; 
    int noofchilds; 
    node *child[n]; 
    node *parent; 
}; 

再帰的アプローチと非再帰的アプローチの両方に感謝します。

Answer 1

非再帰バージョン：

struct node { 
    struct node *parent; 
    unsigned nchild; 
    struct node *child[XXX]; 
    int data; 
    }; 

void deltree(struct node *np) 
{ 
struct node *par; 

while (np) { 
     /* if this node has any children, start by 
     ** "descending" to the highest numbered child and kill that first. 
     */ 
     if (np->nchild--) { 
       np = np->child[np->nchild]; 
       continue; 
       } 
     /* when we arrive here, *np has no more children left, 
     ** so kill it, and step up to its parent 
     */ 
     par = node->parent; 
     // if np->child was obtained via malloc() uncomment next line 
     // free (np->child); 
     free (np); 
     np = par; 
     } 
return; 
} 

Answer 2

ノードを削除し、子ノードを再帰的に削除します。

完全なツリーを削除する必要がある場合は、親ポインタは問題ではありません（ノード自体が削除されると削除されます）。

Answer 3

反復アルゴリズム：

Start at the parent node. 

Then do the following actions as long as possible: 
    if the current node has one or more children: 
     set one of the children nodes as the (next) current node 
    else 
     delete the current node and use its parent as the (next) current node. 
     if the current node was the root node (which has no parent), stop.