做链家房产的网站怎么做的,工地用建筑模板生产厂家,怎么做百度快照让网站排前面,百度账号登录不了Description
给出一个数据序列#xff0c;建立二叉排序树#xff0c;并实现删除功能
对二叉排序树进行中序遍历#xff0c;可以得到有序的数据序列
Input
第一行输入t#xff0c;表示有t个数据序列
第二行输入n#xff0c;表示首个序列包含n个数据
第三行输入n个数据…Description
给出一个数据序列建立二叉排序树并实现删除功能
对二叉排序树进行中序遍历可以得到有序的数据序列
Input
第一行输入t表示有t个数据序列
第二行输入n表示首个序列包含n个数据
第三行输入n个数据都是自然数且互不相同数据之间用空格隔开
第四行输入m表示要删除m个数据
从第五行起输入m行每行一个要删除的数据都是自然数
以此类推输入下一个示例
Output
第一行输出有序的数据序列对二叉排序树进行中序遍历可以得到
从第二行起输出删除第m个数据后的有序序列输出m行
以此类推输出下一个示例的结果
Sample
#0
Input
1
6
22 33 55 66 11 44
3
66
22
77Output
11 22 33 44 55 66
11 22 33 44 55
11 33 44 55
11 33 44 55 AC代码
#include iostream
using namespace std;// 二叉排序树节点
struct TreeNode {int data;TreeNode* left;TreeNode* right;TreeNode(int val) : data(val), left(nullptr), right(nullptr) {}
};// 插入节点到二叉排序树
TreeNode* insert(TreeNode* root, int data) {if (root nullptr) {return new TreeNode(data);}if (data root-data) {root-left insert(root-left, data);}else {root-right insert(root-right, data);}return root;
}// 寻找最小值节点
TreeNode* findMin(TreeNode* node) {//不断往左树找直到空为止就是最小的while (node-left ! nullptr) {node node-left;}return node;
}// 删除节点
TreeNode* remove(TreeNode* root, int data) {if (root nullptr) {return root;}// 不断寻找结点if (data root-data) {root-left remove(root-left, data);}else if (data root-data) {root-right remove(root-right, data);}else {// 节点找到//结点有一个或没有的情况if (root-left nullptr) {//左手空直接把右手接上TreeNode* temp root-right;delete root;return temp;}else if (root-right nullptr) {TreeNode* temp root-left;delete root;return temp;}// 有两个子节点的情况// 去右手找到最小的结点TreeNode* temp findMin(root-right);//用这个右手上找到的最小的来替换当前结点root-data temp-data;//替换完了之后记得把temp删掉root-right remove(root-right, temp-data);}return root;
}// 中序遍历并输出结果
void inorderTraversal(TreeNode* root) {if (root ! nullptr) {inorderTraversal(root-left);cout root-data ;inorderTraversal(root-right);}
}int main() {int t;cin t;for (int i 0; i t; i) {int n;cin n;TreeNode* root nullptr;for (int j 0; j n; j) {int data;cin data;root insert(root, data);}inorderTraversal(root);cout endl;int m;cin m;for (int k 0; k m; k) {int deleteData;cin deleteData;root remove(root, deleteData);inorderTraversal(root);cout endl;}}return 0;
}
