20 二叉树：销毁_java实现销毁二叉树

20 二叉树：销毁

作者: 冯向阳时间限制: 1S章节: DS:树

截止日期: 2022-06-30 23:55:00

问题描述 :

目的：使用C++模板设计并逐步完善二叉树的抽象数据类型（ADT）。

内容：（1）请参照链表的ADT模板，设计二叉树并逐步完善的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考教材、课件，以及网盘中的链表ADT原型文件，自行设计二叉树的ADT。）

注意：二叉树ADT的基本操作的算法设计很多要用到递归的程序设计方法。

（2）基本操作6：在二叉树的二叉链表存储形式建立的基础上，设计二叉树的销毁算法，主要用于析构函数中。完成后将其加入到二叉树的ADT基本操作集中。

要求使用递归的程序设计方法，设计并完成二叉树的销毁算法。

初始条件：二叉树T存在。

操作结果：销毁二叉树T。

参考函数原型：

//销毁树(外壳部分，public） 

template<class ElemType>

void BinaryTree<ElemType>::BinaryTreeDestroy();

//销毁树（递归部分。private） 

template<class ElemType>

void BinaryTree<ElemType>::BinaryTreeDestroy_Cursive( BinaryTreeNode<ElemType> *T );

输入说明 :

第一行：表示无孩子或指针为空的特殊分隔符

第二行：二叉树的先序序列（结点元素之间以空格分隔）

输出说明 :

第一行：

success //销毁成功

fail  //销毁失败

输入范例 :

输出范例 :

其实如果你直接写个

这样的代码

#include<iostream>
using namespace std;
int main()
{
cout<<"success"<<endl;
return 0;
}

好像都可以对很多个。

但全AC得代码如下

#include<iostream>
#include<queue>
using namespace std;
int m1 = 0;
struct student
{
	string data;
	student* left;
	student* right;
};
 
void creat(student*& T, string kk)
{
	string ch;
	cin >> ch;
	if (ch == kk)
	{
		T = NULL;
	}//但凡输入了#号 该节点下一位停止
	else
	{
		T = new student;
		T->data = ch;
		creat(T->left, kk);
		creat(T->right, kk);
	}
}
 
void level_scan(student* root)
{
	queue<student*> m;
	m.push(root);
	student* p;
	while (!m.empty())
	{
		p = m.front();
		if (m1 == 1)
		{
			cout << ",";
 
		}
		m1 = 1;
		cout << p->data;
		m.pop();
		if (p->left != NULL)
		{
			m.push(p->left);
		}
		if (p->right != NULL)
		{
			m.push(p->right);
		}
	}
}
 
int depth(student* root)
{
 
	if (root == NULL)
		return 0;
	else
	{
		int left = depth(root->left);
		int right = depth(root->right);
		if (left > right)
		{
			return left + 1;
		}
		else
		{
			return right + 1;
		}
 
	}
}
void destroy(student* root)
{
	if (root == NULL)
	{
 
		return;
	}
		destroy(root->left);
		destroy(root->right);
 
		delete(root);
		root = NULL;
 
}
int main()
{
	student* root;
	string kk;
	cin >> kk;
	creat(root, kk); 
	if (root == NULL)
	{
		cout << "fail" << endl;
		return 0;
	}
 
	destroy(root);
	
	
		cout << "success" << endl;
		return 0;
	
	
}