如果您的节点确实包含有效的parent指针，那么整个过程可以以一种更加紧凑和可读的方式完成。

void removetree(Node *node)
{
  while (node != NULL)
  {
    Node *next = node->child;

    /* If child subtree exists, we have to delete that child subtree 
       first. Once the child subtree is gone, we'll be able to delete 
       this node. At this moment, if child subtree exists, don't delete
       anything yet - just descend into the child subtree */

    node->child = NULL;
    /* Setting child pointer to null at this early stage ensures that 
       when we emerge from child subtree back to this node again, we will 
       be aware of the fact that child subtree is gone */

    if (next == NULL)
    { /* Child subtree does not exist - delete the current node, 
         and proceed to sibling node. If no sibling, the current 
         subtree is fully deleted - ascend to parent */
      next = node->next != NULL ? node->next : node->parent;
      remove(node); // or `free(node)`
    }

    node = next;
  }
}

这是一棵二叉树！因为你选择的名字让人们感到困惑，next在链表中很常见，但类型才是最重要的，你有一个节点引用了两个完全相同的节点类型，这才是最重要的。
取自此处：https://codegolf.stackexchange.com/a/489/15982你链接到。我将left重命名为child，将right重命名为next：）

void removetree(Node *root) {
    struct Node * node = root;
    struct Node * up = NULL;

    while (node != NULL) {
        if (node->child != NULL) {
            struct Node * child = node->child;
            node->child = up;
            up = node;
            node = child;
        } else if (node->next != NULL) {
            struct Node * next = node->next;
            node->child = up;
            node->next = NULL;
            up = node;
            node = next;
        } else {
            if (up == NULL) {
                free(node);
                node = NULL;
            }
            while (up != NULL) {
                free(node);
                if (up->next != NULL) {
                    node = up->next;
                    up->next = NULL;
                    break;
                } else {
                    node = up;
                    up = up->child;
                }
            }
        }
    }
}

我知道这是一个老帖子，但我希望我的回答能在将来帮助到别人。下面是我在C++中实现的BinaryTree及其操作，没有递归，逻辑可以很容易地在C中实现。
每个节点都拥有一个指向父节点的指针，以使事情变得更容易。
注意：用于打印树内容的inorderPrint（）函数使用递归。

#include<iostream>

template<typename T>
class BinaryTree
{
    
    struct node
    {
        //the binary tree node consists of a parent node for making things easier as you'll see below
        node(T t)
        {
            value = t;
            
        }
        ~node() {  }
        struct node *parent = nullptr;
        T value;
        struct node *left   = nullptr;
        struct node *right  = nullptr;
    };
    node* _root;

