查找算法复习——二叉排序树

    有关二叉排序树的定义是递归定义的。

    1）如果左子树是非空的，则左子树上所有结点的值都小于它的根结点的值；

    2）如果它的右子树是非空的，则右子树上所有结点的值均大于或者等于它的根结点的值；

    3）它的左右子树也分别是二叉排序树。

    如下是有关二叉排序树的创建、插入、查找的算法

#include <stdio.h>
#include <stdlib.h>

#define N 10

typedef struct node {
    int key;
    struct node *lchild, *rchild;
} BSTNode, *BSTtree;

void CreateBST(BSTtree *bst);
void InsertBST(BSTtree *bst, int key);
BSTtree SearchBST(BSTtree bst, int key);

int main()
{
    BSTtree bst;
    BSTtree res;

    CreateBST(&bst);
    res = SearchBST(bst, 122);
    if(res == NULL) {
        printf("not found\n");
        return 0;
    }
    printf("%d\n", res->key);
    return 0;
}

void CreateBST(BSTtree *bst)
{
    int a[N] = {122, 18, 23, 7, 98, 100, 10, 130, 155, 18};
    int i = 0;

    *bst = NULL;
    while(i != N) {
        InsertBST(bst, a[i]);
        i++;
    }
}

void InsertBST(BSTtree *bst, int key)
{
/*插入的递归算法*/
    /*
    BSTtree s;

    if(*bst == NULL) {
        s = (BSTtree)malloc(sizeof(BSTNode));
        s->key = key;
        s->lchild = NULL;
        s->rchild = NULL;
        *bst = s;
    } else if(key < (*bst)->key) {
        InsertBST(&(*bst)->lchild, key);
    } else if(key >= (*bst)->key) {
        InsertBST(&(*bst)->rchild, key);
    }
    */
/*插入的非递归算法*/

    BSTtree tmp, s;
    s = *bst;
    while(s != NULL) {
        if(key < s->key) {
            s = s->lchild;
        } else {
            s = s->rchild;
        }
    }
    tmp = (BSTtree)malloc(sizeof(BSTNode));
    tmp->key = key;
    tmp->lchild = NULL;
    tmp->rchild = NULL;
    s = tmp;
}

BSTtree SearchBST(BSTtree bst, int key)
{
/*查找的递归算法*/
    /*
    if(bst == NULL) {
        return NULL;
    } else if(bst->key == key) {
        return bst;
    } else {
        if(bst->key > key) {
            return SearchBST(bst->lchild, key);
        } else {
            return SearchBST(bst->rchild, key);
        }
    }
    */
    BSTtree q;

/*查找的非递归算法*/

    q = bst;
    while( NULL) {
        if(q->key == key) {
            break;
        } else if(q->key > key) {
            q = q->lchild;
        } else {
            q = q->rchild;
        }
    }
    return q;
}