void类型函数的递归，help

874

被迫用void函数递归遍历二叉树，不知道找到所求的结点后怎么结束递归，我停不下来，大家help
问题如下

编写递归算法，求二叉排序树上的小于x且
最靠近x的值a和大于x且最靠近x的值b。如果这样的
a或b值不存在，则分别返回MINV和MAXV。
实现下列函数：
void OutX(BiTree t, KeyType x, KeyType &a, KeyType &b);
/* a: Return the nearest and smaller value to x, */
/*    but return MINV if no the value in t.      */
/* b: Return the nearest and larger  value to x. */
/*    but return MAXV if no the value in t.      */
二叉树的类型BiTree定义如下：
typedef struct {
    KeyType key;  
    ... ...   // 其他数据域
} ElemType;
typedef struct BiTNode {
    ElemType data;
    BiTNode  *lchild,*rchild;
}BiTNode, *BiTree;

个人思路：
1。中序遍历二叉树，定义静态变量pre，记录前驱结点的数据域关键字
2。系统编译一次以后多次调用这个函数来测试，所以每次递归完成以后必须把pre赋成初值，供下一次调用的时候用
……思路很乱，不知道怎么讲，直接贴代码吧 ，委屈大家读一下我恶心的代码

1. 
   
2. void OutX(BiTree t, KeyType x, KeyType &a, KeyType &b)
   
3. /* a: Return the nearest and smaller value to x, */
   
4. /*    but return MINV if no the value in t.      */
   
5. /* b: Return the nearest and larger  value to x. */
   
6. /*    but return MAXV if no the value in t.      */
   
7. {
   
8.     static KeyType pre=255;
   
9.     static int tag=0;
   
10.     if(t->rchild) tag++;      //tag是标志位，右子树非空加1，访问右子树时减1，最后右子树为空且tag为零时表示遍历完成没找到比x大的值，此时b赋MAXV
    
11.     if (t->lchild) OutX(t->lchild,x,a,b);     //中序遍历
    
12.     if(b已赋值) return;
    
13.     if(pre==255 && t->data.key>=x) a=MINV;    /*pre的初始值为255，本来是要以pre是否为255来判断t是不是最左下的结点，但是在b赋值以后同样会把pre置为255，所以如果b已赋值的话，必须在上一行就结束程序，问题就在于上一行怎样判断b是否已赋值*/
    
14.     if(pre<x && t->data.key>=x)     //给a赋值
    
15.         a=pre;
    
16.     if(pre<=x && t->data.key>x){    //给b赋值，以及把静态变量“初始化”，供下次调用函数时使用
    
17.         b=t->data.key;
    
18.         pre=255;
    
19.         tag=0;
    
20.         return;
    
21.     }
    
22.     pre=t->data.key;    //pre赋值
    
23.     if(t->rchild){          //访问右子树
    
24.         tag--;
    
25.         OutX(t->rchild,x,a,b);
    
26.     }
    
27.     if(pre==255 || b==MAXV) return;     //b已赋过值，退出函数
    
28.     if(tag==0){           //b没有赋过值，且遍历已经完成，把b置MAXV，且把最后一个结点的数据域的关键字赋给a
    
29.     b=MAXV;
    
30.     a=t->data.key;
    
31.     pre=255;
    
32.     tag=0;
    
33.     }
    
34. }
    

复制代码

主要问题在红色部分，如何区分b赋值后的状态和访问最左下结点时的状态
代码中不能上色 ，主要问题是一下几句

1. if (t->lchild) OutX(t->lchild,x,a,b); //中序遍历
   
2. if(b已赋值) return;
   
3. if(pre==255 && t->data.key>=x) a=MINV; /*pre的初始值为255，本来是要以pre是否为255来判断t是不是最左下的结点，但是在b赋值以后同样会把pre置为255，所以如果b已赋值的话，必须在上一行就结束程序，问题就在于上一行怎样判断b是否已赋值*/

复制代码

思路很乱，注释也很乱，希望大家将就着点看一下[em06]
弄了好多天都没能把这个弄完，希望大家帮帮忙

[ 本帖最后由 874 于 2008-6-9 03:57 编辑 ]

onttpi

是数据结构的作业吧？

2。系统编译一次以后多次调用这个函数来测试，所以每次递归完成以后必须把pre赋成初值，供下一次调用的时候用

这句话不知什么意思...不关编译的事吧...

if(b已赋值) return;

这句又是什么意思...



这个算法要求的是值而不是节点，
所以可以用两个变量( 假设为 current_a current_b )，这两个变量用static
保存当前求得的最大和最小的值(一开始赋值为MINV和MAXV即可)
然后中序遍历，对每个节点的值都和 x , MINV , MAXV 比较，决定新的 current_a 和 current_b。

递归结束的条件是左子树和右子树同是为空。

onttpi

void OutX(BiTree t, KeyType x, KeyType &a, KeyType &b){
    KeyType current_a=MINV;
    KeyType current_b=MAXV;

    //处理当前节点
   if(t!=NULL){
        if( t->data.key  >=  x  && t->data.ky<current_b)
             current_b=t->data.key;
        //其它判断......
        //处理左子树
        OutX(t->lchild,x,current_a,current_b);

        //处理右子树
        OutX(t->rchild,x,current_a,current_b);
    }
   


    //赋值，并结束函数递归
   a=current_a;
   b=current_b;
   return;
}

