#include <stdio.h>
#include <stdlib.h>

#define ElemType char
//结构体定义
typedef struct Node {
    ElemType data;
    struct Node *LChild;
    struct Node *RChild;
} BinNode, *BinTree;

typedef struct QueueNode {
    BinTree data;
    struct QueueNode *next;
} QueueNode;

typedef struct LinkQueue
{
    QueueNode *front;
    QueueNode *rear;
} LinkQueue;

/*
 * 结点的层次、打印位置、
 * 是否在同一层次和与输出的空格数
 */
typedef struct NodeInfo {
    int level;
    int pos;
    int enter;
    int spacenum;
} NodeInfo;

typedef struct QueueNodeInfo {
    NodeInfo data;
    struct QueueNodeInfo *next;
} QueueNodeInfo;

typedef struct NodeInfoQueue {
    QueueNodeInfo *front;
    QueueNodeInfo *rear;
} NodeInfoQueue;

//函数声明
int menu_select();
BinTree CreateBinTree(BinTree bt);
void LevelOrder(BinTree bt);
void InitQueue(LinkQueue *Q);
void EnQueue(LinkQueue *Q, BinTree bt);
BinTree DeQueue(LinkQueue *Q);
void InitQueueInfo(NodeInfoQueue *QI);
void EnQueueInfo(NodeInfoQueue *QI, NodeInfo NI);
NodeInfo DeQueueInfo(NodeInfoQueue *QI);
void DisplayTree(BinTree bt, int dataWidth, int screenWidth);


// main()函数
int main() {
    BinTree bt;
    int screenWidth=64;
    int dataWidth=2;
   
    for (;;) {
        switch(menu_select()) {
        case 1:
            printf("1、建立二叉树\n");
            bt = CreateBinTree(bt);
            break;
        case 2:
            printf("2、层次遍历\n");
            LevelOrder(bt);
            break;
        case 3:
            printf("3、显示二叉树\n");
            DisplayTree(bt, dataWidth, screenWidth);
            break;
        case 0:
            printf("再见！！\n");
            free(bt);
            return 0;
        }
    }
}

//菜单驱动程序
int menu_select() {
    int sn;
    printf("=========功能菜单============\n");
    printf("   1、建立二叉树\n");
    printf("   2、层次遍历\n");
    printf("   3、显示二叉树\n");
    printf("   0、退出程序\n");
    printf("==============================\n");
    printf("   请选择0--3：");

    for (;;) {
        scanf("%d", &sn);
        getchar();
        if (sn < 0 || sn > 3)
            printf("\n输入选择错误，请重新选择 0--3：");
        else
            break;
    }
    return sn;
}

/*
  TODO：
  功能描述：创建二叉树操作
  1、按扩展的先序次序输入二叉树中结点的值，
     #字符表示空子树，创建二叉链表表示的二叉树
     (BinTree) malloc(sizeof(BinNode))，
     将字符赋给节点中的data
  例：
    输入格式：AB##C##
    二叉树：
            A
          B   C
  参数：(BinTree bt) 树的指针
  返回值： BinTree 树的指针
*/
BinTree CreateBinTree(BinTree bt) {
}

/*
  TODO：
  功能描述：执行队列初始化操作
  参数：(LinkQueue *Q) 队列结构的指针
  返回值： void
*/
void InitQueue(LinkQueue *Q) {
    QueueNode *qNode = (QueueNode *) malloc(sizeof(QueueNode));
    Q->front = qNode;
    Q->rear = qNode;
    Q->front->next = NULL;
}

/*
  TODO：
  功能描述：执行入队操作
  参数：(LinkQueue *Q, BinTree bt) 队列结构的指针与入队元素值
  返回值： void
*/
void EnQueue(LinkQueue *Q, BinTree bt) {
    QueueNode *qNode = (QueueNode *) malloc(sizeof(QueueNode));
    qNode->data = bt;
    Q->rear->next = qNode;
    Q->rear = qNode;
}

