二叉排序树的基本操作

二叉排序树定义

typedef struct BTNode {
    int val;
    struct BTNode *lchild;
    struct BTNode *rchild;
} BSTNode, *BiTree;

查找

BTNode *BST_Search(BiTree T, int key, BTNode *p) {
    p = NULL;
    while(key < T->val && key != T->val) {
        p = T;
        if(key < T->val)  T = T->lchild;
        else T = T->rchild;
    }
    return T;
}

插入

int BST_Insert(BiTree &T, int k) {
    if(T == NULL) {                 //原树为空，新插入的记录为根结点
        T = (BiTree)malloc(sizeof(BTNode));
        T->val = k;
        T->lchild = T->rchild = NULL;
        return 1;
    } else if(k == T->val)
        return 0;
    else if(k < T->val)
        return BST_Insert(T->lchild, k);
    else
        return BST_Insert(T->rchild, k);
}

构造

void Create_BST(BiTree &T, int *A, int n) {
    T = NULL;
    for(int i = 0; i < n; i++) {
        BST_Insert(T, A[i]);
    }
}