大概没错吧 。。。

[ 本帖最后由 onttpi 于 2008-6-9 16:17 编辑 ]

onttpi

PS：要给代码加颜色用 quote 不要用 code

874

先谢谢楼上
是数据结构作业
这样不行，有好几个问题：
1。经测试，那个作业系统里面MINV是常量'<'，MAXV是常量'>'，所以MINV是常量'>'，所以不可以直接拿MINV和MAXV来比较
2。是我上面要说明的但没说清楚

静态变量只有在编译的时候对变量赋初值，即只赋初值一次，在程序运行时它已有初值。以后每次调用函数时不再重新赋初值，而是知识保留上次函数调用结束时的值。

所以当你测试第一组数据，调用该函数时，current_a和current_b是MINV和MAXV，但在测试第二组数据时，current_a和current_b的值就不是MINV和MAXV了，所以使用静态变量来递归的时候，必须判断出递归什么时候结束，并把静态变量回复成初值，供下一次调用时使用用

在作业系统上跑了几次，结果都是a=<,b=>

onttpi

去掉static，改了下，你运行看看吧...

874

去掉static，每次调用函数时current_a和current_b的值都是MINV和MAXV，显然不符合要求
就这点最烦人，加static也不是，不加也不是

hjack

1. 
   
2. void outx(BiTree t, KeyType x, KeyType &a, KeyType &b)
   
3. {
   
4.    if( t == NULL )
   
5.       return;
   
6. 
   
7.    if( t->data.key == x )
   
8.    {
   
9.       if( t->lchild != NULL )
   
10.          a = t->lchild->data.key;
    
11.       else
    
12.          a = MINV;
    
13.       if( t->rchild != NULL )
    
14.          b = t->rchild->data.key;
    
15.       else
    
16.          b = MAXV;
    
17.    }
    
18.    else if( t->data.key < x )
    
19.    {
    
20.       //left
    
21.       outx(t->lchild, x, a, b);
    
22.       if( b == MAXV )
    
23.          b = t->data.key;
    
24.    }
    
25.    else if( t->data.key > x )
    
26.    {
    
27.       //right
    
28.       outx(t->rchild, x, a, b);
    
29.       if( a == MINV )
    
30.          a = t->data.key;
    
31.    }
    
32. }
    

复制代码

onttpi

晕...
试下这个吧...

我记得我们当时做的有几题是不得不加全局变量的。

void OutX(BiTree t, KeyType x, KeyType &a, KeyType &b){
    static flag=0;
    if(flag==0){
        a=MINV;
        b=MAXV;
   }
    //处理当前节点
   if(t!=NULL){
        if( t->data.key  >=  x  && t->data.ky<b)
             b=t->data.key;
        //其它判断......
        //处理左子树
        flag++;
        OutX(t->lchild,x,a,b);
        //处理右子树
        OutX(t->rchild,x,a,b);
        flag--;
    }
   return;
}

hjack

假设初始入来时参数a就是MINV，b就是MAXV。否则如果一开始就是空树就会有问题了。

onttpi

这个假设不能成立吧...

hjack

那用你那种方法，用个static变量标识初次进入。

874

不是来求代码的，想讨论一下而已
用那个作业系统观察过，a，b一开始是声明后没赋初值的变量
hj好像方向搞错了吧，if( t->data.key < x )这个成立的话应该是访问右子树而不是左子树吧。这个方法应该行得通，去试一下先谢谢了
能说一下思路吗，好像不是遍历。

hjack

是的。方向反了。
思路的话，看代码应该很易明白的吧。
如果不是在子树上的话，那必在父结点上。当查子树为空时，设置为MINV和MAXV，在这一轮查找完后递归返回继续执行时，检查a,b的值，如果是MINV,MAXV，则表明未找到，那么这轮的结点就是了。

皇家救星

记得当年做数据结构的题时有一些递归的函数要重新定义一个函数来调用

即可以这样
int MyOutX(BiTree t, KeyType x, KeyType &a, KeyType &b)
{
}

void OutX(BiTree t, KeyType x, KeyType &a, KeyType &b)
{
MyOutX(...);
}

皇家救星

这样修改后可以在outx里面自己设定a和b的递归初始值
在myouotx里面真正的递归搜索

874

原帖由 皇家救星 于 2008-6-9 22:27 发表
记得当年做数据结构的题时有一些递归的函数要重新定义一个函数来调用

即可以这样
int MyOutX(BiTree t, KeyType x, KeyType &a, KeyType &b)
{
}

void OutX(BiTree t, KeyType x, KeyType &a, KeyType &b)
...

这个方法很不错，谢谢了

874

原帖由 hjack 于 2008-6-9 22:15 发表
是的。方向反了。
思路的话，看代码应该很易明白的吧。
如果不是在子树上的话，那必在父结点上。当查子树为空时，设置为MINV和MAXV，在这一轮查找完后递归返回继续执行时，检查a,b的值，如果是MINV,MAXV，则表明未 ...

明白了，用这个方法解决了，谢谢
你的源代码中if(t->data.key==x)这一段错把t的左右子树的根结点看成t结点的直接前驱和后继结点了，a b的值应该是t的左子树的最大值和右子树的最小值才对，而不是左右儿子的值。把这里改了以后就通过了