data-structures - 如何删除一棵二叉树？每个节点也有一个父指针

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.