0

我已经在 C 中实现了 BST。插入和查找工作正常。但是删除根节点时删除有问题。我无法释放指向根节点的指针。如果我将它作为双指针传递，我可以，但我想在不使用双指针的情况下保持代码简单。这里我没有指向根节点的头指针。我应该使用指向根节点的头指针吗？

#include<stdio.h>
#include<stdlib.h>
struct node
{
    int data;
    struct node* left;
    struct node* right;
};
struct node* newNode(int data)
{
    struct node* node = malloc(sizeof(struct node));
    node->data=data;
    node->left=NULL;
    node->right=NULL;
    return(node);
}

static int lookup(struct node* node,int target)
{
    if(node==NULL)
    {
        return(0);
    }
    else
    {
        if(target == node->data)
        {
            return(1);
        }
        else
        {
            if(target < node->data)
            {
                return(lookup(node->left,target));
            }
            else
            {
                return(lookup(node->right,target));
            }
        }
    }
}


struct node* insert(struct node* node, int data)
{
    if(node==NULL)
    {
        return(newNode(data));
    }   
    else
    {
        if(data < node->data)
        {
            node->left =insert(node->left,data);
        }
        else
        {
            node->right=insert(node->right,data);
        }
        return(node);
    }
}

struct node* delete(struct node* node, struct node* pnode, int target)
{
    struct node* rchild;
    struct node* rchildparent;
    if(node==NULL)
    {
        return(pnode);
    }
    else
    {
        if(target == node->data)
        {
            if(node->left == NULL && node->right == NULL) //leaf node
            {
                if(pnode == NULL) //special case deleting the root node
                {
                    free(node);
                    return(NULL);
                }
                if(pnode->left == node)
                {
                    pnode->left = NULL;
                }
                else
                {
                    pnode->right = NULL;
                }
                free(node);
                return(pnode);
            }
            if(node->left ==NULL ) //one child
            {
                if(pnode == NULL) //deleting root having no left child
                {
                    struct node* temp = node;
                    node = node->right;
                    free(temp);
                    return(node);
                }
                if(pnode->left == node)
                {
                    pnode->left = node->right;
                }
                else
                {
                    pnode->right = node->right;
                }   
                free(node);
                return(pnode);
            }
            if(node->right ==NULL ) //one child
            {
                if(pnode == NULL) //deleting root having no right child
                {
                    struct node* temp = node;
                    node = node->left;
                    free(temp);
                    return(node);
                }
                if(pnode->left == node)
                {
                    pnode->left = node->left;
                }
                else
                {
                    pnode->right = node->left;
                }   
                free(node);
                return(pnode);
            }

            //two children case
            rchild = node->right;
            rchildparent=node;
            while(rchild->left != NULL)
            {
                rchildparent=rchild;
                rchild = rchild->left;
            }
            node->data=rchild->data;
            if(rchildparent == node)
            {
                //rchildparent->right=rchild->right;
                node->right=rchild->right;
            }
            else
            {
                //rchildparent->left=NULL;
                rchildparent->left=rchild->right;
            }
            free(rchild);
            if(pnode ==NULL) //root node
            {
                return(node);
            }           
            return(pnode);
        }
        else
        {
            if(target < node->data)
            {
                delete(node->left,node,target);
                return(node);
            }
            else
            {
                delete(node->right,node,target);
                return(node);
            }
        }

    }

}
void printinorder(struct node* node)
{
    if(node == NULL)
    {
        return;
    }   
    printinorder(node->left);
    printf("%d\t",node->data);
    printinorder(node->right);
}
int main()
{
    clock_t start,end;
    struct node* root = newNode(3);
    insert(root,7);
    insert(root,7);
    insert(root,7);
    printinorder(root);
    printf("\n");
    root = delete(root,NULL,6);
    printinorder(root);
    printf("\n");
}

编辑：根据@modifiable lvalue建议修复了代码。现在有没有办法改进删除逻辑？

4

3 回答 3

1

我会从删除中返回头节点，并在你的主函数中管理头，比如：root = delete(root, NULL, 10);，我会为 insert: 做同样的事情root = insert(root,/*...*/);，因为它看起来像你已经完成的一半......

于 2013-03-07T08:31:17.370 回答
0

