二叉树：销毁_销毁二叉树

目的：使用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 );

正片开始：

仍然用之前的模板上储存结构等代码，然后再按题目要求写两个函数，一个private，一个public。

代码如下：

#include<iostream>
#include<cstring>
#include<vector>
#include<queue>
#include<sstream>
using namespace std;
/* 二叉表的结点定义 */
template<class ElemType>
struct BinaryTreeNode
{
    ElemType data;
    BinaryTreeNode<ElemType> *LChild, *RChild;
    BinaryTreeNode() : LChild(NULL), RChild(NULL) {} //构造函数1，用于构造根结点
    BinaryTreeNode(const ElemType &item, BinaryTreeNode<ElemType> *Lptr = NULL, BinaryTreeNode<ElemType> *Rptr = NULL) //构造函数2，用于构造其他结点
//函数参数表中的形参允许有默认值，但是带默认值的参数需要放后面
    {
        LChild = Lptr;
        RChild = Rptr;
        data = item;
    }
    ElemType getData()
    {
        return data; //取得结点中的数据
    }
    void SetLChild( BinaryTreeNode<ElemType> *link )
    {
        LChild = link; //修改结点的左孩子域
    }
    void SetRChild( BinaryTreeNode<ElemType> *link )
    {
        RChild = link; //修改结点的右孩子域
    }
    void SetData( ElemType value )
    {
        data = value; //修改结点的data域
    }
    BinaryTreeNode<ElemType> * GetLChild() const
    {
        return LChild; //获取左孩子结点
    }
    BinaryTreeNode<ElemType> * GetRChild() const
    {
        return RChild; //获取左孩子结点
    }
 
};
template<class ElemType>
bool visit(BinaryTreeNode<ElemType> *root,int &num)
{
    if(!root)
        return false;
    else
    {
        if(num==0)
        {
            cout<<root->data;
            num++;
        }
        else
            cout<<","<<root->data;
        return true;
    }
}
//二叉树
template<class ElemType>
class BinaryTree
{
private:
    BinaryTreeNode<ElemType> *root; // 头指针
    //销毁树（递归准备，private）
    bool Destroy_Cursive( BinaryTreeNode<ElemType> *T )
            {
                if(T==NULL) return false;
                Destroy_Cursive(T->LChild);
                Destroy_Cursive(T->RChild);
                free(T);
                T=NULL;
                return true;
            }//按题目要求放在private里的函数
public:
//无参数的构造函数
    BinaryTree():root(NULL) {}
//带参数的构造函数
    BinaryTree(const ElemType &item)
    {
        root = new BinaryTreeNode<ElemType>(item);
    }
//生成树
    void makeBinaryTree( const ElemType &item, BinaryTree &left, BinaryTree &right);
//拷贝构造函数
//LinkQueue(LinkQueueList<ElemType> &Queue);
//析构函数
//~BinaryTree()
//{
// BinaryTreeDestroy();
//}
//重载函数:赋值
//LinkList<ElemType>& operator=(LinkList<ElemType> &List);
//销毁树
    void BinaryTreeDestroy();
//销毁子树
    void ChildDestroy(int flag);
//返回二叉树结点的个数
    int BinaryTreeSize( BinaryTreeNode<ElemType> *T ) const;
//判断二叉树是否为空
    bool BinaryTreeisEmpty() const
    {
        return root == NULL;
    }
//获取根结点元素值
    ElemType GetRootData() const
    {
        return root->data;
    }
//bool Location(ElemType &x, BinaryTreeNode<ElemType> * &location);
//设置根结点
    void SetRoot(BinaryTreeNode<ElemType> * p)
    {
        root = p;
    }
//获取根结点
    BinaryTreeNode<ElemType> * GetRoot() const
    {
        return root;
    }
//前序遍历
    bool Pre(BinaryTreeNode<ElemType> *T,bool(*visit)(BinaryTreeNode<ElemType> *T,int &num),int &num) const; //前序遍历（递归）//num的初始值为0，作用为控制输出格式（最后1个结点后不加“，”）
//中序遍历
    bool In(BinaryTreeNode<ElemType> *T,bool(*visit)(BinaryTreeNode<ElemType> *T,int &num),int &num) const; //中序遍历（递归）
//后序遍历
    bool Post(BinaryTreeNode<ElemType> *T,bool(*visit)(BinaryTreeNode<ElemType> *T,int &num),int &num) const; //后序遍历（递归）
//层次遍历
    bool Ceng(BinaryTreeNode<ElemType> *T,bool(*visit)(BinaryTreeNode<ElemType> *T,int &num),int &num) const;//层次遍历 （递归）
//建立二叉树的存储结构
    BinaryTreeNode<ElemType>* CreateBinaryTree(vector<ElemType> &x, ElemType &sym, int &n);
   bool Destroy( );//public这里还要放一个
};
//建立二叉树的存储结构 (递归部分，成员函数）
template<class ElemType>
BinaryTreeNode<ElemType>* BinaryTree<ElemType>::CreateBinaryTree(vector<ElemType> &x, ElemType &sym, int &n)
{
    ElemType ch = x[n];
    n++;
    if (ch == sym)
    {
        return NULL;
    }
    else
    {
        BinaryTreeNode<ElemType> *Node = new BinaryTreeNode<ElemType>;
        Node->data = ch;
        Node->LChild = CreateBinaryTree(x, sym, n);
        Node->RChild = CreateBinaryTree(x, sym, n);
        return Node;
    }
}
//建立二叉树的存储结构 (外壳）
template<class ElemType>
void CreateTree(BinaryTree<ElemType> &T, ElemType &str, ElemType &sym)
{
    ElemType tmp;
    vector<ElemType> t;
    stringstream input_T(str);
    while(input_T>>tmp)
    {
        t.push_back(tmp);
    }
    BinaryTreeNode<ElemType> *root;
    int num=0;
    root=T.CreateBinaryTree(t,sym,num);
    T.SetRoot(root);
}
template<class ElemType>
void BinaryTree<ElemType>::makeBinaryTree(const ElemType &item, BinaryTree &left, BinaryTree &right)
{
    root=new BinaryTreeNode<ElemType>(item,left.root,right.root);
    left.root=NULL;
    right.root=NULL;
}
template<class ElemType>
bool BinaryTree<ElemType>::Destroy()//作为成员函数出现的，前面仍然加了BinaryTree<ElemType>::
{
    BinaryTreeNode<ElemType>*p=GetRoot();//取的类私有的里面的函数，所以直接=GetRoot()
    if(Destroy_Cursive( p ))//这里用的是类的私有函数，定义在private里面的，因为上一行的上一行里有BinaryTree<ElemType>::，就直接用啦
    {
        return true;
    }//然后我的一个问题就是之前写三个遍历的时候把函数名都取的一样的，然后后面自己也没分清楚，结果写这个题的时候，
    else return false;//因为题目里面要求一个放在私有的private里，一个放在公有的public里
}                      //然后都用一样的名字的话就会出现重复定义的问题（其实参数形式不一样的话也顶多重载，但我开始写的时候在探索过程出了点小差错
                      //把公有的这个函数也带上了参数，然后就出现了重复定义的错误）
int main()
{
    BinaryTree<string>BT;
    string mytree;
    string sym;
    getline(cin,sym);
    getline(cin,mytree);
    CreateTree(BT,mytree,sym);
    if(BT.Destroy())//用的内部函数，BT.函数  即可
    {
        cout<<"success"<<endl;
        return 0;
    }
    else
    cout<<"fail"<<endl;//也可以用判空的方法，这里这样直接看有没有destroy干净，没有的话用个else输出fail即可
    return 0;
}

谢谢支持！在学习ADT型，会继续加油的！