用C语言实现二叉排序树查找小于关键字key的最大节点的函数

Question

用C语言实现。
数据结构如下：

typedef struct TreeNode
{
    int Key;
    struct TreeNode *LChlid,*RChlid;
}TreeNode;

以知二叉树有如下特点：左节点数值小于根节点，右节点数值大于根节点，既是一棵二叉排序树。
现在要求编写一个函数TreeNode* Find(TreeNode *root,int key)，在二叉树中找到小于key的最大节点，如果能找到则直接返回该节点，如果不能，则返回NULL。要求Find函数不能调用其它函数，但可以递归调用自身。

Answer 1

提供一个简单的思路。

    template<typename T>
    Node* find(Node* root,T Key){
        if(root == NULL)
            return NULL;
        if(root.val >= key){
            return find(root.left, key);
        }else{
            Node * tmp = find(root.right, key);
            if(tmp == NULL){
                return root;
            }else{
                return tmp;
            }
        }
    }

思路很简单，看代码远比我赘述要轻松，如果不会，可以追问。

Answer 2

用二叉排序数的中序遍历。
该题参考严蔚敏习题集上的一道例题：已知一棵二叉排序树上所有关键字中的最小值为-max，最大值为max，又-max<x<max。编写具有如下功能的函数：求该二叉树上小于x且最靠近x的值a和大于x且最靠近x的b。

int last=0;
void MaxLT_MinGT(BiTree T,int x)//找到二叉排序树T中小于x的最大元素和大于x的最小元素
{
  if(T->lchild) MaxLT_MinGT(T->lchild,x); //本算法仍是借助中序遍历来实现
  if(last<x&&T->data>=x) //找到了小于x的最大元素
    printf("a=%d\n",last);
  if(last<=x&&T->data>x) //找到了大于x的最小元素
    printf("b=%d\n",T->data);
  last=T->data;
  if(T->rchild) MaxLT_MinGT(T->rchild,x);
}//MaxLT_MinGT

中心思想是一样的，只是他的last是数值，你需要的是地址。

Answer 3

今天有点时间, 根据我下面的想法写了代码.

node_t* 
find(node_t* t, int k)
{
        if(t == NULL)
                return NULL;

        /* t1 is used to record the parent of the last node 
         * which is right child of its parent 
         */
        t1 = NULL; 

        do{
                if(k < t->v)
                        t = t->l;
                else if(k = t->v)
                        break;
                else{
                       t1 = t;
                       t = t->r;
                }
        }while(t != NULL);

        if(t == NULL || t->l == NULL)
                return t1;

        /* max(t->l) */
        t = t->l;
        while(t->r != NULL)
                t = t->r;
        return t;
}

---

以前的答案

遍历的话, 时间复杂度O(n). 这里有O(lgn)的方法.

就是求 bst的 某节点的 前驱.查询bst, 如果找到 key的节点, 查此节点的前驱; 否则, 可以知道此key 应该插入的节点位置, 查此位置的前驱.

求bst节点 n的 前驱:

1. 如果左子树不为null, 则前驱为 max(n->left);
2. 否则, 递归n的 父节点p; 如果p为根节点, 则前驱为 根节点;
3. 否则, 如果p为其父节点的右节点, 则前驱为 p;
4. 否则, p = p->p; 重复step2-4.

如果bst节点是有父节点信息的. 很简单:

node_t* 
max(node_t* r)
{
        while(r->r != NULL)
                r = r->r;
        return r;
}

node_t* 
predecessor(node_t* r)
{
        if(r->l != NULL)
                return max(r->l);
        node_t *p = r->p;
        while(p != NULL && r != p->r){
                r = p;
                p = p->p;
        }
        return p;
}

这里时间O(lgn).

没有父节点信息, 则需要辅助内存. 这里可以用一个 辅助栈 把bst查询 的路径节点都记录下来, 然后就可以 像上述算法一样, 递归查询节点的 父节点了. 时间O(lgn), 空间O(lgn).

当然我们还可以在bst查询时, 记录下其 路径上的 最后一个 "为其父节点的右节点的节点", 这样时间O(lgn), 空间O(1).

Answer 4

TreeNode* Find(TreeNode *root,int key)
{
    if(root == NULL)
        return NULL;

    TreeNode *node;
    if(root->Key >= key)
    {
        if(root->LChlid == NULL)
            return NULL;
        else
        {
            node = root->LChlid;
            while(node->RChlid)
            {
                node = node->RChlid;
            }
            if(node->Key < key)
                return node;
        }
        return Find(root->LChlid,key);
    }
    else
    {
        if(root->RChlid == NULL)
            return root;
        else
        {
            node = root->RChlid;
            while(node->LChlid)
            {
                node = node->LChlid;
            }
            if(node->Key >= key)
                return root;
        }
        return Find(root->RChlid,key);
    }
}

这是我参考回答写出来的代码。在此谢谢每一个热情帮助我的人。