K——巨斧砍大树（二叉树操作）

日期：2023-09-30 04:06

描述

阿福最近掌握了一个新动作：用巨斧砍倒大树。这一举动可以砍掉二叉搜索树的某个子树。现在，Afu 有一棵二叉搜索树，前面有 nn 个节点。他要使用mm招式，所以他想问你每次使用“巨斧砍大树”时，二叉搜索树会是什么样子。。

二叉搜索树要么是空树，要么是具有以下性质的二叉树：如果它的左子树不为空，那么左子树上所有节点的值都小于它的根的值节点 ;如果其右子树不为空，则右子树上所有节点的值都大于其根节点的值；它的左子树和右子树也分别是二叉搜索树。

输入

在第一行输入 2 个整数 n, m (1⩽n,m⩽10)。表示二叉搜索树中的节点数和使用的移动次数。

在第二行中输入n个空格分隔的整数v(1⩽v⩽10)，表示二叉搜索树是将此序列按顺序插入生成的二叉树（保证彼此不同）。

接下来，输入mm行，每行包含一个整数w（1⩽w⩽10），这意味着Afu要砍掉节点上值为w的子树（确保w是存在于初始二叉树）。

输出

对于每一次树切割，如果子树切割成功，首先会输出一行Cut x，其中xx是切割子树的根节点上的值。如果要切割的节点之前已经被切割过，则输出一行Already cut x，xx的含义同上。

然后输出一行，表示砍树完成后当前二叉树的中序遍历结果，中间用空格分隔（行尾没有多余的空格，如果整个二叉树为空，输出一个空行）。

样品

输入

输出

切5
1 2 3 4
切2
134
切3
1
已经剪了4
1
切1

答案：

#包括 
#包括
#定义长长长
const int N = 1e5+10;
使用 命名空间 std;结构树
{int数据;树*l,*r;
};布尔标志;树*构建树(树*根,int k) //建树{if(!根){根 =新树;root->数据=k;root ->l=NULL ;root->r=NULL;}否则{如果(k<根->数据) 根->l= 构建树(root->l,k );其他root->r=构建树(根-> r,k) ;}返回根;
}树*删除(树* root,int k)//砍树{if(!root)printf(“已剪%d\n”, k);else{if(k== 根->数据){printf("剪切%d\n", k );根=  NULL;}否则 if(k<根-> 数据)root->l =  删除(root- >l, k);elseroot->r = 删除(root->r, k );}返回根;
}空dis(树*root) //输出{if(根){dis() 根->l);if(标志)标志= 假;否则cout< <" ";cout<<根->数据;dis(根->r);}
}int main()
{intn,m,k ;树*根=NULL;cin>>n>>m; 同时(n--){cin>>k;根=构建树(root,k);}同时(m--){cin>>k;root=删除(root, k);标志= true;dis(root);cout<<endl;}返回0;
}

最近发表

猜你喜欢

K——巨斧砍大树（二叉树操作）

相关文章