二叉搜索树的插入问题

yyaadet

为什么总是插不入结点。
#include<stdio.h>
#include<stdlib.h>

struct tree
{
        int data;
        struct tree *left,*right;
};
typedef struct tree Tree;

Tree *bs_search(Tree *base , int key);
void insert(Tree *base, int key);
void travel(Tree *base);

Tree *bs_search(Tree *base , int key)
{
        if(base==NULL)
                return NULL;
        if(base->data==key)
                return base;
        else
        {
                if(key>base->data)
                {
                        base=base->right;
                        bs_search(base,key);
                }
                else
                {
                        base=base->left;
                        bs_search(base,key);
                }
        }
}

void insert(Tree *base,int key)
{
        //add your code
        Tree *cur=(Tree *)malloc(sizeof(Tree));
        Tree *temp=(Tree *)malloc(sizeof(Tree));
        temp->data=key;
        temp->left=NULL;
        temp->right=NULL;
        cur=bs_search(base,key);
        if(cur!=NULL)
        {
                return ;
        }       
        if(cur==NULL)
        {
                cur=temp;
                return ;
        }
}

void travel(Tree *base)
{
        //add your code
        if(base==NULL)
                return;
        else
        {
                printf(" %d ",base->data);
                travel(base->left);
                travel(base->right);
        }
        printf("\n");
}

int main()
{
        Tree *base=(Tree *)malloc(sizeof(Tree));
    int a[]={2,5,7,5,1,9};
        int i;
        base->data=6;
        base->left=NULL;
        base->right==NULL;
        insert(base,2);
        //for(i=0;i<6;i++)
        //{
        //        insert(base,a[i]);
        //}
        travel(base);
        return 0;
}

earl808

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

struct tree
{
        int data;
        struct tree *left,*right;
};
typedef struct tree Tree;

Tree **bs_search(Tree **base , int key);
void insert(Tree *base, int key);
void travel(Tree *base);

Tree **bs_search(Tree **base , int key)
{
        if((*base)==NULL)
                return base;
        if((*base)->data==key)
                return NULL;
        else
        {
                if(key>(*base)->data)
                {
                        base=&((*base)->right);
                        bs_search(base,key);
                }
                else
                {
                        base=&((*base)->left);
                        bs_search(base,key);
                }
        }
}

void insert(Tree *base,int key)
{
        //add your code
        Tree **cur=NULL;
        Tree *temp=(Tree *)malloc(sizeof(Tree));
        temp->data=key;
        temp->left=NULL;
        temp->right=NULL;
        cur=bs_search(&base,key);
        if(cur==NULL)
        {
                printf("jh");
                return ;
        }      
        if(cur!=NULL)
        {
                *cur=temp;
                return ;
        }
}

void travel(Tree *base)
{
        //add your code
        if(base==NULL)
                return;
        else
        {
                printf(" %d ",base->data);
                travel(base->left);
                travel(base->right);
        }
        printf("\n");
}

int main()
{
        Tree *base=(Tree *)malloc(sizeof(Tree));
            int a[]={2,5,7,5,1,9};
        int i;
        base->data=6;
        base->left=NULL;
        base->right=NULL;
        insert(base,2);
        for(i=0;i<6;i++)
        {
                insert(base,a[i]);
        }
        printf("%d",base->left);
        travel(base);
        return 0;
}

我按照楼主的写了一下。。不过在vc下能实现。。在gcc下也不能插入。。不知道为什么

lenovo

1. 
   
2. Tree **bs_search(Tree **base , int key)
   
3. {
   
4.         if((*base)==NULL)
   
5.                 return base;
   
6.         if((*base)->data==key)
   
7.                 return NULL;
   
8.         else
   
9.         {
   
10.                 if(key>(*base)->data)
    
11.                 {
    
12.                         base=&((*base)->right);
    
13.                         return bs_search(base,key);
    
14.                 }
    
15.                 else
    
16.                 {
    
17.                         base=&((*base)->left);
    
18.                         return bs_search(base,key);
    
19.                 }
    
20.         }
    
21. }
    

复制代码

代码用[ code ]括起来。

earl808

1. Breakpoint 3, bs_search (base=0x804a00c, key=2) at b-tree.c:17
   
2. 17              if((*base)==NULL)
   
3. (gdb)
   
4. 18                      return base;
   
5. (gdb) print base
   
6. $3 = (Tree **) 0x804a00c
   
7. (gdb) next
   
8. 34      }
   
9. (gdb)
   
10. insert (base=0x804a008, key=2) at b-tree.c:45
    
11. 45              if(cur==NULL)
    
12. (gdb) print cur
    
13. $4 = (Tree **) 0xbffffc7c
    
14. (gdb) Quit
    
15. (gdb)

复制代码

这是gdb调试信息。。。
return base时base=0x804a00c
怎么cur=bs_search(&base,key)后cur=0xbffffc7c了?

mik

原帖由 earl808 于 2006-7-6 00:33 发表
[code]Breakpoint 3, bs_search (base=0x804a00c, key=2) at b-tree.c:17
17              if((*base)==NULL)
(gdb)
18                      return base;
(gdb) print base
$3 = (Tree **) 0x804a00c
(gd ...

cur 是个 local var

earl808

cur的作用域不是在整个insert函数里吗?
返回值是0x804a00c
不也就是cur=0x804a00c
cur的赋值和gdb中的检测是在同一个作用域啊
为什么会变了呢?

lenovo

你都没看我给出的代码呀？

earl808

。。对不起啊。。还以为你只是提示我要用code呢。。
应该是说base是个local var..

yyaadet

是不是用bs_search()搜索返回的结点不是需要插入的节点。

earl808

原帖由 yyaadet 于 2006-7-6 22:39 发表
是不是用bs_search()搜索返回的结点不是需要插入的节点。

嗯，我们平时向二叉树插入时一般都是用base->right..这其实是一个指针。。。
你不能直接返回right,所以要用指针的指针指向right
不过可以返回一个base和一个标志，标志用来说明是left还是right，这样的参数简单点