    //gets inorder predecessor
    node getMinimum(node* start)
    {
        
        while(start->left)
        {
            start = start->left;
        }
        return *start;
    }
    /*
        this is the only code that uses recursion
        to print the inorder traversal of the binary tree
    */
    void inorderTraversal(node* rootNode)
    {
        
        if (rootNode)
        {
            
            inorderTraversal(rootNode->left);
            std::cout << rootNode->value<<" ";
            inorderTraversal(rootNode->right);
            
        }
        
    }
    int count;
public:
    int Count()
    {
        return count;
    }
    void Insert(T val)
    {
        count++;
        node* tempRoot = _root;
    
        if (_root == nullptr)
        {
            
            _root = new node(val);
            _root->parent = nullptr;
            
        }
        else
        {
            while (tempRoot)
            {

                if (tempRoot->value < val)
                {
                    if (tempRoot->right)
                        tempRoot = tempRoot->right;
                    else
                    {
                        tempRoot->right = new node(val );
                        tempRoot->right->parent = tempRoot;
                        break;
                    }
                }
                else if (tempRoot->value > val)
                {
                    if (tempRoot->left)
                        tempRoot = tempRoot->left;
                    else
                    {
                        tempRoot->left = new node(val);
                        tempRoot->left->parent = tempRoot;
                        break;
                    }
                }
                else
                {
                    std::cout<<"value already exists";
                    count--;
                }
            }
        }

    }
    void inorderPrint()
    {
        inorderTraversal(_root);
        std::cout <<std::endl;
    }
    void Delete(T val)
    {
        node *tempRoot = _root;
        //find the node with the value first
        while (tempRoot!= nullptr)
        {
            if (tempRoot->value == val)
            {
                break;
            }
            
            if (tempRoot->value > val)
            {
                tempRoot = tempRoot->left;
            }
            else
            {
                tempRoot = tempRoot->right;
            }
            
            
        }
        //if such node is found then delete that node
        if (tempRoot)
        {
            //if it contains both left and right child replace the current node's value with inorder predecessor
            if (tempRoot->right && tempRoot->left)
            {
                node inordPred = getMinimum(tempRoot->right);
                Delete(inordPred.value);
                count++;
                tempRoot->value = inordPred.value;
                
            }
            else if (tempRoot->right)
            {
                /*if it only contains right child, then get the current node's parent
                * check if the current node is the parent's left child or right child
                * replace the respective pointer of the parent with the right child of the current node
                * 
                * finally change the child's parent to the new parent
                */
                if (tempRoot->parent)
                {
                    if (tempRoot->parent->right == tempRoot)
                    {
                        tempRoot->parent->right = tempRoot->right;
                    }
                    if (tempRoot->parent->left == tempRoot)
                    {
                        tempRoot->parent->left = tempRoot->right;
                    }
                    tempRoot->right->parent = tempRoot->parent;
                }
                else
                {
                    //if there is no parent then it's a root node
                    //root node should point to the current node's child
                    
                    
                    _root = tempRoot->right;
                    _root->parent = nullptr;
                    delete tempRoot;
                }
                
            }
            else if (tempRoot->left)
            {
                /*
                * same logic as we've done for the right node
                */
                if (tempRoot->parent)
                {
                    if (tempRoot->parent->right == tempRoot)
                    {
                        tempRoot->parent->right = tempRoot->left;
                    }
                    if (tempRoot->parent->left == tempRoot)
                    {
                        tempRoot->parent->left = tempRoot->left;
                    }
                    tempRoot->left->parent =tempRoot->parent ;
                    
                }
                else
                {
                    
                    
                    _root = tempRoot->left;
                    _root->parent = nullptr;
                    delete tempRoot;
                }
                
            }
            else
            {
                /*
                * if it's a leaf node, then check which ptr (left or right) of the parent is pointing to 
                * the pointer to be deleted (tempRoot)
                * then replace that pointer with a nullptr
                * then delete the (tempRoot)
                */
                if (tempRoot->parent)
                {
                    if (tempRoot->parent->right == tempRoot)
                    {
                        tempRoot->parent->right = nullptr;
                    }
                    else if (tempRoot->parent->left == tempRoot)
                    {
                        tempRoot->parent->left = nullptr;
                    }
                    delete tempRoot;
                }
                else
                {
                    //if the leaf node is a root node ,then delete it and set it to null
                    delete _root;
                    _root = nullptr;
                }
                
            }
            count--;
        }
        else
        {
            std::cout << "No element found";
        }
    }
    
    void freeTree()
    {
        //the output it produces will be that of a preorder traversal
        std::cout << "freeing tree:";
        node* end=_root;
        node* parent=nullptr;
        while (end)
        {
            //go to the node with least value
            if (end->left)
                end = end->left;
            else if (end->right)
            {
                //if it's already at the least value, then check if it has a right sub tree
                //if it does then set it as "end" ptr so that the loop will check for the least node in this subtree
                end = end->right;
            }
            else
            {
                //if it's a leaf node then it should be deleted and it's parent's (left or right pointer )
                //should be safely set to nullptr
                //then end should be set to the parent pointer
                //so that it we can repeat the process for all other nodes that's left
                std::cout << end->value<<" ";
                parent = end->parent;
                if (parent)
                {
                    if (parent->left == end)
                        parent->left = nullptr;
                    else
                        parent->right = nullptr;
                    delete end;
                    
                }
                else
                {
                    delete end;
                    _root = nullptr;
                }
                
                count--;
                end = parent;
            }
            
        }
        
    }
    ~BinaryTree()
    {
        freeTree();
    }
};

int main()
{
    BinaryTree<int> bt;
    bt.Insert(3);
    bt.Insert(2);
    bt.Insert(1);
    bt.Insert(5);
    bt.Insert(4);
    bt.Insert(6);
    std::cout << "before deletion:\n";
    bt.inorderPrint();
    bt.Delete(5);
    bt.Delete(2);
    bt.Delete(1);
    bt.Delete(4);
    std::cout << "after deletion:\n";
    bt.inorderPrint();
    bt.freeTree();
    std::cout << "\nCount: " << bt.Count()<<"\n";
}

输出：

before deletion:
1 2 3 4 5 6
after deletion:
3 6
freeing tree:6 3
Count: 0
freeing tree:

首先要说的是，如果你试图用非递归的方法来解决递归问题，你会遇到麻烦。
我看到一个错误的答案被选为好的答案，所以我会试着展示我的方法：
我将开始使用指针引用而不是普通指针，因为传递根指针引用可以更容易地检测（和更新）指向根节点的指针。因此，例程的接口将是：

void delete_tree(struct node * * const ref);

