[C++知识库]前序创建二叉树c++

#include <iostream>
#include <string>
using namespace std;
int index = 0;
string str = "ABDH#K###E##CFI###G#J##"; //#表示结点为NULL


template<class T>
class TreeNode
{
    public:
        T data;
        TreeNode<T> *Lchild, *Rchild;

        TreeNode();
        TreeNode(T e);
};
template<class T>
TreeNode<T>::TreeNode(T e)
{
    data = e;
    Lchild = NULL;
    Rchild = NULL;
}
template<class T>
TreeNode<T>::TreeNode()
{
    Lchild = NULL;
    Rchild = NULL;
}

template<class T>
class LinkTree
{
    public:
        TreeNode<T> *root;

        LinkTree();
        void CreateTree(TreeNode<T> **r);   //前序创建二叉树
        void PreOrderTraverse(TreeNode<T> *r);  //前序遍历
        void MidOrderTraverse(TreeNode<T> *r);  //中序遍历
        void PostOrderTraverse(TreeNode<T> *r); //后序遍历
        void Post_delete(TreeNode<T> **r);       //根据后序遍历的特点可以用于释放内存，保证链树不断裂
        ~LinkTree();
};
template<class T>
LinkTree<T>::~LinkTree()
{
    if(root == NULL)
        return;
    cout << "内存释放顺序：" << endl;
    Post_delete(&root);
    cout << endl;
    cout << "内存释放完毕" << endl;
}
template<class T>
void LinkTree<T>::Post_delete(TreeNode<T> **r)
{
    if(*r == NULL)
        return;
    Post_delete(&(*r)->Lchild);
    Post_delete(&(*r)->Rchild);
    cout << (*r)->data << " ";
    delete *r;
}
template<class T>
void LinkTree<T>::PostOrderTraverse(TreeNode<T> *r)
{
    if(r == NULL)
        return;
    PostOrderTraverse(r->Lchild);
    PostOrderTraverse(r->Rchild);
    cout << r->data << " ";
}
template<class T>
void LinkTree<T>::MidOrderTraverse(TreeNode<T> *r)
{
    if(r == NULL)
        return;
    MidOrderTraverse(r->Lchild);
    cout << r->data << " ";
    MidOrderTraverse(r->Rchild);
}

template<class T>
void LinkTree<T>::PreOrderTraverse(TreeNode<T> *r)
{
    if(r == NULL)
        return;
    cout << r->data << " ";
    PreOrderTraverse(r->Lchild);
    PreOrderTraverse(r->Rchild);
}
template<class T>
void LinkTree<T>::CreateTree(TreeNode<T> **r)   //因根节点本身为指针，取引用后需用双重指针接收，
{                                               //此时*r代表root
    T ch;
    ch = str[index++];  //index的值不会随着递归返回而改变
    if(ch == '#')
        *r = NULL;
    else
    {
        *r = new TreeNode<T>;
        (*r)->data = ch;
        CreateTree(&(*r)->Lchild);
        CreateTree(&(*r)->Rchild);
    }
}
template<class T>
LinkTree<T>::LinkTree()
{
    root = NULL;
}
void test02()
{
    LinkTree<char> tree;
    tree.CreateTree(&tree.root);    //若此处不取引用，则CreateTree函数无法改变针对root操作。
    cout << "前序遍历为：" << endl;
    tree.PreOrderTraverse(tree.root);
    cout << endl;
    cout << "中序遍历为：" << endl;
    tree.MidOrderTraverse(tree.root);
    cout << endl;
    cout << "后序遍历为：" << endl;
    tree.PostOrderTraverse(tree.root);
    cout << endl;
}
int main()
{
    test02();
    system("pause");
    return 0;
}