二叉查找树
二叉查找树非递归查找
BSTNode *BST_Search(BiTree T, ElemType key, BiTNode *&p) {
//查找函数返回指向关键字值为key的结点指针,若不存在,返回 NULL
p = NULL;//p指向被查找结点的双亲结点,用于插入删除操作
while (T != NULL && key != T->data) {
p = T;
if (key < T->data)
T = T->lchild;
else
T = T->rchild;
}
return T;
}

二叉查找树插入
int BST_Insert(BiTree &T, KeyType k) {
//在二叉排序树T中插入一个关键字为k的结点
if (T == NULL) { //原树为空,新插入的记录为根结点
T = (BiTree)malloc(sizeof(BSTNode));
T->key = k;
T->lchild = T->rchild = NULL;
return 1; //返回1,表示成功
}
else if (k == T->key) //树中存在相同关键字的结点
return 0;
else if (k < T->key) //插入到T的左子树中
return BST_Insert(T->lchild, k);
else //插入到T的右子树中
return BST_Insert(T->rchild, k);
}

二叉排序树构造
void Creat_BST(BiTree &T, KeyType str[], int n) {
//用关键字数组str[]建立一个二叉排序树
T = NULL; //初始时bt为空树
int i = 0;
while (i < n){ //依次将每个元素插入
BST_Insert(T, str[i]);
i++;
}
}