9.32.c

来自「部分高校使用anyview编程测试数据结构习题,此代码为数据结构题集(c语言版)」· C语言 代码 · 共 46 行

9.32③  编写递归算法，求二叉排序树上的小于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;
void Out_X(BiTree t, KeyType x, KeyType &a, KeyType &b,int &last);
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.      */
{ int last=0;
  a=b=0;
  Out_X(t,x,a,b,last);
  if(a==0) a=MINV;
  if(b==0) b=MAXV;
  
}
void Out_X(BiTree t, KeyType x, KeyType &a, KeyType &b,int &last)
{
 if(t->lchild) Out_X(t->lchild,x,a,b,last);
 if(last<x&&t->data.key>=x) a=last;
 if(last<=x&&t->data.key>x) b=t->data.key;
 last=t->data.key;
 if(t->rchild) Out_X(t->rchild,x,a,b,last);
 else if(last<x) a=last;
  }