编辑代码

/*
9. 已知一棵二叉树的数据元素为字符，分别输入其前序遍历和中序遍历的字符串，试编程构造该二叉树的二叉链表存储结构，并按层次遍历该二叉树，输出按层次遍历的字符 b串。
*/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<stdbool.h>
/*
前序遍历字符串  preorder_char[]
中序遍历字符串  inorder_char[]
字符串的长度    number
*/
#define SIZE 100
typedef char TElemType;
#define FALSE -1
#define MAX_SIZE 128
typedef struct BiTNode{
//二叉树二叉链表存储表示，仿照页127
    TElemType data;
    struct BiTNode *LChild,*RChild;//左右孩子指针
}BiTNode,*BiTree;

typedef BiTree Status;

Status CreateBiTree_DLR(char pre[],char in[],int number){
//按前、中序遍历构造二叉树，仿照
    if(!number)return 0;  //FALSE
    int i=0;
    while(i<number && in[i]!=pre[0])i++;
    int Lnumber=i;
    int Rnumber=number-i-1;
    BiTNode *T=(BiTNode *)malloc(sizeof(BiTNode))  ; 
    T->data=pre[0];
    T->LChild=CreateBiTree_DLR(&pre[1],&in[0],Lnumber);
    T->RChild=CreateBiTree_DLR(&pre[Lnumber+1],&in[Lnumber+1],Rnumber);
    return T;
}

typedef struct Queue {      
    int     front;          
    int     rear;           
    BiTNode* data[MAX_SIZE];
} SqQueue;
bool emptyQueue(SqQueue* q) {
    // 首指针和尾指针相等，说明为空。空-返回真，不空-返回假
    if (q->front == q->rear) {
        return true;
    }
    return false;
}                  
bool enQueue(SqQueue* q, BiTNode* node) {
    // 判断队列是否满了。满（插入失败）-返回假，不满（插入成功）-返回真
    if (q->rear == MAX_SIZE - 1) {
        return false;
    }
    q->rear++;               // 头指针加 1
    q->data[q->rear] = node; // 传值
    return true;
}
bool deQueue(SqQueue* q, BiTNode** node) {
    // 判断是否空了。空（取出失败）-返回假，不空（取出成功）-返回真
    if (q->front == q->rear) {
        return false;
    }
    q->front++;                // 尾指针加 1
    *node = q->data[q->front]; // 取值
    return true;
}
void initQueue(SqQueue** q) {
    if (!((*q) = (SqQueue*)malloc(sizeof(SqQueue)))) {
        printf("内存分配失败！");
        exit(-1);
    }
    (*q)->front = (*q)->rear = -1; // 置 -1
}
void levelOrder(BiTNode* BT) {
    SqQueue* q;       
    initQueue(&q);    
    if (BT != NULL) { 
        enQueue(q, BT);
    }
    // 一层一层的把节点存入队列，当没有孩子节点时就不再循环
    while (!emptyQueue(q)) {      
        deQueue(q, &BT);         
        printf("%c", BT->data); 
        if (BT->LChild != NULL) { 
            enQueue(q, BT->LChild);
        }
        if (BT->RChild != NULL) { 
            enQueue(q, BT->RChild);
        }
    }
}


int main () {
    char preorder_char[SIZE],inorder_char[SIZE];  //n=100
    //分别输入其前序遍历和中序遍历的字符串
    //ABCDEFGHIJKL
    //CEDBFAIHKJGL
    printf("DLR:");gets(preorder_char);
    printf("LDR:");gets(inorder_char);
    //测试结点//
    //printf("测试结点：\n    你所输入的:\n         1.前序遍历序列：%s\n         2.中序遍历序列：%s\n",preorder_char,inorder_char);

    BiTNode *C;
    //构造
    C=CreateBiTree_DLR(preorder_char, inorder_char, strlen(preorder_char));

    //按层次遍历输出
    //ABGCFHLDIJEK
    printf("LevelOrder:");
    levelOrder(C);
    printf("\n");
    system("pause");
}