编写程序对给定二叉树执行若干次删除子树操作，输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于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;
}

 

二叉树删除子树
输入格式:
输出格式:
输入样例:
输出样例:
题解:
完全二叉树的思路
链式存储实现二叉树
利用内存池去简化代码

编写程序对给定二叉树执行若干次删除子树操作，输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于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 

题解:
这题主要就是构建出一颗二叉树，然后进行遍历操作，而构建二叉树可以利用数组或结构体来实现，这里我都一一讲一下，并且说一下各自的利弊。
完全二叉树的思路
首先是用存储完全二叉树的思路去构建二叉树。node 表示当前节点，如果根节点从 0 开始算的话，那么它的左孩子就是 2*node+1，右孩子就是 2*node+2，参考下图理解一下，随便任意一个节点的编号乘以 2 再加 1就是左孩子的编号，加2就是右孩子的编号。

所以我们就可以利用一个数组，数组的下标就对应节点的编号，这种做法的好处是代码简单，容易理解，代码如下。
#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+5;
int data[N], ans[N], len;
// data 存储节点的数据
// ans 储存题目要求输出的中序遍历
// len 记录ans数组中节点的个数

void build_tree(int node) {
    int lnode = 2*node + 1; //计算左孩子节点的下标
    int rnode = 2*node + 2; //计算右孩子节点的下标
    int x;
    cin >> x; //读入当前节点数据
    data[node] = x; 
    if(x == 0) return ; //如果x == 0是结束标志，返回
    build_tree(lnode); //构建当前节点的左子树
    build_tree(rnode); //构建当前节点的右子树
}

bool solve(int node, int x) {
    if(data[node] == 0) return false; //data[node] == 0是结束标志，返回false
    if(data[node] == x) { //找到了需要切掉的子树的根，将data[node]修改为0
        data[node] = 0;	  //之后递归到这里就会直接返回，相当于切掉了该子树
        return true;	  //找到了要切掉的子树，返回true
    }
    bool flag = false;
    int lnode = 2*node + 1;
    int rnode = 2*node + 2;
    flag |= solve(lnode, x); //等价于flag = flag|solve(lnode,x)
    ans[len++] = data[node]; //记录中序遍历
    flag |= solve(rnode, x); // ‘|’是或运算符，如flag = true|false，则flag = true
    return flag; //返回有没有找到需要切掉的子树
} 

int main() {
    build_tree(0); //构建二叉树
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        len = 0;
        if(!solve(0, x)) cout << 0 << endl; //没有找到，输出0，行末无空格
        else {
            for(int i=0; i < len; i++) //找到了要切的子树，输出中序遍历，行末有空格
                cout << ans[i] << ' ';
            cout << endl; //记得换行
        }
    }
    return 0;
}

上述代码写了两个函数，一个是构建二叉树，一个是对二叉树进行中序遍历，不过要注意的就是在中序遍历时，如果遍历到了要切掉的子树的根时，也要返回，因为被切掉的子树不需要遍历。OK，提交代码后完美地来了段错误。

不难发现，这题的节点个数保证不超过5000个，也就是说最坏情况下，我们需要的data数组大小是2^5000。所以打算用完全二叉树的思路水过这道题的计划失败，老老实实写个链式存储。
链式存储实现二叉树
我们要用结构体去定义一个节点，一个节点有三个属性，数据 data，指向左孩子的指针 lson，指向右孩子的指针 rson。其实就是数据结构课上教的实现方法，代码如下。
#include<bits/stdc++.h>
using namespace std;

const int N = 5e3+5;
int ans[N], len;

struct Node {
    int data; //记录当前节点数据
    Node *lson; //左孩子指针
    Node *rson; //右孩子指针
};

Node * build_tree() {
    int x;
    cin >> x;
    if(x == 0) return NULL; //结束标志，返回NULL
    Node *p = new Node(); //申请当前节点内存空间
    p->data = x; 
    p->lson = build_tree(); //构建左子树
    p->rson = build_tree(); //构建右子树
    return p;
}

void delete_tree(Node *p) {
    if(p == NULL) return ;
    delete_tree(p->lson); //删除左子树
    delete_tree(p->rson); //删除右子树
    delete p; //释放当前节点
}