它表示对指向根节点的指针的引用。我将下降到节点，如果child或next中的一个是NULL，那么这个节点可以通过使引用指针指向另一个链接来自由消除（所以我不会丢失它）。如果节点有两个子节点（child和next都是!= NULL），那么我不能删除这个节点，直到其中一个分支折叠，然后我选择其中一个分支并移动引用（我声明了ref参数const以确保我不会修改它，所以我为此使用另一个 moving 引用）

struct node **moving_reference;

然后，算法如下：

void tree_delete(struct node ** const static_ref)
{
    while (*static_ref) {
        struct node **moving_ref = static_ref;

        while (*moving_ref) {
            struct node *to_be_deleted = NULL;

            if ((*moving_ref)->child && (*moving_ref)->next) {
                /* we have both children, we cannot delete until
                 * ulterior pass. Just move the reference. */
                moving_ref = &(*moving_ref)->child;
            } else if ((*moving_ref)->child) {
                /* not both != NULL and child != NULL, 
                 * so next == NULL */
                to_be_deleted = *moving_ref;
                *moving_ref = to_be_deleted->child;
            } else {
                /* not both != NULL and child == NULL,
                 * so follow next */
                to_be_deleted = *moving_ref;
                *moving_ref = to_be_deleted->next;
            } /* if, else if */
            /* now, delete the unlinked node, if available */
            if (to_be_deleted) node_delete(to_be_deleted);
        } /* while (*moving_ref) */
    } /* while (*static_ref) */
} /* delete_tree */

我已经在一个完整的例子中包含了这个算法，向您展示了部分树和moving_ref在树中移动时的位置。它还显示了删除它所需的刀路。

#include <stdio.h>
#include <stdlib.h>

#define N 100

#define D(x) __FILE__":%d:%s: " x, __LINE__, __func__

#define ASSERT(x) do { \
        int res; \
        printf(D("ASSERT: (" #x ") ==> %s\n"), \
                        (res = (int)(x)) ? "TRUE" : "FALSE"); \
        if (!res) exit(EXIT_FAILURE); \
} while (0)

struct node {
        int key;
        struct node *child;
        struct node *next;
}; /* struct node */

struct node *node_alloc(void);
void node_delete(struct node *n);

/* This routine has been written recursively to show the simplicity
 * of traversing the tree when you can use recursive algorithms. */
void tree_traverse(struct node *n, struct node *p, int lvl)
{
    while(n) {
        printf(D("%*s[%d]\n"), lvl<<2, p && p == n ? ">" : "", n->key);
        tree_traverse(n->child, p, lvl+1);
        n = n->next;
    } /* while */
} /* tree_traverse */

void tree_delete(struct node ** const static_ref)
{
    int pass;

    printf(D("BEGIN\n"));

    for (pass = 1; *static_ref; pass++) {
        struct node **moving_ref = static_ref;

        printf(D("Pass #%d: Considering node %d:\n"),
                        pass, (*moving_ref)->key);

        while (*moving_ref) {
            struct node *to_be_deleted = NULL;

            /* print the tree before deciding what to do. */
            tree_traverse(*static_ref, *moving_ref, 0);

            if ((*moving_ref)->child && (*moving_ref)->next) {
                printf(D("Cannot remove, Node [%d] has both children, "
                                        "skip to 'child'\n"),
                                (*moving_ref)->key);
                /* we have both children, we cannot delete until
                 * ulterior pass. Just move the reference. */
                moving_ref = &(*moving_ref)->child;
            } else if ((*moving_ref)->child) {
                /* not both != NULL and child != NULL, 
                 * so next == NULL */
                to_be_deleted = *moving_ref;
                printf(D("Deleting [%d], link through 'child' pointer\n"),
                                to_be_deleted->key);
                *moving_ref = to_be_deleted->child;
            } else {
                /* not both != NULL and child != NULL,
                 * so follow next */
                to_be_deleted = *moving_ref;
                printf(D("Deleting [%d], link through 'next' pointer\n"),
                                to_be_deleted->key);
                *moving_ref = to_be_deleted->next;
            } /* if, else if */

            /* now, delete the unlinked node, if available */
            if (to_be_deleted) node_delete(to_be_deleted);
        } /* while (*moving_ref) */
        printf(D("Pass #%d end.\n"), pass);
    } /* for */

    printf(D("END.\n"));
} /* delete_tree */

struct node heap[N] = {0};
size_t allocated = 0;
size_t deleted = 0;

/* simple allocation/free routines, normally use malloc(3). */
struct node *node_alloc()
{
        return heap + allocated++;
} /* node_alloc */

void node_delete(struct node *n)
{
        if (n->key == -1) {
                fprintf(stderr,
                                D("doubly freed node %ld\n"),
                                (n - heap));
        }
        n->key = -1;
        n->child = n->next = NULL;
        deleted++;
} /* node_delete */

