数据结构|PTA查找—二叉搜索树的删除操作数据结构|算法

二叉搜索树的删除操作 【数据结构|PTA查找—二叉搜索树的删除操作】给出一棵二叉搜索树（没有相同元素）, 请输出其删除部分元素之后的层序遍历序列。
删除结点的策略如下：

如果一个结点是叶子结点，则直接删除；
如果一个结点的左子树不为空, 则将该结点的值设置为其左子树上各结点中的最大值，并继续删除其左子树上拥有最大值的结点；
如果一个结点的左子树为空但右子树不为空，则将该结点的值设置为其右子树上各结点中的最小值，并继续删除其右子树上拥有最小值的结点。

输入格式:
每个输入文件包含一个测试用例。每个测试用例的第一行包含一个整数 N (0<N<=100)，表示二叉搜索树中结点的个数。第二行给出该二叉搜索树的先序遍历序列，由 N 个整数构成，以一个空格分隔。第三行给出一个整数K (0<K<N)，表示待删除的结点个数。最后一行给出 K 个整数，表示待删除的各个结点上的值。必须按输入次序删除结点。题目保证结点一定能被删除。
输出格式:
在一行中输出删除结点后的层序遍历序列。序列中的数字以一个空格分隔，行末不得有多余空格。
输入样例:

7 4 2 1 3 6 5 7 2 3 6 结尾无空行

输出样例:

4 2 5 1 7 结尾无空行

AC代码：

#include using namespace std; struct BSTree { int data; BSTree* left; BSTree* right; }; void insert_Node(BSTree* &root,int n) { if(root==NULL) { root = new BSTree(); root->data=https://www.it610.com/article/n; root->left=NULL; root->right=NULL; } else { if(n<=root->data) { insert_Node(root->left,n); } else { insert_Node(root->right,n); } } }int levelOder(BSTree* t,int a,int k) { queueq; q.push(t); BSTree* p; int sum=0; while(!q.empty()) { if(sumdata<<" "; } else { cout<data; } sum++; //控制输出 p=q.front(); q.pop(); if(p->left!=NULL) { q.push(p->left); } if(p->right!=NULL) { q.push(p->right); } } }void delete_Node(BSTree* &root) { if(root->left==NULL&&root->right==NULL) { root=NULL; } else if(root->left!=NULL) { BSTree* p=root; BSTree* q=root->left; while(q->right!=NULL) { p=q; q=q->right; } root->data=https://www.it610.com/article/q->data; if(p!=root) { delete_Node(p->right); } else { delete_Node(p->left); } } else if(root->left==NULL&&root->right!=NULL) { BSTree* p=root; BSTree* q=root->right; while(q->left!=NULL) { p=q; q=q->left; } root->data=https://www.it610.com/article/q->data; if(p!=root) { delete_Node(p->left); } else { delete_Node(p->right); } } }void deleteN(BSTree* &root,int n) { //根据二叉搜索树特性查找指定结点 if(n==root->data) { delete_Node(root); } else if(ndata) { deleteN(root->left,n); } else { deleteN(root->right,n); } }int main() { int a; cin>>a; int n; BSTree* root=NULL; for(int i=0; i>n; insert_Node(root,n); } int k; cin>>k; for(int i=0; i>n; deleteN(root,n); } levelOder(root,a,k); return 0; }

PS：
做题过程中发现以下问题：
就本题目而言，删除结点 3 的时候可以直接通过 delete_Node 函数完成，但是删除结点 5 时不可以直接使 q 指针指向 5 再让 q = NULL。原因猜测是 delete_Node 函数的参数 root 使用了引用形式 &root ，当删除 3 时，root直接指向 3，而删除 5 时，root指向 6，因此需要通过 root->left 来进行删除操作。