数据结构C++实现二叉树的基本操作，创建二叉树时总是显示“无法读取内存”

Question

0x7763B48B (ntdll.dll) (二叉排序树基本操作.exe 中)处有未经处理的异常: 0xC0000005: 写入位置 0x004C0FFC 时发生访问冲突。

求大神解答！！！

存储结构

 template<class ElemType>
struct Btnode
{
    ElemType Data;
    Btnode<ElemType> *Lchild, *Rchild;
};

创建二叉树

 //按以先序次序输入节点值的方式建立二叉树
template<class ElemType>
void BinaryTree<ElemType>::_Create1(Btnode<ElemType> * &T,
                                    ElemType ch[], const ElemType &c, int &i)
{
    if (ch[i] == c) //c为特殊数据，如#、￥，用以标示空指针
    {
        T = NULL;
    }
    else
    {
        T = new Btnode<ElemType>;
        //T = (Btnode<ElemType> *)malloc(sizeof(Btnode<ElemType>));
        T->Data = ch[i];
        _Create1(T->Lchild, ch, c, ++i);
        _Create1(T->Rchild, ch, c, ++i);
    }
}

全部代码：

.h

 #ifndef _BINARYTREE_H
#define _BINARYTREE_H

#include <stack>
#include <queue>
using namespace std;

template<class ElemType>
struct Btnode
{
    ElemType Data;
    Btnode<ElemType> *Lchild, *Rchild;
};



//二叉链表类
template<class ElemType>
class BinaryTree
{
public:
    //构造函数
    BinaryTree() : m_root(NULL){}

    //拷贝函数
    BinaryTree(const BinaryTree &rhs)
    {
        m_root = _Copy(rhs.m_root);
    }

    //赋值重载
    BinaryTree& operator=(const BinaryTree &rhs)
    {
        if (&rhs == this)
        {
            return *this;
        }

        _Destroy(m_root);
        m_root = _Copy(rhs.m_root);
        return *this;
    }

    //析构函数
    ~BinaryTree()
    {
        _Destroy(m_root);
    }

    //按以先序次序输入节点值的方式建立二叉树的接口函数
    void Create1(ElemType ch[], const ElemType &c);

    //以二叉树的先序和中序次序建立二叉树的接口函数
    void Create2(ElemType ch1[], ElemType ch2[], int);

    //置空二叉树
     void Clear()
    {
        _Destroy(m_root);
    }

    //判断二叉树是否为空
    bool IsEmpty() const{
        return m_root == NULL;
    }

    //返回根节点的指针
    Btnode<ElemType>* Root() const{
        return m_root ;
    }

    //返回二叉树T中元素为e的节点的指针
    Btnode<ElemType>* Locate(ElemType &e)
    {
        return _Locate(m_root, e);
    }

    //求二叉树深度
    int Depth()
    {
        return _Depth(m_root);
    }

    //返回节点的双亲节点
    Btnode<ElemType>* Parent(Btnode<ElemType> *p)
    {
        return _Parent(m_root, p);
    }

    //返回节点的左孩子
    Btnode<ElemType>* LeftChild(Btnode<ElemType> *p)
    {
        return p->Lchild;
    }

    //返回节点的右孩子
     Btnode<ElemType>* RightChild(Btnode<ElemType> *p)
    {
        return p->Rchild;
    }

    //返回节点的左兄弟节点
    Btnode<ElemType>* LeftSibling(Btnode<ElemType> *p);

    //返回节点的右兄弟节点
    Btnode<ElemType>* RightSibling(Btnode<ElemType> *p);

    //先序递归遍历二叉树的接口函数
    void PreorderTraverse(void(*visit)(const ElemType &));

    //先序非递归遍历二叉树的接口函数
    void PreorderTraverseNoRecursive(void(*visit)(const ElemType &));

    //中序递归遍历二叉树的接口函数
    void InordTraverse(void(*visit)(const ElemType &));

    //后序递归遍历二叉树的接口函数
    void PostorderTraverse(void(*visit)(const ElemType &));


    //层序遍历二叉树
    void LevelTraverse(void(*visit)(const ElemType &e));


private:
    Btnode<ElemType> *m_root;   //二叉树根节点指针

    //复制二叉树
    Btnode<ElemType> *_Copy(Btnode<ElemType> *);

    //按以先序次序输入节点值的方式建立二叉树
    void _Create1(Btnode<ElemType> * &, ElemType ch[], const ElemType &, int &);


    //销毁二叉树
    void _Destroy(Btnode<ElemType> * &);

    //求二叉树的深度
    int _Depth(Btnode<ElemType> *);

    //返回二叉树中元素值为e的节点的指针
    Btnode<ElemType> * _Locate(Btnode<ElemType>*, const ElemType &);

