1. 二叉排序树的数据结构本质上和普通二叉树没有区别，只不过在创建时需要额外加上一层约束条件，使结点按照“左子树的值都比根节点小，右子树的值都比根节点大”的规则来插入。

2.对二叉排序树的结点插入、中序遍历、查找结点等算法都用到了递归，十分方便。唯一注意的就是在执行创建BST时，要调用插入结点的算法，不算是递归，但也和递归差不多。

上代码

#include <iostream>
using namespace std;typedef int KeyType;//二叉排序树的结构体定义
typedef struct BSTNode { KeyType data; //数据域struct BSTNode* lchild, * rchild; //二叉排序树中的左子树和右子树
}BSTNode,*BSTree;//二叉排序树插入节点算法 递归
void BSTNodeInsert(BSTree &T, KeyType key) { if (key < T->data) { //走左子树if (T->lchild == NULL) { //如果左子树为空 则直接赋值给左子树T->lchild = new BSTNode;T->lchild->data = key;T->lchild->lchild = NULL;T->lchild->rchild = NULL;}else { //如果左子树不为空 则递归继续找左子树BSTNodeInsert(T->lchild, key);}}else { //当key比根节点的值大时 找右子树if (T->rchild == NULL) { //如果右子树为空 直接赋值T->rchild = new BSTNode;T->rchild->data = key;T->rchild->lchild = NULL;T->rchild->rchild = NULL;}else { //否则继续递归找右子树BSTNodeInsert(T->rchild, key);}}
}//创建二叉排序树算法
void CreatBSTree(BSTree& T) { T = new BSTNode;T->lchild = NULL;T->rchild = NULL;int i;cin >> i; //输入序列值if (i != -1) { //初始化操作，给根节点赋初值T->data = i; }while (i != -1) {cin >> i;if (i != -1) //双重判断 不然-1会加进序列BSTNodeInsert(T, i);}cout << "创建成功！" << endl;
}//递归打印创建好的二叉排序树
void PrintBSTree(BSTree T) { //采用中序遍历 可以得到从小到大的有序序列if (T != NULL) {PrintBSTree(T->lchild);cout << T->data << " ";PrintBSTree(T->rchild);}
}//二叉排序树的递归查找算法
int SearchBSTree(BSTree T, int key) {if (T == NULL)return 0;if (T->data == key)return 1;if (key < T->data)SearchBSTree(T->lchild, key);elseSearchBSTree(T->rchild, key);
}int main() {BSTree T;cout << "请输入序列：(以-1为结束数)" << endl;CreatBSTree(T);cout << "创建好的二叉排序树中序遍历结果为：" << endl;PrintBSTree(T);cout << endl;int i;cout << "请输入要查找的数字：" << endl;cin >> i;if (SearchBSTree(T, i) == 0)cout << "查找失败！该序列中没有此数！" << endl;if (SearchBSTree(T, i) == 1)cout << "查找成功！该序列中存在此数！" << endl;
}