建立如图所示的二叉树,为什么输入到第五个数据时程序就崩溃了
(每次输入一个学号加一个姓名,先序输入)
#include<iostream>
#include<string>
using namespace std;
#include<stack>
#include<queue>
typedef struct
{
int num; //学号
string name; //姓名
} student;
typedef struct Binode { //二叉树定义
student data;
Binode* lchild, * rchild;
}*binode;
bool creatbitree(binode&t) { //先序遍历建立二叉树
t = new Binode;
int tnum;
char tname[10];
cin >> tnum;
cin >> tname;
if (tnum == -1) return false;
t->data.num = tnum;
t->data.name= tname;
creatbitree(t->lchild);
creatbitree(t->rchild);
return true;
}
/*elementype input;
cout << "请输入数据(先序遍历创建树)" << endl;
cin >> input;
if (input == -1) return false;
t = new Binode;
t->data = input;
DLRcreatbitree(t->lchild);
DLRcreatbitree(t->rchild);
return true;*/
bool vist(binode& t) {
if (!t) return false;
cout << t->data.num << '/t';
cout << t->data.name;
return true;
}
bool previst(binode& t) { //先序遍历
if (t == nullptr) return true;
//if(!t->lchild&&!t->rchild) (打印叶子)
vist(t);
previst(t->lchild);
previst(t->rchild);
return true;
}
bool invist(binode& t) {//中序遍历
if (t == nullptr) {
return true;
}
invist(t->lchild);
vist(t);
invist(t->rchild);
return true;
}
bool postvist(binode& t) {//后序遍历
if (t == nullptr) {
return true;
}
postvist(t->lchild);
postvist(t->rchild);
vist(t);
return true;
}
void levelorder(binode& t) {//层次遍历
queue<binode>q;//创建一个队列并初始化
if (t) return;//若树为空,则返回
q.push(t); //将树的第一层(根节点)入队
while (!q.empty())//当队列不为空时
{
t = q.front();
cout << t->data.num<<" "<<t->data.name << endl;//弹出一个元素,并将其左右孩子保存在队列中
if (t->lchild) q.push(t->lchild);
if (t->rchild) q.push(t->rchild);
}
}
int main() {
cout << "请依次输入根节点,及其左右孩子,若该节点为空,则输入-1" << endl;
binode t = new Binode;
if (creatbitree(t)) {
previst(t);
invist(t);
postvist(t);
levelorder(t);
}
return 0;
}
你的代码有几个错误:
(1)main函数中,binode t = new Binode;这一句,不需要new了,你creatbitree函数中已经new了。
(2)creatbitree函数中,t的左右节点没有初始化为0,导致你后面的遍历函数无法正常结束,因为指针不初始化的话,是一个非0野指针,会导致程序崩溃!!
代码修改如下,修改的地方有注释:
creatbitree函数:
bool creatbitree(binode& t) { //先序遍历建立二叉树
t = new Binode;
t->lchild = 0; //修改,初始化变量
t->rchild = 0; //修改,初始化变量
int tnum;
char tname[10];
cin >> tnum;
cin >> tname;
if (tnum == -1) //修改,如果没有节点,
{
delete t;
t = 0;
return false;
}
t->data.num = tnum;
t->data.name = tname;
creatbitree(t->lchild);
creatbitree(t->rchild);
return true;
}
vist函数,这里只是加了一个回车符,方便查看信息,否则信息都连到一起了
bool vist(binode& t) {
if (!t) return false;
cout << t->data.num << '/t';
cout << t->data.name << endl; //修改 ,增加一个回车符,方便查看
return true;
}
main函数:
int main() {
cout << "请依次输入根节点,及其左右孩子,若该节点为空,则输入-1" << endl;
binode t = 0;// new Binode; //修改,t再create函数中已经new了,这里没必要重复new
if (creatbitree(t)) {
previst(t);
invist(t);
postvist(t);
levelorder(t);
}
return 0;
}
1、Binode的两个指针未初始为null
2、creatbitree进入后先new Binode,后面如果输入-1,这个节点其实不应该存在。另外为了方便快速测试,输入-11表示后面所有子节点都为空,可快速结束,避免输入很多-1
3、if (t) 这个判断t非0时为true,对于一个指针地址是非0的,要改为if (t==nullptr);q.front()是拿队列第一个元素,元素还留在队列里面,会导致死循环,取完应弹出元素。
修改后的程序如下:
#include<iostream>
#include<string>
#include<stack>
#include<queue>
using namespace std;
typedef struct {
int num; //学号
string name; //姓名
} student;
typedef struct Binode { //二叉树定义
student data;
Binode *lchild = nullptr, *rchild = nullptr;
} *binode;
int treeInputEnd = 0;
bool creatbitree(binode &t) { //先序遍历建立二叉树
if (treeInputEnd) return false;
int tnum;
char tname[10];
cin >> tnum;
if (tnum == -1) return false;
if (tnum == -11) {treeInputEnd = 1; return false;}
cin >> tname;
t = new Binode;
t->data.num = tnum;
t->data.name = tname;
creatbitree(t->lchild);
creatbitree(t->rchild);
return true;
}
bool vist(binode &t) {
if (!t) return false;
cout << t->data.num << ':';
cout << t->data.name << ',';
return true;
}
bool previst(binode &t) { //先序遍历
if (t == nullptr) return true;
vist(t);
previst(t->lchild);
previst(t->rchild);
return true;
}
bool invist(binode &t) {//中序遍历
if (t == nullptr) {
return true;
}
invist(t->lchild);
vist(t);
invist(t->rchild);
return true;
}
bool postvist(binode &t) {//后序遍历
if (t == nullptr) {
return true;
}
postvist(t->lchild);
postvist(t->rchild);
vist(t);
return true;
}
void levelorder(binode &t) {//层次遍历
queue<binode> q;//创建一个队列并初始化
if (t==nullptr) return;//若树为空,则返回
q.push(t); //将树的第一层(根节点)入队
while (!q.empty())//当队列不为空时
{
t = q.front();
q.pop();
cout << t->data.num << " " << t->data.name << endl;//弹出一个元素,并将其左右孩子保存在队列中
if (t->lchild) q.push(t->lchild);
if (t->rchild) q.push(t->rchild);
}
}
int main() {
cout << "请依次输入根节点,及其左右孩子,若该节点为空,则输入-1" << endl;
binode t = nullptr;
if (creatbitree(t)) {
previst(t);
cout << endl;
invist(t);
cout << endl;
postvist(t);
cout << endl;
levelorder(t);
}
return 0;
}
您好,我是有问必答小助手,您的问题已经有小伙伴帮您解答,感谢您对有问必答的支持与关注!