#include<iostream>
#include<vector>
using namespace std;
const int N=100;
struct TreeNode
{
int val;//存值
int left;//左子树
int right;//右子树
int parent;//双亲
TreeNode() : val(0),left(-1),right(-1){}//无参构造函数
TreeNode(int x) : val(x),left(-1),right(-1){}//有参构造函数
};
TreeNode tree[N];//存树
int nextidx=0;//指向下一个节点的索引
//构造树
int insert(int parent,int root,int val)
{
if(root==-1)//判断root是否等于-1,如果等于-1就说明已经找到叶子节点了
{
tree[nextidx]=TreeNode(val);//把当前要插入的节点插入到数组中
tree[nextidx].parent=parent;
return nextidx++;//返回当前节点的索引,然后把nextidx++
}
if(val<=tree[root].val)//判断当前要插入的节点是否小于根节点
tree[root].left=insert(root,tree[root].left,val);//插入到左子树,并更新左子树的索引
else
tree[root].right=insert(root,tree[root].right,val);//插入到右子树,并更新右子树的索引
return root;//返回根节点的索引
}
//打印输出
void printTree(int root,int n)
{
//输出提示语
cout << "idx\t" << "val\t" << "parent\t" << "left\t" << "right\n";
for(int i=0;i<n;i++)//循环输出
cout << i << "\t" << tree[i].val << "\t" << tree[i].parent << "\t" << tree[i].left << "\t" << tree[i].right << '\n';
}
//中序遍历二叉搜索树
void inoder(int root)
{
if(root==-1)//等于-1就返回
return;
inoder(tree[root].left);//递归调用左子树
cout << tree[root].val << " ";//输出当前节点的值
inoder(tree[root].right);//递归调用右子树
}
//查找节点的函数
bool search(int root,int val)
{
if(root==-1)//判断root是否等于-1,等于-1说明没找到
return false;//返回false
if(val==tree[root].val)//判断当前节点的值是否等于要查找的值
return true;//返回true
else if(val<tree[root].val)//判断当前节点的值是否小于要查找的值
return search(tree[root].left,val);//递归调用左子树
else
return search(tree[root].right,val);//递归调用右子树
}
int findMid(int root)
{
while(tree[root].left!=-1)
root=tree[root].left;
return root;
}
//删除某个节点
int remove(int root,int val)
{
if(root==-1)//判断root是否等于-1
return -1;//返回-1
if(val<tree[root].val)//判断要删的值是否小于当前的值
tree[root].left=remove(tree[root].left,val);//递归在左子树中删除节点,并更新左子树的索引
else if(val>tree[root].val)//判断要删的值是否大于当前的值
tree[root].right=remove(tree[root].right,val);//递归在右子树中删除节点,并更新右子树的索引
else
{
//情况1:要删的节点是叶节点,就直接返回-1
if(tree[root].left==-1 && tree[root].right==-1)
return -1;
//情况2:要删的节点只有一个孩子,如果只有左子树就用左子树顶替要删的那个节点,右子树同理
else if(tree[root].left==-1)
return tree[root].right;
else if(tree[root].right==-1)
return tree[root].left;
//情况3:要删的节点左右子树都有,从右子树中选择最小的节点去覆盖要删的节点。
//然后递归在右子树中删除之前找到的最小的节点,并更新右子树的索引
else
{
int minMid=findMid(tree[root].right);
tree[root].val=tree[minMid].val;
tree[root].right=remove(tree[root].right,tree[minMid].val);
}
}
return root;//返回当前根节点的索引
}
int main()
{
int root=-1;//初始化根节点为-1
vector<int> values = {5, 3, 7, 2, 5, 4, 6, 8}; // 待插入的值的数组
for(int val:values)//循环调用递归
root=insert(-1,root,val);//递归调用
printTree(root,values.size());//打印输出
inoder(root);//中序遍历
// cout << "\n请输入待查找元素:";
int n;
// cin >> n;
// if(search(root,n))
// cout << "找到";
// else
// cout << "未找到";
cout << "\n请输入要删除的元素:";
cin >> n;
root=remove(root,n);
//cout << "****";
printTree(root,8);
inoder(root);
return 0;
}