首先何为二叉搜索树？
二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。
二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).
结构体定义，为了方便起见，data用int型，读者可以自己更改成模板
struct BTNode { int data; BTNode *lchild,*rchild;};
这个没啥好解释的，就是树的结点标准定义，一个数据域，两个孩子指针
类定义
class BTree {private: BTNode *root; //二叉搜索树的根结点 void creat(int loc, BTNode *p); //创建二叉搜索树，递归形式创建，私有函数 void travel(BTNode *p); //用来遍历（中序），输出时候需要调用的 int *data, number; //这个是用来存储输入的数组，估计不需要了，下一个版本会删除 void search(int key, BTNode *p, bool &flag); //查找，其实这个查找方法和二分法类似 void insert(BTNode *p, int x); //插入函数public: BTree(int a[], int n); void Creat(); void Insert(int x); void Search(int key); void Print();}; 本代码采用封装方式，即具体对于root的操作全是由私有函数来进行的，一方面是安全另一方面是代码看起来很整洁
构造函数
BTree::BTree(int a[], int n){ int mid = a[0]; //把第一个数据作为二叉树的根结点的数值 root = new BTNode(); root->data = mid; root->lchild = root->rchild = NULL; number = n; data = new int[number]; for (int i = 0; i < number; i++) { data[i] = a[i]; }} 构造函数只有两个功能，一是创建根结点还有给类中自带的数组拷贝复制
数组有点多余，因为我当时是先写creat函数的，感觉creat调用的参数有点太多了所以就在类中添加了一个
完全没必要，直接删掉以后在构造函数中调用creat就行
查找函数
void BTree::search(int key, BTNode *p, bool &flag){ while (p) { if (p->data == key) //找到 { flag = true; break; } else if (p->data > key) //比结点的值小就向左找 { p = p->lchild; } else //比结点的值小就向左找 { p = p->rchild; } }} 和二分法查找类似，不再赘述
只不过因为查找这里不像前面静态查找中可以直接返回第几个，这里只加了一个flag来进行表示是否查找成功
可以把函数返回值该成BTNode* 即可返回地址
插入函数
void BTree::insert(BTNode *p, int x){ /*if (p==NULL) { p = new BTNode(); p->data = x; p->rchild = p->lchild = NULL; cout << "p->data" < data<< endl; } else if (x > p->data) { insert(p->rchild, x); } else if (x < p->data) { insert(p->lchild, x); }*/ //这个错误的原因很明显 if (x > p->data) { if (p->rchild == NULL) { p->rchild = new BTNode(); p->rchild->data = x; p->rchild->rchild = p->rchild->lchild = NULL; cout << p->rchild->data << "插入成功！" << endl; } else insert(p->rchild, x); } else if (x < p->data) { if (p->lchild == NULL) { p->lchild = new BTNode(); p->lchild->data = x; p->lchild->rchild = p->lchild->lchild = NULL; cout << p->lchild->data << "插入成功！" << endl; } else insert(p->lchild, x); } else { cout << "不可以插入已经存在于二叉搜索树中的元素！" << endl; }} 注释那一段可以想一想为什么添加失败/(ㄒoㄒ)/~~
调了半天才发现原来当p为空的时候再创建已经找不到它的双亲了（孤儿···）
所以虽然是添加成功了但是在打印族谱 啊 呸 二叉树的时候肯定找不到它了
因此要么你把双亲的地址提前记下来然后创建好再连接上去，要么就直接用p->lchild/p->rchild来创建
此处@陈总~感谢提供
删除功能
由于实验指导书中并没有要求删除这个功能，因此这里只给出思想，感兴趣的可以自行回去完善。
二叉查找树的删除，分三种情况进行处理：
1.p为叶子节点，直接删除该节点，再修改其父节点的指针（注意分是根节点和不是根节点）
2.p为单支节点（即只有左子树或右子树）。让p的子树与p的父亲节点相连，删除p即可；（注意分是根节点和不是根节点）
3.p的左子树和右子树均不空。找到p的后继y，因为y一定没有左子树，所以可以删除y，并让y的父亲节点成为y的右子树的父亲节点，并用y的值代替p的值；或者方法二是找到p的前驱x，x一定没有右子树，所以可以删除x，并让x的父亲节点成为y的左子树的父亲节点
具体可以参考：
完整代码（头文件自己选择添加或者把这个放在头文件里都行）
struct BTNode { int data; BTNode *lchild,*rchild;};class BTree {private: BTNode *root; //二叉搜索树的根结点 void creat(int loc, BTNode *p); //创建二叉搜索树，递归形式创建，私有函数 void travel(BTNode *p); //用来遍历（中序），输出时候需要调用的 int *data, number; //这个是用来存储输入的数组，估计不需要了，下一个版本会删除 void search(int key, BTNode *p, bool &flag); //查找，其实这个查找方法和二分法类似 void insert(BTNode *p, int x); //插入函数public: BTree(int a[], int n); void Creat(); void Insert(int x); void Search(int key); void Print();};void BTree::creat(int loc, BTNode * p){ if (data[loc] > p->data) //判断要输入的值是比结点值大还是小，大向右，小向左 { if (p->rchild == NULL)//然后再判断，如果比结点值大且右孩子为空就创建 { p->rchild = new BTNode(); p->rchild->data = data[loc]; p->rchild->lchild = p->rchild->rchild = NULL; } else //不为空就继续进行判断比较，递归 { creat(loc, p->rchild); } } else if (data[loc] < p->data)//同理 { if (p->lchild == NULL) { p->lchild = new BTNode(); p->lchild->data = data[loc]; p->lchild->lchild = p->lchild->rchild = NULL; } else { creat(loc, p->lchild); } }}void BTree::travel(BTNode * p){ //中序遍历，左根右 if (p != NULL) { travel(p->lchild);//先左 cout << p->data << " ";//根 travel(p->rchild);//后右 }}void BTree::search(int key, BTNode *p, bool &flag){ while (p) { if (p->data == key) //找到 { flag = true; break; } else if (p->data > key) //比结点的值小就向左找 { p = p->lchild; } else //比结点的值小就向左找 { p = p->rchild; } }}void BTree::insert(BTNode *p, int x){ /*if (p==NULL) { p = new BTNode(); p->data = x; p->rchild = p->lchild = NULL; cout << "p->data" < data<< endl; } else if (x > p->data) { insert(p->rchild, x); } else if (x < p->data) { insert(p->lchild, x); }*/ //这个错误的原因很明显 if (x > p->data) { if (p->rchild == NULL) { p->rchild = new BTNode(); p->rchild->data = x; p->rchild->rchild = p->rchild->lchild = NULL; cout << p->rchild->data << "插入成功！" << endl; } else insert(p->rchild, x); } else if (x < p->data) { if (p->lchild == NULL) { p->lchild = new BTNode(); p->lchild->data = x; p->lchild->rchild = p->lchild->lchild = NULL; cout << p->lchild->data << "插入成功！" << endl; } else insert(p->lchild, x); } else { cout << "不可以插入已经存在于二叉搜索树中的元素！" << endl; }}BTree::BTree(int a[], int n){ int mid = a[0]; //把第一个数据作为二叉树的根结点的数值 root = new BTNode(); root->data = mid; root->lchild = root->rchild = NULL; number = n; data = new int[number]; for (int i = 0; i < number; i++) { data[i] = a[i]; //创建这个数组个人觉得有点多余，其实可以直接在构造函数里完成 //自己改一下吧，直接在构造函数里调用creat，参数需要调整一下 }}void BTree::Insert(int x){ BTNode *p = root; insert(p, x); //这里可以把insert函数增加一个参数bool类型来判断是否真的是插入成功了 //插入成功会有提示，失败不会打印插入成功的消息}void BTree::Search(int key){ //此函数对应私有函数没有返回值，可以自己更改，把地址取出来（目前没有用所以我只是做了一个简单的判断） BTNode *p = root; bool flag = false; search(key, p, flag); if (flag) { cout << "搜索到" << key << "在二叉树中" << endl; } else { cout << "未查找到指定数据！" << endl; }}void BTree::Print(){ BTNode *p = root; travel(p); cout << endl;}void BTree::Creat(){ BTNode *p = root; for (int i = 1; i < number; i++) //从1开始是因为root在构造函数中已经被赋值了 { creat(i, p); } cout << "二叉搜索树创建成功了。。。吧" << endl; } 主函数代码
int main(){ cout << "请输入二叉搜索树的元素个数:"; int number, *a, key, x; cin >> number; a = new int[number]; cout << "请分别为这些元素赋值:" << endl; for (int i = 0; i < number; i++) { cin >> a[i]; } BTree test(a, number); test.Creat(); test.Print(); cout << "请输入要查找的数值" << endl; cin >> key; test.Search(key); cout << "请输入要插入的数值" << endl; cin >> x; test.Insert(x); test.Print(); system("pause"); return 0;} 测试截图
