创建出来的二叉树,后序序列和层次序列输出值不对
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define M 50
typedef struct BiNode
{
char data;
struct BiNode* lchild, * rchild;
}BiNode, * BiTree;
typedef struct Queue
{
BiTree data[M];
int front;
int rear;
}Queue;
void InitQueue(Queue& Q)
{
Q.front = Q.rear = 0;
}
void EnQueue(Queue& Q, BiTree T)
{
if ((Q.rear + 1) % M == Q.front)
return;
Q.data[Q.rear] = T;
Q.rear = (Q.rear + 1) % M;
}
void DeQueue(Queue& Q, BiTree& T)
{
if (Q.rear == Q.front)
return;
T = Q.data[Q.front];
Q.front = (Q.front + 1) % M;
}
BiTree CreateBiTree(char pre[], char mid[], int preL, int preR, int midL, int midR)
{
if (preL <= preR)
{
int i = 0, llen = 0, rlen = 0;
for (i = 0; mid[i] != pre[preL], i < preL; i++);//找到根节点在中序序列中的位置
llen = i - midL;//左子树的长度
rlen = midR - i;//右子树的长度
BiTree T = new BiNode;
T->data = pre[preL];
T->lchild = CreateBiTree(pre, mid, preL + 1, preL + llen, midL, midL + llen - 1);//递归创建二叉树
T->rchild = CreateBiTree(pre, mid, preL + llen + 1, preR, midL + llen + 1, midR);
return T;
}
else
return NULL;
}
void LevelTraverse(BiTree T)
{
BiTree p;
Queue Q;
InitQueue(Q);
if (T)
{
Q.data[Q.rear] = T;
Q.rear = (Q.rear + 1) % M;
while (Q.front != Q.rear)
{
p = Q.data[Q.front];
printf("%c ", p->data);
Q.front = (Q.front + 1) % M;
if (p->lchild)
{
Q.data[Q.rear] = p->lchild;
Q.rear = (Q.rear + 1) % M;
}
if (p->rchild)
{
Q.data[Q.rear] = p->rchild;
Q.rear = (Q.rear + 1) % M;
}
}
}
}
void PostTraverse(BiTree T)
{
if (T)
{
PostTraverse(T->lchild);
PostTraverse(T->rchild);
printf("%c ", T->data);
}
}
int main()
{
char pre[100], mid[100];
int n, i;
printf("请输入结点数:\n");
scanf_s("%d", &n);
printf("请输入先序序列:\n");
for (i = 0; i < n; i++)
scanf_s("%c", &pre[i]);
printf("请输入中序序列:\n");
for (i = 0; i < n; i++)
scanf_s("%c", &mid[i]);
BiTree T = CreateBiTree(pre, mid, 0, n - 1, 0, n - 1);
printf("层次序列如下:\n");
LevelTraverse(T);
printf("\n");
printf("后序序列如下:\n");
PostTraverse(T);
printf("\n");
return 0;
}
我输入的先序序列和中序序列如图
运行结果如图
可以看到输出结果不仅序列不对,而且少了对F结点的输出;
创建二叉树的函数我用笔画了一下应该是没有问题的,同样,层次遍历和后序遍历的函数应该也是正确的,不知道问题出在哪里。