/*
  TODO：
  功能描述：执行出队操作
  参数：(LinkQueue *Q, BinTree bt) 队列结构的指针与入队元素值
  返回值： BinTree 树的节点指针
*/
BinTree DeQueue(LinkQueue *Q) {
    QueueNode *qNode = Q->front->next;
    BinTree bt = qNode->data;
    Q->front->next = qNode->next;
    if (qNode == Q->rear) {
        Q->rear = Q->front;
    }
    free(qNode);
    return bt;
}

/*
  TODO：
  功能描述：执行队列初始化操作
  参数：(NodeInfoQueue *QI) 节点队列信息结构的指针
  返回值： void
*/
void InitQueueInfo(NodeInfoQueue *QI) {
    QueueNodeInfo *qNodeInfo = (QueueNodeInfo *) malloc(sizeof(QueueNodeInfo));
    QI->front = qNodeInfo;
    QI->rear = qNodeInfo;
    QI->front->next = NULL;
}

/*
  TODO：
  功能描述：执行入队操作
  参数：(NodeInfoQueue *QI, NodeInfo NI) 节点队列信息结构的指针与入队元素值
  返回值： void
*/
void EnQueueInfo(NodeInfoQueue *QI, NodeInfo NI) {
    QueueNodeInfo *qNodeInfo = (QueueNodeInfo *) malloc(sizeof(QueueNodeInfo));
    qNodeInfo->data = NI;
    QI->rear->next = qNodeInfo;
    QI->rear = qNodeInfo;
}

/*
  TODO：
  功能描述：执行出队操作
  参数：(NodeInfoQueue *QI) 队列结构的指针
  返回值： NodeInfo 树的节点的信息
*/
NodeInfo DeQueueInfo(NodeInfoQueue *QI) {
    QueueNodeInfo *qNodeInfo = QI->front->next;
    NodeInfo nInfo = qNodeInfo->data;
    QI->front->next = qNodeInfo->next;
    if (qNodeInfo == QI->rear) {
        QI->rear = QI->front;
    }
    free(qNodeInfo);
    return nInfo;
}

// 换行
void LineFeed() {
    printf("\n");
}

// 空格
void vBlank() {
    printf(" ");
}

// 数据展示
void Visit(ElemType data) {
    printf("%2c", data);
}

/*
  TODO：
  功能描述：层次遍历二叉树操作
  1、从根节点开始，从上至下逐层遍历，
  在同一层中，从左到右逐一显示。
  2、显示全部节点末尾调用换行函数
  3、换行：
     调用函数 void LineFeed()
     数据打印：
     调用函数 void Visit(ElemType data)
  参数： (BinTree bt) 树的指针
  返回值： void
*/
void LevelOrder(BinTree bt) {
}
/*
  TODO：
  功能描述：显示二叉树操作
  1、从根节点开始，从上至下逐层遍历，
  在同一层中，从左到右逐一访问。
  2、数据值的最大宽度dataWidth=2以及屏幕的宽度screenWidth=64。
  第i层的偏移量（offset）为screenWidth/2的i次幂。
  第i层的每个结点的位置是访问第i-1层其双亲结点时确定的。
  假设其双亲位置是（i-1，parentPos）。
  若其第i层的结点是左孩子，那么它的位置是（i，parentPos-offset）；
  若是右孩子则位置为（i，parentPos+offset）。
  3、用两个队列和按层遍历树中的结点。
  队列LinkQueue中存放结点，二队列NodeInfoQueue中则以记录类型Info存放结点的层次和打印位置。
  当结点被加入到LinkQueue中时，相应的打印信息也被存储到NodeInfoQueue中
  4、显示全部节点末尾调用换行函数
  5、换行：
     调用函数 void LineFeed()
     空格：
     调用函数 void vBlank()
     数据打印：
     调用函数 void Visit(ElemType data)

  参数：(BinTree bt, int dataWidth, int screenWidth) 树的指针数据值的最大宽度与屏幕的宽度
  返回值：void
*/
void  DisplayTree(BinTree bt, int dataWidth, int screenWidth) {
}