#include<iostream>
#include<vector>
using namespace std;
const int N = 100;//数组的大小最多是100
//定义二叉搜索树节点结构体
struct TreeNode
{
    int l;//左子树
    int r;//右子树
    int val;//节点存储的值
    int p;//双亲节点
    TreeNode() : l(-1), r(-1), val(0) {}//无参数构造函数
    TreeNode(int x) : l(-1), r(-1), val(x) {}//有一个参数的构造函数
};
TreeNode tree[N];
int nextIndex = 0;//下一个新节点位置
//插入节点的函数，返回插入节点后形成的新树的树根节点的索引
int insert(int root, int val, int pr)
{
    if(root == -1)//还没有根节点
    {

        tree[nextIndex] = TreeNode(val);//创建新节点
        tree[nextIndex].p = pr;
        return nextIndex++;//返回根节点的索引后将下一个新节点位置+1
    }
    if(val <= tree[root].val)//如果新插入的节点的值<=当前节点的值
        tree[root].l = insert(tree[root].l, val, root);//递归左子树
    else//新插入的节点的值>当前节点的值
        tree[root].r = insert(tree[root].r, val, root);//递归右子树
    return root;//返回根节点
}
vector<int> values = {5, 3, 7, 2, 5, 4, 6, 8};//输入数据
void printtree(int root)
{
    printf("sy\tval\tl\tr\tp\n");
    for(int i=root; i<values.size(); i++)
        printf("%d\t%d\t%d\t%d\t%d\n", i, tree[i].val, tree[i].l, tree[i].r, tree[i].p);
}
//中序遍历二叉查找数
void inorder(int root)
{
    if(root == -1)//如果当前节点是叶子节点
        return;//返回
    inorder(tree[root].l);//递归左子树
    cout << tree[root].val << " ";//输出当前节点的值
    inorder(tree[root].r);//递归右子树
}
//查找节点，判断是否存在该节点
bool search(int root, int val)
{
    if(root == -1)//根节点为空
        return false;//直接返回false
    if(tree[root].val == val)//当前节点就是要查找的节点
        return true;//返回true，表示找到了
    else if(val < tree[root].val)//如果要查找的值<当前节点的值
        search(tree[root].l, val);//递归查找左子树
    else//要查找的值>当前节点的值
        search(tree[root].r, val);//递归查找右子树
}
//找最小的值的节点索引
int findMin(int root)
{
    while(tree[root].l != -1)//左子树不为空就一直向左遍历
        root = tree[root].l;//索引等于tree[root]的左子树索引
    return root;//返回最小的值的节点索引
}
//删除节点
int remove(int root, int val)
{
    if(root == -1)//根节点为空
        return root;//返回-1
    if(val < tree[root].val)//要删除的节点<当前节点
        tree[root].l = remove(tree[root].l, val);//递归当前节点的左子树
    else if(val > tree[root].val)//要删除的节点>当前节点
        tree[root].r = remove(tree[root].r, val);//递归当前节点的右子树
    else//当前节点就是要删除的节点
    {
        //情况1：要删除的节点是叶子节点
        if(tree[root].l==-1 && tree[root].r==-1)
            return -1;//返回-1
        //情况2：要删除的的节点只有左子树或只有右子树
        else if(tree[root].l==-1)
            return tree[root].r;//返回要删除的的节点的右子树
        else if(tree[root].r==-1)
            return tree[root].l;//返回要删除的的节点的左子树
        int minn = findMin(tree[root].r);//找到右子树中的最小值的索引
        tree[root].val = tree[minn].val;//将值最小的节点的值赋值给要删除的节点的值
        tree[root].r = remove(tree[root].r, tree[minn].val);//递归删除右子树中值最小的节点
    }
    return root;//返回根节点的索引
}
int main()
{
    int root = -1;//根节点的索引
    for(int val : values)//构造二叉搜索树
        root = insert(root, val, -1);//插入值为val的节点
    printtree(root);
    cout << "中序遍历:\n";
    inorder(root);//输出二叉查找树的中序遍历
    cout << '\n';//换行
    int searchVal = 4;//要查找的值
    if(search(root, searchVal))//判断是否有searchVal
        cout << "找到了\n";
    else
        cout << "未找到\n";
    int removeVal = 5;//要删除的值
    root = remove(root, removeVal);//删除removeVal
    cout << "删除 " << removeVal << " 后的中序遍历结果：";//输出删除removeVal后的结果
    inorder(root);//中序遍历
    cout << '\n';//换行
    return 0;
}