以二叉链表为存储结构，在二叉树中删除以值x为根结点的子树

【问题描述】

首先输入扩展二叉树的前序序列，构建二叉树，然后输入希望删除的节点，输出删除后二叉树的前序和中序遍历序列。

【输入形式】 输入扩展二叉树的前序序列。

【输出形式】 分两行分别输出删除后二叉树的前序和中序遍历序列。

【样例输入】

ab##cd##e## c

【样例输出】

删除后.........

前序遍历：ab

中序遍历：ba

【样例说明】 上述输入对应以下结构的二叉树：

 a

/
b c

  /
 d e

删除以c为节点的子树后，得到下图的子树：

 a

/
b

【思路】

先判断根节点是否需要删除，需要的话就用release删除，不需要的话就检查其左右子树是否需要删除，左右子树调用delSubTree函数删除。

【题解代码】

#include<iostream>
using namespace std;

struct BiNode {
	char data;
	BiNode* lchild, * rchild;
};
class BiTree
{
private:
	BiNode* root;
	char x;
public:
	
	BiTree(){ root = creat(root); }
	~BiTree() {
	}
	BiNode* getRoot() { return root; }
	void searchDel(BiNode *bt, char x);//检查根结点
	void delSubTree(BiNode* bt, char x);//查找并删除结点
	void release(BiNode* bt);//释放树结点
	BiNode* creat(BiNode* bt);
	void preOrder(BiNode* bt);
	void inOrder(BiNode* bt);
	char getX() {  //输入要删除的结点
		cin >> x;
		return x;
	}
};
//创建二叉树
BiNode* BiTree::creat(BiNode* bt)
{
	char ch;
	cin >> ch;
	if (ch == '#')
	{
		bt = NULL;
	}
	else
	{
		bt = new BiNode;
		bt->data = ch;
		bt->lchild = creat(bt->lchild);
		bt->rchild = creat(bt->rchild);
	}
	return bt;
}

//检查根节点
void BiTree::searchDel(BiNode *bt, char x)
{
	if (bt == NULL)
		return;
	if (bt->data == x)//如果根节点就是要找的结点，直接release根节点，再将根节点赋为空
	{
		release(bt);
		root = NULL;
	}
	else//其他情况再调用delSubTree函数进行查找和删除
	{
		delSubTree(bt, x);
	}
}
//查找并删除结点
void BiTree::delSubTree(BiNode* bt, char x)
{
	if (bt == NULL)
		return;
	else
	{
		//左子树不为空，并且左子树就是要找的结点，删除左子树，再将左子树赋为空
		if (bt->lchild && bt->lchild->data == x)
		{
			release(bt->lchild);
			bt->lchild = NULL;
		}
		//右子树不为空，并且右子树就是要找的结点，删除右子树，再将右子树赋为空
		if (bt->rchild && bt->rchild->data == x)
		{
			release(bt->rchild);
			bt->rchild = NULL;
		}
		//继续递归查找
		delSubTree(bt->lchild, x);
		delSubTree(bt->rchild, x);

	}
}

void BiTree::release(BiNode* bt)
{
	if (bt != NULL)
	{
		release(bt->lchild);
		release(bt->rchild);
		delete bt;
	}
}
//前序遍历
void BiTree::preOrder(BiNode* bt)
{
	if (bt == NULL)
	{
		return;
	}
	cout << bt->data;
	preOrder(bt->lchild);
	preOrder(bt->rchild);
}
//中序遍历
void BiTree::inOrder(BiNode* bt) {
	if (bt == NULL) {
		return;
	}
	else {
		inOrder(bt->lchild);
		cout << bt->data;
		inOrder(bt->rchild);
	}
}
int main()
{
	BiTree tree;
	tree.searchDel(tree.getRoot(), tree.getX());
	cout << "删除后……" << endl;
	cout << "前序遍历:";
	tree.preOrder(tree.getRoot());
	cout << "\n中序遍历:";
	tree.inOrder(tree.getRoot());
	return 0;

}

【运行结果】