首先何为二叉搜索树?
二叉查找树(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;}
测试截图