潭影-pjq

typedef char ElemType;      //我們在數據域存入字符類型的數據
typedef struct BiTNode {
    ElemType c;//數據域
    struct BiTNode* lchild, * rchild;//左、右孩子的指針
}BiTNode,*BiTree;//在后續操作中，BiTNode強調是一個結點，BiTree強調是一棵樹

typedef struct tag {
    BiTree p;           //某一個結點的指針
    struct tag* pnext;  //下一個結點的指針
}tag_t;  //在后續操作中tag_t強調這是鏈表中的一個結點

void PreOrder(BiTree T)//先序遍歷
{
    if (T != NULL)
    {
        putchar(T->c);
        PreOrder(T->lchild);
        PreOrder(T->rchild);
    }
}

int main()
{
    //開始建二叉樹
    BiTree T=NULL;//首先聲明一棵二叉樹,此時二叉樹為空
    BiTNode* pnew=NULL;//表示用于存放將要存入樹中的元素
    tag_t* phead=NULL; //在后續操作中phead始終指向輔助鏈表的頭部(這個鏈表沒帶頭結點)
    tag_t* ptail=NULL; //而ptail指向輔助鏈表的尾部
    tag_t* pcur=NULL;  //pcur表示current,即當前指向當前鏈表中的一個結點，
                       //——我暫時說不清它指向哪個結點，但是可以確定的是，它不是指向新的結點
    tag_t* listpnew=NULL;//表示新的結點
    char c;//需要被讀取的元素
    while (scanf("%c", &c) != EOF) //EOF表示讀取結束
    {
        if (c == '\n')  //注意這個判斷條件，一般都是"=="，而賦值是"="
        {
            break;      //如果c=='\n',跳出讀取，因為%c會讀取換行符，也就是它會把'\n'當作一個字符
        }
        pnew = (BiTNode*)calloc(1, sizeof(BiTNode));//用于暫存二叉樹的新結點
        pnew->c = c;                                //新結點的屬于設為讀入的元素
        listpnew = (tag_t*)calloc(1, sizeof(BiTNode));//用于將存放二叉樹新結點的地址
        listpnew->p = pnew;                           //數據域設為pnew
        if (T == NULL)
        {
            T = pnew;               //樹空則填入第一個結點
            phead = listpnew;       //并將phead，ptail，pcur，都指向listpnew
            ptail = listpnew;       //雖然每次讀入一個元素這個listpnew一直在變化成一個新的鏈表結點
            pcur = listpnew;        //但是這個phead指向的地址卻不變，相當于又一個鏈表，phead指向鏈表頭
                                    //ptail指向鏈表尾
            continue;//一定要加這個continue，表示結束這一次循環，也就是說我們添加了根節點之后，這部分if語句里的代碼就不用管了
        }
        else
        {
            ptail->pnext = listpnew; //將新元素插入鏈表尾部
            ptail = listpnew;        //ptail指向鏈表尾部
        }
        if (pcur->p->lchild == NULL)//二叉樹中的一個結點的左子樹為空
        {
            pcur->p->lchild = pnew; //將其左子樹填入新結點
        }
        else if (pcur->p->rchild == NULL)//右子樹為空
        {
            pcur->p->rchild = pnew;   //將其右子樹填入新的結點
            pcur = pcur->pnext; //當左右子樹都填入結點之后，表示這個節點的數據域，左右孩子域內都有元素了
                                //那么此時pcur就可以指向下一個鏈表中的節點了
            //比如層次建樹。前三個元素是abc，a是根節點，在a的左孩子填入b，在a的右孩子填入c，那么a就可以功成身退了
            //此時鏈表中的元素是abc，繼而將pur指向結點b，繼續在b的左右孩子域填入新結點，依此類推，直到所有元素完全填入
        }
    }
    PreOrder(T);
    //abcdefg
}