    //返回e节点的双亲节点指针
    Btnode<ElemType> * _Parent(Btnode<ElemType>*, Btnode<ElemType>*);

    //先序递归遍历二叉树
    void _PreorderTraverse(Btnode<ElemType>*T, void(*visit)(const ElemType  &e));

    //中序递归遍历二叉树
    void _InorderTraverse(Btnode<ElemType>*T, void(*visit)(const ElemType  &e));

    //后序递归遍历二叉树
    void _PostorderTraverse(Btnode<ElemType>*T, void(*visit)(const ElemType  &e));

};

#endif

.cpp

 // #include "BinaryTree.h"
#include <iostream>
#include <stack>
#include <queue>
#include "BinaryTree.h"
using namespace std;



//先序递归遍历二叉树
template<class ElemType>
void BinaryTree<ElemType>::_PreorderTraverse(Btnode<ElemType>*T, void(*visit)
                                             (const ElemType  &e))
{
    if (T)
    {
        visit(T->Data);
        _PreorderTraverse(T->Lchild, visit);
        _PreorderTraverse(T->Rchild, visit);
    }
}

//先序递归遍历二叉树的接口函数
template<class ElemType>
void BinaryTree<ElemType>::PreorderTraverse(void(*visit)(const ElemType &))
{
    _PreorderTraverse(m_root, visit);
}

//中序递归遍历二叉树
template<class ElemType>
void BinaryTree<ElemType>::_InorderTraverse(Btnode<ElemType>*T, void(*visit)
                                            (const ElemType  &e))
{
    if (T)
    {
        _InorderTraverse(T->Lchild, visit);
        visit(T->Data);
        _InorderTraverse(T->Rchild, visit);
    }
}

//中序递归遍历二叉树的接口函数
template<class ElemType>
void BinaryTree<ElemType>::InordTraverse(void(*visit)(const ElemType &))
{
    _InorderTraverse(m_root, visit);
}

//后序递归遍历二叉树
template<class ElemType>
void BinaryTree<ElemType>::_PostorderTraverse(Btnode<ElemType>*T, void(*visit)
                                              (const ElemType  &e))
{
    if (T)
    {
        _PostorderTraverse(T->Lchild, visit);
        _PostorderTraverse(T->Rchild, visit);
        visit(T->Data);
    }
}

//后序递归遍历二叉树的接口函数
template<class ElemType>
void BinaryTree<ElemType>::PostorderTraverse(void(*visit)(const ElemType &))
{
    _PostorderTraverse(m_root, visit);
}


//按以先序次序输入节点值的方式建立二叉树
template<class ElemType>
void BinaryTree<ElemType>::_Create1(Btnode<ElemType> * &T,
                                    ElemType ch[], const ElemType &c, int &i)
{
    if (ch[i] == c) //c为特殊数据，如#、￥，用以标示空指针
    {
        T = NULL;
    }
    else
    {
        T = new Btnode<ElemType>;
        //T = (Btnode<ElemType> *)malloc(sizeof(Btnode<ElemType>));
        T->Data = ch[i];
        _Create1(T->Lchild, ch, c, ++i);
        _Create1(T->Rchild, ch, c, ++i);
    }
}

//按以先序次序输入节点值的方式建立二叉树的接口函数
template<class ElemType>
void BinaryTree<ElemType>::Create1(ElemType ch[], const ElemType &c)
{
    int i = 0;
    _Create1(m_root, ch, c, i);
}

//销毁二叉树
template<class ElemType>
void BinaryTree<ElemType>::_Destroy(Btnode<ElemType> * &T)
{
    if (T)
    {
        _Destroy(T->Lchild);
        _Destroy(T->Rchild);
        delete T;
    }
    T = NULL;
}

//求二叉树的深度
template<class ElemType>
int BinaryTree<ElemType>::_Depth(Btnode<ElemType> *T)
{
    if (!T)
    {
        return 0;
    }
    int h1, h2;
    h1 = _Depth(T->Lchild);
    h2 = _Depth(T->Rchild);
    return h1 > h2 ? h1 + 1 : h2 + 1;
}

//层序遍历二叉树--利用队列
template<class ElemType>
void BinaryTree<ElemType>::LevelTraverse(void(*visit)(const ElemType &e))
{
    queue<Btnode<ElemType>*> Q;
    if (m_root)
    {
        Q.push(m_root);     //根指针进队
    }

    while (!Q.empty())
    {
        Btnode < ElemType> *p;
        p = Q.front();       //取队头指针
        Q.pop();             //出队
        visit(p->Data);      //访问队头指针所指元素
        if (p->Lchild)       
        {
            Q.push(p->Lchild);//非空的左孩子的指针进队
        }
        if (p->Rchild)       
        {
            Q.push(p->Rchild);//非空的左孩子的指针进队
        }
    }
}


