二叉排序树的定义如下：
二叉排序树定义 ——摘自百度百科
简单的来讲，就是对一个一个结点来讲，左子树比他小，右子树比他大。这样的树就是一颗二叉排序树。
例如：下面的数组组成的二叉排序树是什么？
28,5,4,16,3,1,29,19,17
可以看到 对于任意一个结点来讲，它的左子树上的所有数都比它小，右子树上的所有值都比它大。
对于二叉排序树来讲。主要有以下的几种常用的操作。
- 插入操作
- 删除操作
-
寻找一个值
其中比较麻烦的就是删除操作；删除要分为两种情况
删除后的树也应该是二叉排序树，也就是满足二叉排序树的要求。
1:若是删除的这个结点为叶子结点。那就直接删除，若是这个结点为左子树，那就将父结点的左子树设置为NULL。反之，亦然。删除上面例子中结点1，之后的树的结构如下图：
image.png
2：若是删除的这个结点只有左子树，没有右子树，，这样的删除就需要找一个结点来比要删除的结点小一点的值。那这个结点就是要删的结点的左子树的，如果要删除的是 上面例子中的3 那替代它的就是结点1.
3:删除的这个结点有右子树。又要分为两种情况：
a：要删除的结点的右子树没有左子树。那替代的结点就是要删的结点的右子树，
要删除5:树的示意图如下：
b：：要删除的结点的右子树有左子树。那替代的结点就是要删的结点的右子的最后一个左子树；
如下图所示的二叉排序树，要删除5，得到新的结点如下；
（未删除5的二叉排序树）
（删除之后的二叉排序树）
在这个例子中，删除的结点是5，找到替代的结点是10
<h3>在这里用递归的方法来创建树，查询，删除</h3>
代码如下
//
// main.cpp
// 二叉排序树
//
// Created by 刘晨 on 2018/12/19.
// Copyright © 2018 刘晨. All rights reserved.
//
/*
二叉排序树就是根节点的左子树比他小，右子树比他大；
注意： ******************************************************
指针的指向要规定好，不能让指针乱指，这样会造成没有必要的麻烦。有的时候，逻辑上没有问题，但是就是输出有问题，那可能就是指针指向有问题，比如我遇到的问题如下：
1；首先就是在删除5这个结点的时候，逻辑上没有问题，结果输出一直在1，3，4，10，中循环，问题就是出现在findMIn中父结点的指向有问题，删除这个结点之后没有设置为NULL，从而就导致了这样的问题。
*/
include <iostream>
using namespace std;
typedef struct node{
int data;
node* rchild;
node* lchild;
}node;
class Tree{
private:
node * head;//树的头结点
node * seachx(node * t,int data);//私有递归的查询
void insertx(node *& t,int data);//私有递归的插入;
void inorder(nodep);// 中序遍历
node findMin(nodep,nodeparent);//找删除的结点的左子树中的最大值,参数一，从那个结点开始，参数二，这个结点的父结点
bool isLeaf(node *p);//看是不是叶子结点
bool deleteNode(node parnet,nodep,int data,int direction);//私有删除结点 参数一，从那个结点开始，参数二，这个结点的父结点，参数三 要删除的数据，参数四，位于哪个子树，左子树用1表示，右子树用0来表示。
bool isHaveLeftChild(node *p);
public:
void searchTree(int data);//公有函数调用私有插入，寻找结点
void inserTree(int *a,int length);//参数一：将数组传进来，参数二，数组的长度；。。插入结点。
void deleteTree(int data);//删除结点.
void inorderTree();
Tree();
};
bool Tree::isHaveLeftChild(node *p){
if(p ->lchild != NULL && p->rchild ==NULL){
return true;
}
return false;
}
Tree::Tree(){
head = NULL;
}
/*
寻找就是便利二叉树，寻找
/
node Tree:: seachx(node t , int data ){
if (t == NULL) {
return NULL;
}
else{
if(t->data == data) return t;
if(t->data < data) t = seachx(t->rchild, data);
if(t->data > data) t = seachx(t->lchild, data);
}
return t;
}
/
插入其实就是不断的插入叶子结点，先找到叶子结点之后再创建结点，然后插入，大的放在右边，小的放在左边。
参数一是引用的指针，这就就不需要返回值。直接就相连了。
*/
void Tree::insertx(node *&t , int data ){
if(t == NULL){
t = new node;
t->lchild = t->rchild = NULL;
t->data = data;
}
else{
if (t->data <data) insertx(t->rchild, data);
if (t -> data > data) insertx(t->lchild, data);
}
}
void Tree::searchTree(int data){
nodep = head;
p = seachx(p, data);
cout<<p<<endl;
cout<<p->data;
}
void Tree::inserTree(int a,int length){
for (int i =0; i<length; i++) {
insertx(head, a[i] );
}
}
void Tree::inorder(node p){
if (p == NULL){
return;
}
else{
inorder(p->lchild);
cout<<p->data<<"\n";
inorder(p->rchild);
}
}
void Tree::inorderTree(){
nodep = head;
inorder(p);
}
node* Tree::findMin(node p,nodeparent){
cout<<p->data<<":"<<parent->data<<endl;
if(p->lchild == NULL){
//即就是找到了这个结点，然后将父结点的左子树设置为NULL
parent->lchild=NULL;
return p;
}
else{
//否则就继续找
p = findMin(p->lchild, p);
}
return p;
}
bool Tree::isLeaf(node *p){
if(p->lchild == NULL && p->rchild == NULL){
return true;
}
return false;
}
/*
返回值为bool是为了，判断有没有找到，要是左子树没有找到就继续去找右子树。
*/
bool Tree::deleteNode(node parnet,nodep,int data,int diretcion){
if (p == NULL) {
//设置终止条件。
return false;
}
else{
cout<<"parent"<<parnet->data<<endl;
cout<<"delete NOde "<<p->data<<endl;
if(p->data == data){
if(isLeaf( p) == true){
// 这个结点是叶子结点
if(diretcion == 1) {
//左边
parnet->lchild = NULL;delete p;
}
if(diretcion == 0) {
//右边
parnet->rchild = NULL;delete p;
}
}
if(isHaveLeftChild(p) == true){
//只有左子树
if(diretcion == 1) {
parnet->lchild = p->lchild;delete p;
}
if(diretcion == 0) {
parnet->rchild = p->lchild;delete p;
}
}
else {
//有右子树
node *t = findMin(p->rchild,p->rchild);//找到最替换的结点
cout<<t->data<<endl;
cout<<parnet->data<<endl;
if(diretcion == 1) {
if(p->rchild->lchild == NULL){
//删除的结点的右子树的左子树 没有。
parnet->lchild = t;
cout<<p->data<<endl;
t->rchild= p->rchild->rchild;
t->lchild = p->lchild;
delete p;
}
else{
//要删除的结点的右子树有左子树。
parnet->lchild = t;
cout<<p->data<<endl;
cout<<p->rchild->data<<endl;
t->rchild= p->rchild;
t->lchild = p->lchild;
delete p;
}
}
if(diretcion == 0) {
if(p->rchild->lchild == NULL){
parnet->rchild = t;
t->rchild= p->rchild->rchild;
t->lchild = p->lchild;
delete p;
}
else{
parnet->rchild = t;
t->lchild = p->lchild;
t->rchild = p->rchild;
delete p;
}
}
}
}
if( data > p->data){
deleteNode(p, p->rchild, data, 0);
}
if(data < p->data){
deleteNode(p, p->lchild, data, 1);
}
return true;
}
}
void Tree::deleteTree(int data){
if (true == deleteNode(head, head, data, 1)){
return;
}
else{
deleteNode(head, head, data, 1);
}
}
int main(){
Tree a ;
int b[] = {28,5,4,16,3,1,29,19,17};
a.inserTree(b,9);
a.inorderTree();
a.searchTree(1);
a.deleteTree(3);
cout<<"删除后的结点如下：\n";
a.inorderTree();
cout<<endl;
return 1;
}
测试的图就是上面提到的图。
二叉排序树——码云地址
