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;
}