根据二叉树先序遍历和中序遍历还原二叉树,求二叉树层次遍历
没有输出层次遍历,不知道错在哪里
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h
typedef char DataType;
typedef struct BiTNode{
DataType data;
struct BiTNode *lchild, *rchild;
}LinkBiTree,*BiTree;
void CreateBiTree(LinkBiTree **T,char *PreStr,char *InStr,int L1,int R1,int L2,int R2){//递归
(*T) = (LinkBiTree *)malloc(sizeof(LinkBiTree));
(*T)->data = PreStr[L1];
int root;
for (root = 0; root <= R2; root++){
if (PreStr[L1] == InStr[root])
{
break;
}
}
if (root - L2 != 0){
CreateBiTree(&(*T)->lchild, PreStr, InStr, L1 + 1, L1 + (root - L2), L2, root - 1);
}else{
(*T)->lchild = NULL;
}
if (R2 - root != 0){
CreateBiTree(&(*T)->rchild, PreStr, InStr, R1 - (R2 - root) + 1, R1, root + 1, R2);
}else{
(*T)->rchild = NULL;
}
}
// 后序
void PostOrderTraverse(LinkBiTree *T){
if(T){
PostOrderTraverse(T->lchild);
PostOrderTraverse(T->rchild);
printf("%c ", T->data);
}
}
//先序
void PreTraverse(LinkBiTree *T){
if(T){
printf("%c ", T->data);
PreTraverse(T->lchild);
PreTraverse(T->rchild);
}
}
//中序
void InTraverse(LinkBiTree *T){
if(T){
InTraverse(T->lchild);
printf("%c ", T->data);
InTraverse(T->rchild);
}
}
typedef struct LinkNode {
LinkBiTree* data;
LinkNode* next;
}LinkNode;
typedef struct {
LinkNode* front, * rear;//队头队尾
}LinkQueue;
void InitQueue(LinkQueue& Q) {
//初始化时,front,rear都指向头节点
Q.front = Q.rear = (LinkNode*)malloc(sizeof(LinkNode));
Q.front->next = NULL;
}
void EnQueue(LinkQueue& Q,BiTree p) {
LinkNode* s = (LinkNode*)malloc(sizeof(LinkNode));
s->data = p;
s->next = NULL;
Q.rear->next = s;
Q.rear = s;
}
bool DeQueue(LinkQueue& Q, BiTree* p) {
if (Q.front == Q.rear)
return false; //空队
LinkNode* x = Q.front->next;
*p = x->data;
Q.front = x->next;
if (x == Q.rear) {
Q.rear = Q.front;
}
return true;
}
void visit(BiTree p) {
printf("%c", p->data);
}
int IsEmpty(LinkQueue &Q){
if(Q.rear==Q.rear){
return 1;
}else{
return 0;
}
}
void LevelTraverse(LinkBiTree* T) {
LinkQueue Q;
InitQueue(Q);
BiTree p=(LinkBiTree*)malloc(sizeof(LinkBiTree));
EnQueue(Q, T);
while (!IsEmpty(Q)) {
DeQueue(Q, &p);
visit(p);
if (p->lchild != NULL)
EnQueue(Q, p->lchild);
if (p->rchild != NULL)
EnQueue(Q, p->rchild);
}
}
int main(){
char PreStr[30], InStr[30];
printf("请输入先序序列:");
scanf("%s", PreStr);
printf("请输入中序序列:");
scanf("%s", InStr);
int len1 = strlen(PreStr);
int len2 = strlen(InStr);
LinkBiTree *T;
CreateBiTree(&T, PreStr, InStr, 0, len1 - 1, 0, len2 - 1);
printf("后序遍历二叉树:");
PostOrderTraverse(T);
printf("\n");
printf("先序遍历二叉树:");
PreTraverse(T);
printf("\n");
printf("中序遍历二叉树:");
InTraverse(T);
printf("\n");
printf("层次遍历二叉树:");
LevelTraverse(T);
printf("\n");
return 0;
}
层序遍历P的定义那里改为
BiTree p=T;
EnQuene(Q,p);