#include 
#define QUEUE_MAX_SIZE 20
#define STACK_MAX_SIZE 10
typedef int elemType;
#include "BT.c"
/************************************************************************/
/*                    以下是关于二叉搜索树操作的4个简单算法               */
/************************************************************************/

/* 1.查找 */
/* 递归算法 */
elemType *findBSTree1(struct BTreeNode *bst, elemType x)
{
/* 树为空则返回NULL */
if (bst == NULL){
return NULL;
}else{
if (x == bst->data){
return &(bst->data);
}else{
if (x < bst->data){    /* 向左子树查找并直接返回 */
return findBSTree1(bst->left, x);
}else{        /* 向右子树查找并直接返回 */
return findBSTree1(bst->right, x);
}
}
}
}
/* 非递归算法 */
elemType *findBSTree2(struct BTreeNode *bst, elemType x)
{
while (bst != NULL){
if (x == bst->data){
return &(bst->data);
}else if (x < bst->data){
bst = bst->left;
}else{
bst = bst->right;
}
}
return NULL;
}

/* 2.插入 */
/* 递归算法 */
void insertBSTree1(struct BTreeNode* *bst, elemType x)
{
/* 新建一个根结点 */
if (*bst == NULL){
struct BTreeNode *p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
p->data = x;
p->left = p->right = NULL;
*bst = p;
return;
}else if (x < (*bst)->data){        /* 向左子树完成插入运算 */
insertBSTree1(&((*bst)->left), x);
}else{        /* 向右子树完成插入运算 */
insertBSTree1(&((*bst)->right), x);
}
}

/* 非递归算法 */
void insertBSTree2(struct BTreeNode* *bst, elemType x)
{
struct BTreeNode *p;
struct BTreeNode *t = *bst, *parent = NULL;
/* 为待插入的元素查找插入位置 */
while (t != NULL){
parent = t;
if (x < t->data){
t = t->left;
}else{
t = t->right;
}
}
/* 建立值为x，左右指针域为空的新结点 */
p = (struct BTreeNode *)malloc(sizeof(struct BTreeNode));
p->data = x;
p->left = p->right = NULL;
/* 将新结点链接到指针为空的位置 */
if (parent == NULL){
*bst = p;        /* 作为根结点插入 */
}else i