C Program to copy one binary search tree to anothe

问题:

So, here i have come up with Binary search tree prgram, where i am creating 2 binary trees tmp and tmp2, where i am trying to copy whole tmp2 to tmp, the node which is taken as input from user. But i am getting some segmentation fault, also i am not so sure if the logic is right. Here is the whole program, please lemme know where is it going wrong in t_cpy() or please just fix it for me..

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

struct node
{
int data;
struct node *rlink;
struct node *llink;
}*tmp=NULL,*tmp2=NULL,*tmp3=NULL;

typedef struct node NODE;

NODE *create();

void inorder(NODE *);
void insert(NODE *);
void t_cpy(NODE *,NODE *);

int main()
{

int n,m;
do
{
    printf("\n1.create tree 1\n2.Insert element to tree1\n3.create tree 2\n4.Insert element to tree2\n5.Inorder tree1\n6.Inorder tree2\n7.Copy tree2 to tree1\n8.exit\n\n");
    printf("\nEnter ur choice: ");
    scanf("%d",&m);
    switch(m)
    {
        case 1: tmp=create();
                break;
        case 2: insert(tmp);
                break;
        case 3: tmp2=create();
                break;
        case 4:
                insert(tmp2);
                break;
        case 5: printf("\n\nInorder Tree1: ");
                inorder(tmp);
                break;
        case 6: printf("\n\nInorder Tree 2: ");
                inorder(tmp2);
                break;
        case 7: t_cpy(tmp,tmp2);

                break;
        case 8: return(0);
    }
}while(n!=8);
return(0);
}
void insert(NODE *root)
{
    NODE *newnode;
    if(root==NULL)
    {
        newnode=create();
        root=newnode;
    }
    else
    {
        newnode=create();
        while(1)
        {
            if(newnode->data<root->data)
            {
                if(root->llink==NULL)
                {
                    root->llink=newnode;
                    break;
                }
                root=root->llink;
            }
            if(newnode->data>root->data)
            {
                if(root->rlink==NULL)
                {
                    root->rlink=newnode;
                    break;
                }
                root=root->rlink;
            }
        }
    }
}

NODE *create()
{
    NODE *newnode;
    int n;
    newnode=(NODE *)malloc(sizeof(NODE));
    printf("\n\nEnter the Data ");
    scanf("%d",&n);
    newnode->data=n;
    newnode->llink=NULL;
    newnode->rlink=NULL;
return(newnode);
}


void t_cpy(NODE *t1,NODE *t2)
{
    int val,opt=0;
    NODE *temp;
    if(t1==NULL || t2==NULL)
    {
        printf("Can not copy !\n");
    }
    inorder(t1);

    printf("\nEnter the node value where tree 2 should be copied\n");
    scanf("%d",&val);
    temp=t1;
    while(temp!=NULL)
    {
        if(val<temp->data)
            temp=temp->llink;
        else
            temp=temp->rlink;
    }
    if(temp->llink!=NULL || temp->rlink!=NULL)
        printf("Not possible to copy tree to this node\n");
    else
    {
        printf("Copy tree to \n 1.Left Node \n 2.Right Node\n Enter your choice : ");
        scanf("%d",&opt);
        if(opt==1)
        {
            temp->llink=t2;
        }
        else if(opt==2)
        {
            temp->rlink=t2;
        }
        else
            printf("Invalid choice\n");
    }
    printf("Tree1 after copying is\n");
    inorder(temp);
}


void inorder(NODE *tmp)
{
    if(tmp!=NULL)
    {
        inorder(tmp->llink);
        printf("%d",tmp->data);
        inorder(tmp->rlink);
    }
}

EDIT : Thanks to @xaxxon , who helped me with this. Just update the while to make it work :

while(temp!=NULL&&temp->data!=val)
{
    if(val<temp->data)
        temp=temp->llink;
    else
        temp=temp->rlink;
    if(temp->llink==NULL && temp->rlink==NULL && temp->data!=val)
    { 
        printf("Invalid Node value entered !\n");
        //break;
        return 0;
    }

and, Now it works fine for if entered value is present in the tree.

Thanks :)

回答1:

Among other possible problems, you traverse temp until it is null, and on the next line you dereference it.

while(temp!=NULL)
    {
        if(val<temp->data)
            temp=temp->llink;
        else
            temp=temp->rlink;
    }
    if(temp->llink!=NULL || temp->rlink!=NULL)
        printf("Not possible to copy tree to this node\n");

You most likely mean to break out of this loop if val == temp->data, but you don't. Also, you still need to check to see if temp is null after the loop in case you didn't find val in your tree. Most likely you just meant to say:

    if(temp==NULL)
        printf("Not possible to copy tree to this node\n");

Also, you can't ask which side of the found node the user wants to copy a tree to. If you have a binary search tree, it has to be the side where the value should go. If you say to copy it to the right side, but all the values are less than the node, it's no longer a BST. In fact, you can't even ask where the value should go and still have a binary search tree. Each node has to be traversed from the root of the tree you want to put the other tree into to maintain the BST mechanics.

回答2:

When you first use insert(tmp) the value of tmp does not change after you call insert(). Pass the address of tmp to insert(), using a *root within it instead of root.