// 返回节点的左兄弟节点
template<class ElemType>
Btnode<ElemType>* BinaryTree<ElemType>::LeftSibling(Btnode<ElemType> *p)
{
    Btnode<ElemType> * father;
    father = Parent(p);
    if (father && father->Rchild == p)
    {
        return father->Lchild;
    }
    return NULL;
}

//返回节点的右兄弟节点
template<class ElemType>
Btnode<ElemType>* BinaryTree<ElemType>::RightSibling(Btnode<ElemType> *p)
{
    Btnode<ElemType> * father;
    father = Parent(p);
    if (father && father->Lchild == p)
    {
        return father->Rchild;
    }
    return NULL;
}

//复制一颗子二叉树
template<class ElemType>
Btnode<ElemType>* BinaryTree<ElemType>::_Copy(Btnode<ElemType> *T)
{
    if (T==NULL)
    {
        return NULL;
    }

    Btnode<ElemType> *p;
    p = new Btnode<ElemType>;
    p->Data = T->Data;
    p->Lchild = _Copy(T->Lchild);
    p->Rchild = _Copy(T->Rchild);
    return p;
}

//返回二叉树中元素值为e的节点的指针
template<class ElemType>
Btnode<ElemType>* BinaryTree<ElemType>::_Locate(Btnode<ElemType>*bt, const ElemType &e)
{
    if (!bt || bt->Data == e)
    {
        return bt;
    }

    Btnode<ElemType> *q;
    q = _Locate(bt->Lchild, e);
    if (q)
    {
        return q;
    }

    q = _Locate(bt->Rchild, e);
    return q;
}


//返回e节点的双亲节点指针
template<class ElemType>
Btnode<ElemType>* BinaryTree<ElemType>::_Parent(Btnode<ElemType>* T, Btnode<ElemType>*p)
{
    if (T==NULL || T == p)
    {
        return NULL;
    }
    if (T->Lchild == p || T->Rchild==p)
    {
        return T;
    }
    Btnode<ElemType> *q;
    q = _Parent(T->Lchild, p);
    if (q)
        return q;
    q = _Parent(T->Rchild, p);
    if (q)
        return q;
}







#include <iostream>
#include "BinaryTree.h"
using namespace std;

  void Print(const char &c) //遍历中访问的具体操作
  {
    cout << c << "\t";
  }

  int main()
  {
    cout << "-- 二叉树部分基本操作的演示实例--" << endl << endl;

    BinaryTree<char> bt1;
    char c = '#';
    char e, ch1[256];
    cout << "请按先序方式输入所需建的树的数据（此处空指针用 # 表示，数据用以建立对象：" << endl;
    cin >> ch1;
    bt1.Create1(ch1, c);
    cout << endl;

    cout << "当前二叉树的深度是:";
    cout << bt1.Depth() << endl;

    cout << "对当前二叉树先序递归遍历的结果是：" << endl;
    bt1.PreorderTraverse(Print);
    cout << endl;

    cout << "对当前二叉树中序递归遍历的结果是：" << endl;
    bt1.InordTraverse(Print);
    cout << endl;

    cout << "对当前二叉树后序递归遍历的结果是：" << endl;
    bt1.PostorderTraverse(Print);
    cout << endl;

    cout << "对当前二叉树按层次遍历的结果是：" << endl;
    bt1.LevelTraverse(Print);
    cout << endl;

    Btnode<char> *p, *q;
    p = bt1.Root();
    if (p)
    {
        cout << "当前二叉树的根：";
        cout << bt1.Root()->Data << endl;
    }
    else
        cout << "当前二叉树是空树" << endl;

    cout << "请输入当前二叉树中的一个值：" << endl;
    cin >> e;
    p = bt1.Locate(e);
    if (p)
    {
        cout << "当前节点的双亲是：" << endl;
        q = bt1.Parent(p);
        if (q)
        {
            cout << q->Data << endl;
        }
        else
            cout << "无" << endl;

        cout << "当前节点的左孩子是：" << endl;
        q = bt1.LeftChild(p);
        if (q)
            cout << q->Data << endl;
        else
            cout << "无" << endl;

        cout << "当前节点的右孩子是：" << endl;
        q = bt1.RightChild(p);
        if (q)
            cout << q->Data << endl;
        else
            cout << "无" << endl;

        cout << "当前节点的左兄弟是：" << endl;
        q = bt1.LeftSibling(p);
        if (q)
            cout << q->Data << endl;
        else
            cout << "无" << endl;

        cout << "当前节点的右兄弟是：" << endl;
        q = bt1.RightSibling(p);
        if (q)
            cout << q->Data << endl;
        else
            cout << "无" << endl;

    }
    else
        cout << "当前树中无此节点" << endl;


    system("pause");
    return 0;

  }

Answer 1

http://blog.csdn.net/jobsxiao/article/details/7848343