#include <iostream>
using namespace std;
typedef struct node {
char data;
struct node *lchild, *rchild;
}BTNode;//二叉树的类型定义
typedef struct {
BTNode *data[200];
int front, rear;
}SqQueue;//队的类型定义
void InitQueue(SqQueue *&q) {
q = (SqQueue*)malloc(sizeof(SqQueue));
q->front = q->rear = -1;
}
bool enQueue(SqQueue *&q, BTNode *b) {
if (q->rear == 200 - 1)
return false;
q->rear = (q->rear + 1) % 200;
q->data[q->rear] = b;
return true;
}
bool deQueue(SqQueue *&q, BTNode *b) {
if (q->front == q->rear)return false;
q->front = (q->front + 1) % 200;
b = q->data[q->front];
return true;
}
bool QueueEmpty(SqQueue *q) { return (q->front == q->rear); }
void CreatBTNode(BTNode *&b, char *str) {
BTNode *st[200], *p;
int top = -1, k, j = 0;
char ch;
b = NULL; ch = str[j];
while (ch != 0) {
switch (ch) {
case '(':top++;st[top] = p;k = 1;break;
case')':top--;break;
case',':k = 2;break;
default:p = (BTNode*)malloc(sizeof(BTNode));
p->data = ch;p->lchild = p->rchild = NULL;
if (b == NULL)
b = p;
else {
switch (k) {
case 1:st[top]->lchild = p;break;
case 2:st[top]->rchild = p;break;
}
}
}
j++;ch = str[j];
}
}
void LevelOrder(BTNode *b, char *a) {
BTNode *p;
int i = 0;
SqQueue *qu;
InitQueue(qu);
enQueue(qu, b);
while (!QueueEmpty(qu)) {
deQueue(qu, p);
a[i] = p->data;i++;
if (p->lchild != NULL)
enQueue(qu, p->lchild);
if (p->rchild != NULL)
enQueue(qu, p->rchild);
}
a[i] = 0;
}
int main() {
BTNode *M;
char str[200] = "A(B(D(,G)),C(E,F))";
CreatBTNode(M, str);//已经创建成功
char a[200];
LevelOrder(M, a);
int len, i;
len = strlen(a);
for (i = len - 1;i >= 0;i--)
cout << a[i]<<" ";
}
deQueue函数的b参数加个引用可以不崩溃,其他你再看看:
bool deQueue(SqQueue *&q, BTNode *&b) {
if (q->front == q->rear)return false;
q->front = (q->front + 1) % 200;
b = q->data[q->front];
return true;
}
把错误报告贴出来,好分析原因
deQueue函数中的p变量没有初始化
BTNode *p = new BTNode;