更改树和修剪

Question

的根我有一个N叉树结构像什么在回答here解释：使用malloc创建

typedef struct node { 
    int ID; 
    struct node *child; // points to (first) child 
    struct node *next; // points to next node at same level (sibling) 
    struct node *parent; // points to parent 
} node; 

节点。

我想编写一个函数，将树的根改变为另一个（指定）节点，并且释放所有节点的内存 - 由于根的变化 - 不再是树的一部分即如果一个节点不能通过父节点追溯到新的根目录，它应该被设置为NULL并且它的内存应该被释放）。

举例来说，如果这是我的树：

 1   
    /\ 
    2 3   
/\ \ 
    4 5  6  
/\ 
7 8  

，我想根本改变，从1到3，然后调用prune_tree功能后，根将是3，每个节点的内存除了3和6以外，将被释放。

我来解决我的问题，最近的包括这样的功能：

void prune_tree(node **root, node *new_root) { 
    if (*root == NULL || (*root)->parent == new_root) 
     return; 

    prune_tree(&((*root)->child), new_root); 
    prune_tree(&((*root)->next), new_root); 

    free(*root); 
    *root = NULL; 
} 

后调用这个函数我设置

root = new_root; 

我来到这里主要是通过试验和错误;事实上，我甚至不知道为什么这个测试大部分时间都是这样。它还增加了在调用该函数之后必须将根设置为新根地址的不必要步骤。我假设有一种方法可以修改函数中的根地址，或返回新的根地址。

我认为我不需要担心内存使用，因为函数释放内存，但是省时的函数更可取。我不知道这是否意味着我应该避开递归或不...

Answer 1

您的方法不起作用，因为您将释放新的根本身。您只能在parent是新根的节点上停止。

这里是一个修正版本：

void prune_tree(node **root, node *new_root) { 
    if (*root == NULL) 
     return; 
    if (*root == new_root) { 
     (*root)->parent = NULL; 
     return; 
    } 
    prune_tree(&(*root)->child, new_root); 
    prune_tree(&(*root)->next, new_root); 
    free(*root); 
    *root = NULL; 
} 

您仍需要调用其地址此功能后，树的根更新到new_root：

prune_tree(&root, new_root); 
root = new_root; 

Answer 2

递归函数会完美的这一点。

你基本上想要做什么（假设树中没有循环）是删除新根的所有兄弟姐妹，他们的子女和父母以及父母的根。

的算法可以是：

typedef struct node { 
    int ID; 
    struct node *child; 
    struct node *sibling; 
    struct node *parent; 
} node; 

void remove_node(struct node* node, struct node* root) 
{ 
    if(node->parent != NULL) 
     remove_node(node->parent, new_root) 

    if(node->sibling != NULL) 
     remove_node(node->sibling, new_root) 

    if((node->child != NULL) && (node->child != root)) 
     remove_node(node->sibling, new_root) 

    free(node) 
} 

void prune_tree(node **root, node *new_root) { 
    *root = new_root 
    remove_node(new_root->parent); 
    remove_node(new_root->sibling); 
} 

假设：

• new_root是树
• 没有循环树

Answer 3

我想我找到了解决办法。 ..

void prune_tree(node** root, node* new_root) 
{ 
    bool del = true; 

    if (*root == NULL) 
     return; 

    if (*root == new_root) { 
     del = false; 
    } 

    if (del){ 
     prune_tree(&(*root)->child, new_root); 
     prune_tree(&(*root)->next, new_root); 
     free(*root); 
     *root = NULL; 
    } 
    else{ 
     prune_tree(&(*root)->next, new_root); 
    } 
}