bool solve(Node *p, int x) {
    if(p == NULL) return false; //找不到要切的子树，返回false
    if(p->data == x) { //找到了要切的子树
        delete_tree(p); //调用函数删除该子树
        return true; //返回true表示找到了该子树
    }
    bool flag = false;
    int t = -1;
    if(p->lson != NULL) t = p->lson->data; //记录下左子树的根的数据
    flag |= solve(p->lson, x); 
    if(t == x) p->lson = NULL; //如果左子树为要切的子树，则将p->lson赋值为NULL，不然就变成野指针了
    ans[len++] = p->data;
    t = -1;
    if(p->rson != NULL) t = p->rson->data;
    flag |= solve(p->rson, x);
    if(t == x) p->rson = NULL;
    return flag;
} 

int main() {
    Node *head = build_tree(); //构建二叉树，并记录根节点地址
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        len = 0;
        if(!solve(head, x)) cout << 0 << endl; //没有找到，输出0，行末无空格
        else {
            for(int i=0; i < len; i++) //找到了要切的子树，输出中序遍历，行末有空格
                cout << ans[i] << ' ';
            cout << endl;
        }
    }
    delete_tree(head); //记得释放申请的所有空间
    return 0;
}

主要思路还是不变的，在中序遍历时如果找到了要切除的子树，则调用delete_tree函数释放掉该子树，但是有一点很麻烦的就是释放掉该子树后，原先指向该子树的指针没有修改成NULL，这样就会导致段错误。所以可以发现我在递归调用左右子树的时候加了好几段可读性很差的代码。
利用内存池去简化代码
上面代码我觉得主要难写的是释放要切除的子树后，还要想办法去把指向这个子树的指针修改为NULL，如果换成一道复杂的题，这个bug可能就要找好久了。还有就是动态分配的内存需要释放掉就很烦，所以内存池就是解决这些问题的。内存池可以理解成我们事先申请一整块内存，然后需要用到一个节点的时候我们就分一点给它，这样我们在写代码的时候就不需要去考虑管理这些内存了，直接在程序最后结束的时候一次性全部释放掉就行了。可能还有点抽象，看下面的代码和注释理解一下。
const int N = 5e3+5;

struct Node {
	int data;
    Node *lson;
    Node *rson;
}node[N]; //申请一个节点数组作为内存池

Node * newnode() { //这个函数每次调用，就从内存池中拿一个新的节点并返回。
    static int cnt = -1; //静态变量，记录最后一次申请的节点的下标
    return &node[++cnt]; //返回一块内存
}

/* 看不懂上面的静态变量的可以看一下下面这个，两个等效的
int cnt = -1;
Node * newnode() {
	cnt = cnt + 1;
	return &node[cnt];
}
*/

有了上面的代码，我们就可以不用去管理内存了，在做切除子树操作时，只需要把 data 标记为 0, 代表结束的标志，而不用真正地去释放这颗子树的内存。整体的代码就像完全二叉树的思路里的代码一样了，代码如下。
#include<bits/stdc++.h>
using namespace std;

const int N = 5e3+5;
int ans[N], len;

struct Node {
    int data;
    Node *lson;
    Node *rson;
}node[N]; //申请一个节点数组作为内存池

Node * newnode() { //从内存池中申请一块新的内存
    static int cnt = -1;
    return &node[++cnt];
}

Node * build_tree() { //构建二叉树
    int x;
    cin >> x;
    if(x == 0) return NULL;
    Node *p = newnode(); //申请新节点
    p->data = x;
    p->lson = build_tree(); //构建左子树
    p->rson = build_tree(); //构建右子树
    return p; //返回当前构建好的这棵树
}

bool solve(Node *p, int x) {
    if(p == NULL || p->data == 0) return false; //当前树为空树或这棵树被标记为被切掉了
    if(p->data == x) { //找到了要切掉的子树的树根
        p->data = 0; //标记一下这棵树被切掉了
        return true; //返回true表示找到了要切的树
    }
    //中序遍历
    bool flag = false;
    flag |= solve(p->lson, x); //到左子树中找
    ans[len++] = p->data;
    flag |= solve(p->rson, x); //到右子树中找
    return flag;
} 

int main() {
    Node *head = build_tree(); //构建二叉树，并记录根的地址
    int t;
    cin >> t;
    while(t--) {
        int x;
        cin >> x;
        len = 0;
        if(!solve(head, x)) cout << 0 << endl; //没有找到要切除的子树，输出0，行末无空格
        else {
            for(int i=0; i < len; i++) //输出切除子树后的中序遍历序列，行末有空格
                cout << ans[i] << ' ';
            cout << endl; //记得换行
        }
    }
    //在程序结束的时候，申请来的节点数组node[]就会被自动释放了
    return 0;
}

