二叉树删除子树 （题目分析+C++代码实现）
二叉树删除子树
题目要求
编写程序对给定二叉树执行若干次删除子树操作，输出每次删除子树后剩余二叉树的中根序列。二叉树结点的数据域值为不等于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 题目分析
要点1：根据先根序列创建二叉树
从先根遍历的思想出发创建二叉树
//先根序列创建二叉树
BTNode* CreateBT() {
int a;
cin >> a;
BTNode* t;
if (a == 0) {
return NULL; //若为0则为空指针
}
else {
t = new BTNode;
t->data = a; //创建结点
}
t->left = CreateBT(); //递归左节点
t->right = CreateBT(); //递归右结点
return t;
}要点2：删除数据域为k的结点p为根的子树
先要查找到数据域为k的结点p；
结合递归释放二叉树，删除以结点p为根的子树还包括其左右子树；
同时，注意还要修改该结点p的父结点，将其父结点指向该结点p的指针置为空。
查找结点
先根遍历思想，找到数据域为k的结点
//查找结点
BTNode* Find(BTNode* root,int k) {
BTNode* q;
if (root == NULL) return NULL;
if (root->data == k) {
q = root;
return q;
}
q = Find(root->left, k);
if (q != NULL) return q;
q = Find(root->right, k);
}释放二叉树
递归释放结点及其左右子树
//释放二叉树
void Del(BTNode* p) {
if (p == NULL) return;
Del(p->left); //递归释放左右子树
Del(p->right);
delete(p); //释放内存
}查找给定结点的父亲
//查找给定结点的父亲
BTNode* father(BTNode* root, BTNode* p) {
BTNode* q;
if (root == NULL || p == NULL) return NULL;
if (root->left == p || root->right == p) {
q = root;
return q;
}
BTNode* ql;
ql = father(root->left, p);
if (ql != NULL) return ql;
q = father(root->right, p);
return q;
}删除子树
//删除子树
void delSubTree(BTNode* root, BTNode* p) {
if (root == NULL || p == NULL) return; //指针为空，直接返回
if (p == root) {
Del(p);
root = NULL;
return;
}
BTNode* q=father(root,p); //找到结点p的父结点
if (q->left == p) q->left = NULL; //p为q的左儿子，将左指针置空
if (q->right == p) q->right = NULL; //p为q的右儿子，将右指针置空
Del(p); //删除p及其子树
}完整代码
#include <iostream>
using namespace std;
typedef struct BTNode {
int data;
BTNode* left;
BTNode* right;
}BTNode;
//先根序列创建二叉树
BTNode* CreateBT() {
int a;
cin >> a;
BTNode* t;
if (a == 0) {
return NULL; //若为0则为空指针
}
else {
t = new BTNode;
t->data = a; //创建结点
}
t->left = CreateBT(); //递归左节点
t->right = CreateBT(); //递归右结点
return t;
}
//查找给定结点的父亲
BTNode* father(BTNode* root, BTNode* p) {
BTNode* q;
if (root == NULL || p == NULL) return NULL;
if (root->left == p || root->right == p) {
q = root;
return q;
}
BTNode* ql;
ql = father(root->left, p);
if (ql != NULL) return ql;
q = father(root->right, p);
return q;
}
//释放二叉树
void Del(BTNode* p) {
if (p == NULL) return;
Del(p->left); //递归释放左右子树
Del(p->right);
delete(p); //释放内存
}
//删除子树
void delSubTree(BTNode* root, BTNode* p) {
if (root == NULL || p == NULL) return; //指针为空，直接返回
if (p == root) {
Del(p);
root = NULL;
return;
}
BTNode* q=father(root,p); //找到结点p的父结点
if (q->left == p) q->left = NULL; //p为q的左儿子，将左指针置空
if (q->right == p) q->right = NULL; //p为q的右儿子，将右指针置空
Del(p); //删除p及其子树
}
//查找结点
BTNode* Find(BTNode* root,int k) {
BTNode* q;
if (root == NULL) return NULL;
if (root->data == k) {
q = root;
return q;
}
q = Find(root->left, k);
if (q != NULL) return q;
q = Find(root->right, k);
return q;
}
//中根遍历输出二叉树
void InOrder(BTNode* root) {
if (root == NULL) return;
InOrder(root->left);
cout << root->data << ' ';
InOrder(root->right);
}
int main() {
BTNode* root=CreateBT();
int m; //操作数
cin >> m;
while (m--) {
int k;
cin >> k;
BTNode* p = Find(root, k);
if (p == NULL) cout << '0' << endl; //若要删除的子树不在当前二叉树中，则该行输出0
else {
delSubTree(root, p); //删除子树
InOrder(root); //中根序列遍历输出
cout << endl;
}
}
return 0;
}提交结果
原文地址：https://blog.csdn.net/fcc13461862452/article/details/145284060
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！