考研数据结构（每日一题）day47

考研数据结构（每日一题）

题目：

1. 设计一个算法，求出给定二叉排序树中最小和最大的关键字
2. 设计一个算法，从大到小输出二叉排序树中所有值不小于k的关键字

算法思想：

在二叉排序树中，最左下结点即为关键字最小的结点，最右下结点即为关键字最大的结点。本算法只要找出这两个结点即可，不需要比较关键字。

由二叉树排序树的性质可知，右子树中所有的结点值均大于根结点值，左子树中所有的结点值均小于根结点值。为了从大到小输出，先遍历右子树，在访问根结点，后遍历右子树。

完整代码：

KeyType MinKey(BSTNode *bt){
    while (bt -> lchild != NULL)
    {
        bt = bt -> lchild;
    }
    return bt -> data;
}
KeyType MaxKey(BSTNode *bt){
    while (bt -> rchild != NULL)
    {
        bt = bt -> rchild;
    }
    return bt -> data;
}

void OutPut(BSTNode *bt,KetType k){
    if (bt == NULL)
    {
        retrn;
    }
    if (bt -> rchild != NULL)
    {
        OutPut(bt -> rchild,k);  //递归输出右子树结点
    }
    if (bt -> data >= k)
    {
        printf("%d",bt -> data);  //只输出大于等于k的结点
    }
    if (bt -> lchild != NULL)
    {
        OutPut(bt -> lchild,k);   //递归输出右子树结点
    }
}