博客

二叉搜索树的删除操作

给出一棵二叉搜索树（没有相同元素）, 请输出其删除部分元素之后的层序遍历序列。

删除结点的策略如下：

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

输入格式:

每个输入文件包含一个测试用例。每个测试用例的第一行包含一个整数

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<bits/stdc++.h>
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=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) {
	queue<BSTree*>q;
	q.push(t);
	BSTree* p;
	int sum=0;
	while(!q.empty()) {
		if(sum<a-k-1) {
			cout<<q.front()->data<<" ";
		} else {
			cout<<q.front()->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=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=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(n<root->data) {
		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<a;i++) {
		cin>>n;
		insert_Node(root,n);
	}
	int k;
	cin>>k;
	for(int i=0;i<k;i++) {
		cin>>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 来进行删除操作。