/* main simulation program. */
int main()
{
        size_t i;

        printf(D("Allocating %d nodes...\n"), N);
        for (i = 0; i < N; i++) {
                struct node *n;

                n = node_alloc(); /* the node */
                n->key = i;
                n->next = NULL;
                n->child = NULL;

                printf(D("Node %d"), n->key);

                if (i) { /* when we have more than one node */
                        /* get a parent for it. */
                        struct node *p = heap + (rand() % i);

                        printf(", parent %d", p->key);
                        /* insert as a child of the parent */
                        n->next = p->child;
                        p->child = n;
                } /* if */
                printf("\n");
        } /* for */

        struct node *root = heap;

        ASSERT(allocated == N);
        ASSERT(deleted == 0);

        printf(D("Complete tree:\n"));
        tree_traverse(root, NULL, 0);

        tree_delete(&root);

        ASSERT(allocated == N);
        ASSERT(deleted == N);
} /* main */

为什么不递归地做呢？

void removetree(Node *node) {
  if (node == NULL) {
    return;
  }
  number_of_iterations++;
  removetree(node->next);
  removetree(node->child);
  free(node);
  number_of_deletions++;
}

该实现不适用于根为1的树，该树只有一个子树2。

NodeOne.parent = null
NodeOne.next = null
NodeOne.child = NodeTwo

NodeTwo.parent = null
NodeTwo.next = null
NodeTwo.child = null

执行Removetree(NodeOne)不会在NodeOne上调用remove。

我会的

void removeTree(Node *node){
    Node *temp;
    while (node !=NULL){
        if (node->child != NULL) {
            removeTree(node->child);
        }
        temp = node;
        node = node->next;
        free(temp);
    }
}

非递归版本：

void removeTree(Node *node){
    Node *temp;
    while (node !=NULL){
        temp = node;
        while(temp != node) {
            for(;temp->child == NULL; temp = temp->child); //Go to the leaf
            if (temp->next == NULL)
                free(temp); //free the leaf
            else { // If there is a next move it to the child an repeat
                temp->child = temp->next;
                temp->next = temp->next->next;
            }
        }
        node = temp->next; // Move to the next
        free(temp)
    }
}

我想这应该能行

您只释放子树，而不是父节点。假设child表示节点的left子节点，next是right子节点。然后，您的代码变为：

struct Node{
    Node *parent;
    Node *right;
    Node *left;
}

int number_of_iterations =0;
int number_of_deletions =0;
    void removetree(Node *node)
    {
        number_of_iterations++;
        while(node != NULL)
        {
            Node *temp = node;

            if(node->left != NULL)
            {
                node = node->left;
                temp->left = node->right;
                node->right = temp;
            }
            else
            {
                node = node->right;
                remove(temp);
                number_of_deletions++ 
            }
        }
    }

每次while循环完成一次迭代时，左子节点将没有指向它的指针。以下面的树为例：

1
     2                3
4        5        6         7

当node是根节点时，会发生以下情况

• node指向“% 1”
• temp指向“% 1”
• node现在指向“2”
• temp->left现在指向“5”
• node->right现在指向“1”

在下一次迭代中，您开始使用指向'2'的node和temp。如您所见，您没有删除节点“% 1”。这将重复。
为了解决这个问题，如果希望避免递归，您可能需要考虑使用BFS和类似队列的结构来删除所有节点。

编辑BFS方式：

1.创建队列结构Q
1.将根节点node添加到Q
1.将node的左节点添加到Q
1.将node的右节点添加到Q
1.释放node并将其从Q中删除
1.设置node = Q的第一个元素
1.重复步骤3-6，直到Q变为空
这使用了队列是FIFO结构的事实。

起初，我认为@AnT建议的代码是不正确的，因为我认为这个问题是关于一个以通常方式定义的二叉树（即每个节点都引用其左子树和右子树）。此为虚妄。）假设，结果是节点在其左子树被遍历和释放之后立即被释放，但在右子树发生相同的情况之前。然后，当从右子树向上时，我们将踩在已经被释放的父节点上。
我忽略的是，在最初的问题中，二叉树被表示为一个通用的二叉树，以单向链表的队列的形式，具有到父节点的额外的内部链接。为了清楚起见，我绘制了下图，其中虚线表示对父代的引用。

如果有人仍然关心，有一个正确的方法在通常的形式二叉树。但它仍然需要父链接。用C89写的

void igena_avl_subtree_free( igena_avl_node_p root ) {
  igena_avl_node_p next_node;
{
  while (root != NULL) {
    if (root->left != NULL) {
      next_node = root->left;
      root->left = NULL;
    } else if (root->right != NULL) {
      next_node = root->right;
      root->right = NULL;
    } else {
      next_node = root->parent;
      free( root );
    }
    root = next_node;
  }
}}

直接取自我自己的项目Gena。