编写程序对给定二叉树执行若干次删除子树操作，输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于0的整数。每次删除操作是在上一次删除操作后剩下的二叉树上执行。

输入格式:

输入第1行为一组用空格间隔的整数，表示带空指针信息的二叉树先根序列，其中空指针信息用0表示。例如1 5 8 0 0 0 6 0 0表示如下图的二叉树。第2行为整数m，表示要进行的删除操作次数。接下来m行，每行一个不等于0的整数K，表示要删除以K为根的子树。m不超过100，二叉树结点个数不超过5000。输入数据保证各结点数据值互不相等，且删除子树后二叉树不为空。

输出格式:

输出为m行，每行为一组整数，表示执行删除操作后剩余二叉树的中根序列（中根序列中每个整数后一个空格）。若要删除的子树不在当前二叉树中，则该行输出0（0后无空格）。

输入样例:

1 5 8 0 0 0 6 0 0
3
5
8
6

输出样例:

1 6 
0
1 

#include<bits/stdc++.h>
using namespace std;

struct BNode 
{
	string data;
	BNode* lch, * rch;
	BNode(string item):data(item), lch(NULL), rch(NULL){}
};

void PreOderBuild(BNode*& BT) {  //建树
    string s;
    cin>>s;
	if (s == "0") {
		BT = NULL;
	}
	else {
		BT = new BNode(s);
		PreOderBuild(BT->lch);
		PreOderBuild(BT->rch);
	}
}
void midOrder(BNode* root) {
	if (!root) return;
	midOrder(root->lch);
    cout<<root->data<<" ";
	midOrder(root->rch);
}
void deletNode(BNode*& root, string goal, bool& flag) {
	if (!root) {
		flag |= false;
		return;
	}
	if (root->data == goal) {
		root = NULL;
		flag |= true;
		return;
	}
	deletNode(root->lch, goal, flag);
	if(!flag) deletNode(root->rch, goal, flag);
}
int main() {
    BNode* BT;
	PreOderBuild( BT);	
	int m;
	cin >> m;
	string child;
	while (m--) {
		cin >> child;
        bool flag = false;
		deletNode(BT, child, flag);
		if (flag) {
			midOrder(BT);
			cout << endl;
		}
		else {
			cout << 0 << endl;
		}
	}
	return 0;
}

链式存储的二叉树：

删除节点分两种情况：

case1：要删除的就是根节点

• 让根节点 == null
  case2：要删除一个子树
• 想要删除某个节点，就找到他的父节点，让父节点不再指向子节点，就删掉了

代码：

1：测试类[TestBinaryTree]中先写好要遍历的树，然后写出对应的方法【其余代码看4.4】

   	 /**
        * 删除二叉树子树操作
        */
       //删除一个子树
       System.out.println("=======");
       binTree.delete(3);
       //检查是否删掉了5
       binTree.frontShow();

2：创建二叉树[BinaryTree]（写出根节点对应的方法）

    public void delete(int i) { //删除一个子树
       if(root.value == i){
           root = null;
       }else {
           root.delete(i);
       }
   }

3：创建树节点[TreeNode]（根据对应的方法，写出他的实现代码）

public void delete(int i) { //删除一个子树
       TreeNode parent = this;
       //判断左儿子
       if(parent.leftNode != null && parent.leftNode.value == i){
           parent.leftNode = null;
           return;
       }
       //判断右儿子
       if(parent.leftNode != null && parent.rightNode.value == i){
           parent.rightNode = null;
           return;
       }
       //递归检查并删除左儿子
       parent = leftNode;
       if(parent != null){
           parent.delete(i);
       }
       //递归检查并删除右儿子
       parent = rightNode;
       if(parent != null){
           parent.delete(i);
       }

   }

结果：当删除7时候，对应子节点被删除

结果：当删除3时候，左子树下的子节点也应该删除