章节简介
前5篇博客写的都是线性结构，对于有层级结构的数据需要用树形结构来描述
本章的重要知识点
理解有关树的基本概念和二叉树的基本概念
掌握二叉树的存储结构以及遍历方法
掌握树的存储结构以及树、森林、二叉树的相互转换方法
梳理掌握哈夫曼树构造方法和哈夫曼编码的设计方法
树的基本概念
核心一句话
 线性结构中一个结点至多只有一个直接后继，树形结构一个结点可以有一个或多个直接后继
认识树
看图即可，你要能区分出来哪些是树，哪些不是树 
树的相关术语
结点的度：树上任意结点所拥有的子树的数目称为该结点的度 
叶子：度为0的结点称为叶子或者终端结点  
树的度：一棵树中所有结点的度的最大值称为该树的度，就是把所有结点的度求和
结点的层次：从根算起，根的层次为1，其余结点的层次为其双亲的层次加1  
树的高度：一棵树中所有结点层次数的最大值称为该树的高度或深度
还有一些小概念：有序树、无序树
 树的相关术语，一定要一开始就明确清晰，后面才好学习
二叉树
官方概念：二叉树是n(n≥0)个元素的有限集合，该集合或者为空，或者由一个根及两棵互不相交的左子树和右子树组成，其中左子树和右子树也均为二叉树。二叉树的任一结点都有两棵子树（它们中的任何一个都可以是空子树），并且这两棵子树之间有次序关系，交换位置就成为一棵不同的二叉树。
左子树和右子树，也有的叫做左孩子和右孩子
二叉树五种基本形态，方块表示子树
二叉树的基本运算（不写代码，了解重点函数即可）
初始化
求双亲
求左孩子
求右孩子
建二叉树
先序遍历！！！
中序遍历！！！
后序遍历！！！
层次遍历！！！ 先序遍历，中序遍历，后序遍历在考试中一般不要求手写代码，但是需要你能通过一棵树结构，输出最终的结果，这个博客结尾给大家看一下例题
二叉树性质（很重要，细碎知识点很多）
性质1：二叉树第i(i≥1)层上至多有2^i-1^个结点。
 不需要死记硬背，实际需要的时候画一个二叉树就可以求出来了
性质2：深度为k（k≥1）的二叉树至多有2^k^-1个结点
 依旧可以推导出来 深度为1的二叉树 结点最多为1 深度为2的二叉树 结点最多为3 深度为3的二叉树 结点最多为7 深度为k的二叉树 结点最多为2^k^-1
性质3：对任何一棵二叉树，若度数为0的结点（叶结点）个数为n~0~，度数为2的结点个数为n~2~，则n~0~ = n~2~+1
 这个性质需要稍微推导一下 先回答一个问题，你知道树的度数，怎么计算树的结点数 例如  树的度数为2，结点树为几，这个不难想象，会出现如下情况
 看到这里不难发现，存在一个公式为  树的度数+1=树的结点树 那么我们开始推导上述公式 假设 二叉树的0度，1度，2度结点个数为n~0~，n~1~，n~2~，结点总数为T T = n~0~+n~1~+n~2~ 树的度数+1 = T 树的度数怎么求？n~0~0+n~1~1+n~2~2 是树的度数 继续n~0~0+n~1~1+n~2~2 +1 = T = n~0~+n~1~+n~2~ ===> 2n~2~+1=n~0~+n~2~ ===>n~0~=n~2~+1 
好了，上述过程，争取看明白吧
性质4：含有n个结点的完全二叉树的深度为 log~2~n +1
 这个地方引出了一个新的概念完全二叉树
说明什么是完全二叉树之前，需要理解什么是满二叉树
满二叉树 深度为k(k≥1)且有2^k^-1个结点的二叉树称为满二叉树
完全二叉树 如果对满二叉树按从上到下，从左到右的顺序编号，并在最下一层删除去部分结点（删除最后一层仍有结点），如果删除的这些结点的编号是连续的且删除的结点中含有最大编号的结点，那么这棵二叉树就是完全二叉树 注意  x  这个符号，表示不大于x的最大整数
教材中，给了几个范例，偷懒我用一下
 关于性质4的证明，有兴趣的自行研究一下吧
性质5：如果将一棵有n个结点的完全二叉树按层编号，按层编号是指：将一棵二叉树中的所有n个结点按照从第一层到最大层，每层从左到右的顺序依次标记为1,2，....，n。则对任意编号i(1≤i≤n)的结点A有： 
（1）若i=1，则结点A是根；若i＞1，则A的双亲编号为  i/2  。（注意  x  这个符号，表示不大于x的最大整数）  
（2）若2*i＞n，则结点A既无左孩子，也无右孩子；否则A的左孩子的编号为2*i。 （
3）若2*i+1＞n，则结点A无右孩子；否则，A的右孩子编号为2*i+1；
这个性质5有点意思，先验证一下 
 所以这个性质稍微配合着图看一下就可以完美学会
