//
// Created by 10415 on 2022-12-15.
//

#ifndef INC_1_TREE_FUNCTION_H
#define INC_1_TREE_FUNCTION_H

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

// 定义二叉树的结构体
typedef char BiElemType;
typedef struct BiTNode{
    BiElemType c;  // 用于存储数据
    struct BiTNode *lchild;
    struct BiTNode *rchild;
}BiTNode, *BiTree;

// tag结构体是辅助队列使用的
typedef struct tag{
    BiTree p;    // 树的某一个结点的地址值
    struct tag *pnext;
}tag_t, *ptag_t;

#endif //INC_1_TREE_FUNCTION_H

#include "function.h"

// 二叉树的层次建树

int main(){
    BiTree pnew;   // 申请一个树的新结点
    BiTree tree = NULL;    // tree是指向树根的，代表树
    char c;
    ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur;
    // abcdefghij
    while(scanf("%c", &c)){
        if(c == '\n'){
            break;   // 读到换行就结束
        }
        // calloc申请的空间大小是两个参数直接相乘，并对空间进行初始化，赋值为0
        pnew = (BiTree)calloc(1, sizeof(BiTNode));
        pnew->c = c;
        listpnew = (ptag_t)calloc(1,sizeof(tag_t)); // 给队列结点申请空间
        listpnew->p = pnew;
        // 如果是树的第一个结点
        if(NULL == tree){
            tree = pnew;   // tree指向树的根节点
            phead = listpnew;   // 第一个结点既是队列头，也是队列尾
            ptail = listpnew;
            pcur = listpnew;   // pcur要指向进入树的父亲元素
        }else{
            // 让元素先入队列
            ptail->pnext = listpnew;
            ptail = listpnew;
            // 接下来把b结点放入树中
            if(NULL == pcur->p->lchild){
                pcur->p->lchild = pnew;    // pcur->p左孩子为空，就放入左孩子
            }else if(NULL == pcur->p->rchild){
                pcur->p->rchild = pnew;   // pcur->p右孩子为空，就放入右孩子
                pcur = pcur->pnext;       // 当前结点左右孩子都有了，pcur就指向下一个
            }
        }
    }
    return 0;
}