在遍历二叉树的过程中，如何删除树中的节点呢？

wisage

typedef struct rbtreenode_item rbtreenode_t;
typedef struct rbtree_item rbtree_t;

enum RB_COLOR {BLACK,RED};

typedef struct {  
    int        datalen;          // value related to key
    void* pdata;
} ValType;

struct rbtreenode_item
{
        struct rbtreenode_item *left;
        struct rbtreenode_item *right;
        struct rbtreenode_item *parent;
        enum RB_COLOR color;
        KeyType        key;
        ValType val;                // data related to key
};

struct rbtree_item
{
        rbtreenode_t *root;
        rbtreenode_t *nil;
};

void rbtInorder(rbtree_t *rbtree, void (callback)(rbtreenode_t *,int *),int *RetVal)
{
        rbtreenode_t *p=NULL;
        p=rbtree->root;

        rbtreenode_t *stack[MAXSIZE];
        int top = -1;
        while(p != rbtree->nil || top > -1)
        {
                while (isValidPointer((unsigned int)p) && p != rbtree->nil)
                {
                        top++;
                        stack[top] = p;
                        p = p->left;
                }

                 /* 出栈并访问该节点 */
                 p = stack[top];
                 top--;
                 callback(p,RetVal);
                 /* 扫描p的右孩子 */
                 p = p->right;     
        }
        return;
}

回调函数中进行条件判断，符合条件就将节点p删除，但这时树会重新平衡，原有的节点指针p也为空了
请问各位大侠，如何在遍历的过程中删除符合条件的节点呢？

wisage

自己顶一下，没有人知道吗？

雨夜流星

static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,                  struct rb_root *root) {     struct rb_node *other;     while ((!node || rb_is_black(node)) && node != root->rb_node)     {         if (parent->rb_left == node)         {             other = parent->rb_right;             if (rb_is_red(other))             {                 rb_set_black(other);                 rb_set_red(parent);                 __rb_rotate_left(parent, root);                 other = parent->rb_right;             }             if ((!other->rb_left || rb_is_black(other->rb_left)) &&                 (!other->rb_right || rb_is_black(other->rb_right)))             {                 rb_set_red(other);                 node = parent;                 parent = rb_parent(node);             }             else             {                 if (!other->rb_right || rb_is_black(other->rb_right))                 {                     struct rb_node *o_left;                     if ((o_left = other->rb_left))                         rb_set_black(o_left);                     rb_set_red(other);                     __rb_rotate_right(other, root);                     other = parent->rb_right;                 }                 rb_set_color(other, rb_color(parent));                 rb_set_black(parent);                 if (other->rb_right)                     rb_set_black(other->rb_right);                 __rb_rotate_left(parent, root);                 node = root->rb_node;                 break;             }         }         else         {             other = parent->rb_left;             if (rb_is_red(other))             {                 rb_set_black(other);                 rb_set_red(parent);                 __rb_rotate_right(parent, root);                 other = parent->rb_left;             }             if ((!other->rb_left || rb_is_black(other->rb_left)) &&                 (!other->rb_right || rb_is_black(other->rb_right)))             {                 rb_set_red(other);                 node = parent;                 parent = rb_parent(node);             }             else             {                 if (!other->rb_left || rb_is_black(other->rb_left))                 {                     register struct rb_node *o_right;                     if ((o_right = other->rb_right))                         rb_set_black(o_right);                     rb_set_red(other);                     __rb_rotate_left(other, root);                     other = parent->rb_left;                 }                 rb_set_color(other, rb_color(parent));                 rb_set_black(parent);                 if (other->rb_left)                     rb_set_black(other->rb_left);                 __rb_rotate_right(parent, root);                 node = root->rb_node;                 break;             }         }     }     if (node)         rb_set_black(node); }

雨夜流星

static void rb_erase(struct rb_node *node, struct rb_root *root) {     struct rb_node *child, *parent;     int color;     if (!node->rb_left)         child = node->rb_right;     else if (!node->rb_right)         child = node->rb_left;     else     {         struct rb_node *old = node, *left;         node = node->rb_right;         while ((left = node->rb_left) != NULL)             node = left;         child = node->rb_right;         parent = rb_parent(node);         color = rb_color(node);         if (child)             rb_set_parent(child, parent);         if (parent == old) {             parent->rb_right = child;             parent = node;         } else             parent->rb_left = child;         node->rb_parent_color = old->rb_parent_color;         node->rb_right = old->rb_right;         node->rb_left = old->rb_left;         if (rb_parent(old))         {             if (rb_parent(old)->rb_left == old)                 rb_parent(old)->rb_left = node;             else                 rb_parent(old)->rb_right = node;         } else             root->rb_node = node;         rb_set_parent(old->rb_left, node);         if (old->rb_right)             rb_set_parent(old->rb_right, node);         goto color;     }     parent = rb_parent(node);     color = rb_color(node);     if (child)         rb_set_parent(child, parent);     if (parent)     {         if (parent->rb_left == node)             parent->rb_left = child;         else             parent->rb_right = child;     }     else         root->rb_node = child;  color:     if (color == RB_BLACK)         __rb_erase_color(child, parent, root); } int rb_delete_node(struct rb_root *root, void *delvalue, cmp_callback_func cmpfunc) {     struct rb_node *pt = rb_find_node(root, delvalue, cmpfunc);          if ( NULL != pt )     {         rb_erase(pt, root);         return 1;     }          return 0; }

大概是这个样子吧

shmild

有一种比较适合普通人的办法，惰性删除

雨夜流星

懒惰删除遗留的问题也比较多