二叉树存储结构
二叉树也是两类存储结构：顺序存储和链式存储
先看顺序存储结构
这个地方对于初学者你来说，理解即可
对一棵完全二叉树上的所有结点按层编号，然后按照编号存储到一维数组里面即可。
书中有个比较好的例子了，直接截图，理解一下
 重点是下面，如果一个树不是完全二叉树咋办
教材中给的方案是，添加虚拟结点，说白了，就是凑成完全二叉树，不过注意这种解决方案缺点就是浪费空间 
 二叉树的链式存储，记住常用的叫做 二叉链表  和  三叉链表 即可，其他的在自考和期末考试中不是重点部分，选择性的看不到吧。
二叉树的遍历
这个有点意思了，是考试的重点，但是不是叫你写代码哦~而是手动遍历。 请注意，二叉树遍历有六种可能，我们核心关注三种
分别是
先序遍历
中序遍历
后序遍历
直接看图解释吧,先画一个二叉树 
 为了解决遍历问题，你要先划分好区域，找到左子树、右子树还有根 
先序遍历走起 1. 访问根结点 （==根结点在开头==） 2. 先序遍历左子树 3. 先序遍历右子树  
 中序遍历走起 4. 中序遍历左子树 5. 访问根结点   （==根结点在中间==） 6. 中序遍历右子树  
 后序遍历走起 1. 后序遍历左子树 2. 后序遍历右子树
 3. 访问根结点（==根结点在后头==）
 这种题就多练就可以啦~
当然还有一种需要会，叫做二叉树的按层遍历，这个就比较简单了，自行学习一下就可以掌握
自考真题
二叉树遍历在自考中是一个比较重要的题目，来几道真题吧 
在评论区写上你的答案吧
与梦想老师建立关系时间
更多内容，欢迎关注 https://dwz.cn/r4lCXEuL

#include<stdio.h>
#include <stdlib.h>
typedef struct BiTNode{                //定义结点结构 
	char data;
	struct BiTNode *lchild,*rchild;    //指向左右孩子的指针 
}BiTNode,*BiTree;                    //命名结点类型名，和指向结点的指针类型 

void Release(BiTree &T){            //递归删除该结点及以下结点 
	if(T!=NULL){
	Release(T->lchild);
	Release(T->rchild);
	free(T);
	T=NULL;		//因为free只是告诉系统这块内存我们不用了而不是物（释放了该结点，不在连接到树上） 
						//理上面的释放所以我们要手动赋值NULL;  （虽然释放了该结点，但里面还有存放这值，这里置空） 
	}
}

void Delete_X(BiTree &T,char x){    //递归寻找要删除的结点 
	if(T==NULL)                    //1、树为空 
		return;
	
	if(T->data==x){       //2、若T的data为想要删除的元素 则进行删除
			Release(T);   //删除包括根节点
		
	}
	if(T!=NULL){		 //3、以上情况都不是，递归向左右孩子寻找 
		Delete_X(T->lchild, x);
		Delete_X(T->rchild, x);
	}

}
void CreateBiTree(BiTree &T){  //先序建立二叉树  
	char ch;
	scanf("%c",&ch);          
	if(ch=='#') T=NULL;      //#代表该结点为空 ，也就是父节点没有这个孩子结点 
	else
	{
		T=new BiTNode;
		T->data=ch;
		CreateBiTree(T->lchild);
		CreateBiTree(T->rchild);
	}
}
void FirstTraver(BiTree T){  //先序遍历 
	if(T){
		printf("%c",T->data);
		FirstTraver(T->lchild);
		FirstTraver(T->rchild);
	}
} 

int main()
{
	BiTree T; 
	printf("请建立表：\n");
	
	CreateBiTree(T);
	char ch;                
    ch=getchar();        //接收输入数据后回车的影响 
//	BiTree K=T;
	FirstTraver(T);     //先序遍历创建的树 
	printf("\n");
	printf("请输入要删除的节点:\n");
	char del;
	scanf("%c",&del);
	Delete_X(T,del);      //删除该结点及其子树 
	FirstTraver(T);       //先序遍历删除后的结果 
	
}             

这里还有快捷的方式，就是不用递归删除子树，而是当找到要删除的结点时，修改该结点的指向左右孩子指针为NULL;这等于直接切掉了该子树。但该子树还是存在内存中。




测试结果