9.33.c

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

9.33③ 编写递归算法，从大到小输出给定二叉排序树
中所有关键字不小于x的数据元素。要求你的算法的时
间复杂度为O(log2n+m)，其中n为排序树中所含结点数，
m为输出的关键字个数。

实现下列函数：
void OrderOut(BiTree t, KeyType x, void(*visit)(TElemType));
/* Output is to use visit(t->data);  */

二叉树的类型BiTree定义如下：
typedef struct {
    KeyType key;  
    ... ...   // 其他数据域
} ElemType;

typedef struct BiTNode {
    ElemType data;
    BiTNode  *lchild,*rchild;
}BiTNode, *BiTree;
void out(BiTree t,KeyType x,int &flag,void(*visit)(TElemType));
void OrderOut(BiTree t, KeyType x, void(*visit)(TElemType))
/* Output is to use visit(t->data);  */
{
 int flag=1;
 out(t,x,flag,visit);
}
void out(BiTree t,KeyType x,int &flag,void(*visit)(TElemType))
{
 if(t->rchild) out(t->rchild,x,flag,visit);
 if(t->data.key<x) flag=0;
 if(flag)
   {visit(t->data);
    if(t->lchild)out(t->lchild,x,flag,visit);
    }
}