私有数据节点删除（数据节点根，int dValue）{

DataNode temp=null;
if(root!=null){
    if(dValue<root.value){
        root.left=delete(root.left,dValue);
    }
    else if(dValue>root.value){
        root.right=delete(root.right,dValue);
    }
    else{
           if(root.left==null){
                temp=root.right;
               root.right=null;
               return temp;
           }
           else if(root.right==null){
               temp=root.left;
               root.left=null;
               return temp;
           }

           temp=MinBST(root.right);
           root.value=temp.value;
           //deleting inorder successor
           root.right=null;
    }
}
return root;

}

私有数据节点 MinBST（数据节点根）{

if(root!=null){
    while(root.left!=null){
        root=root.left;
    }
}
return root;

}

浏览从二叉树中删除节点的链接

https://www.youtube.com/watch?v=YK3tLMYk3nk

于 2015-04-24T11:12:49.343 回答
0 
//c tree
#include<stdio.h>
#include<conio.h>
struct tree_node
{
    struct tree_node*right,*left;
    int data;
};
struct tree_node*savetemp=NULL;
struct tree_node* del(struct tree_node*,int);
struct tree_node* insert(struct tree_node*,int);
struct tree_node* travel(struct tree_node*,struct tree_node*);
void inorder(struct tree_node *);
int height(struct tree_node*);
int noOfNode(struct tree_node *);
void main()
{
    struct tree_node* root=NULL;
    int item,cho;
    clrscr();
    do
    {
        printf("Enter your choice\n");
        printf("1.insert 2.delete 3.display 4.no of nodes 5.height 6.exit\n");
        scanf("%d",&cho);
        switch(cho)
        {
            case 1:{
                printf("Enter element to insert\n");
                scanf("%d",&item);
                root=insert(root,item);
            }
            break;
            case 2:{
                printf("Enter element to delete\n");
                scanf("%d",&item);
                root=del(root,item);
                if(savetemp!=NULL)//condition for any break link is present to insert or not
                travel(root,savetemp);//to insert break link during insertion
            }
            break;
            case 3:{
                printf("inorder travel\n");
                inorder(root);
            }
            break;
            case 4:{
                printf("No of nodes are: %d\n",noOfNode(root));
            }
            break;
            case 5:
            printf("height of tree %d",height(root));
            break;
            case 6:
            printf("Exiting");
            break;
            default : printf("wrong cho\n");
        }
    }while(cho!=6);
    getch();
}
void inorder(struct tree_node *root)
{
    if (root != NULL)
    {
    inorder(root->left);
    printf("%d \n", root->data);
    inorder(root->right);
    }
}
struct tree_node* insert(struct tree_node*root,int item)
{
    if(root==NULL)
    {
        struct tree_node* temp;
        temp=(struct tree_node*)malloc(sizeof(struct tree_node));
        temp->left=NULL;
        temp->right=NULL;
        temp->data=item;
        root=temp;
    }
    else
    {
            if(root->data<item)
            {
                root->right=insert(root->right,item);
            }
            else
            {
                root->left=insert(root->left,item);
            }
    }
    return(root);
}
struct tree_node* del(struct tree_node*root,int item)
{
    if(item==root->data)
    {
        if(root->left==NULL&&root->right==NULL) //no child
        {
            root=NULL;

        }
        else if(root->left==NULL||root->right==NULL) //one child
        {
            if(root->left!=NULL) //left child
            {
                root=root->left;
            }
            else               //right child
            {
                root=root->right;
            }
        }
        else  if(root->left!=NULL&&root->right!=NULL) //both child
        {
            struct tree_node* temp;
            savetemp=root->right->left;
            temp=root;
            root=root->right;
            root->left=temp->left;
        }
    }
    else
    {
            if(root->data<item)
            {
                root->right=del(root->right,item);
            }
            else
            {
                root->left=del(root->left,item);
            }
    }
    return(root);
}
struct tree_node* travel(struct tree_node*root,struct tree_node*savetemp)
{
    if (savetemp != NULL)
    {
        insert(root,savetemp->data);
        travel(root,savetemp->left);
        travel(root,savetemp->right);
    }
    return(root);
}
int height(struct tree_node*root)
{
    int lheight,rheight;
    if(root==NULL)
    {
        return(-1);
    }
        else
    {
        lheight=height(root->left);
        rheight=height(root->right);
    }
    if(lheight>rheight)
    {
        return(lheight+1);
    }
    else
    {
        return(rheight+1);
    }
}
int noOfNode(struct tree_node *root)
{
static int count=0;
    if (root != NULL)
    {
    noOfNode(root->left);
    count=count+1;
    noOfNode(root->right);
    }
    return(count);
}
于 2016-10-22T04:49:56.230 回答