Summary

1. Traversal: left and right roots first; Middle order traversal: left root right; Post order traversal: left and right roots.
2. If you select a hierarchy to build a tree, you need a chained queue to assist the implementation (specify, don't ask why).
3. The specific operation process of the auxiliary queue (key understanding): the data field p of the queue node stores the address of the tree node (BiTNode *p type). The head pointer phead points to the head of the queue, the tail pointer ptail points to the tail of the queue, and the queue pointer pCur always points to the current operation position. The current operation position refers to: when a new node is added to the binary tree, The new node is the child of the tree node (the data field of the queue node) pointed to by the queue pointer pCur. At this time, if the left child of the tree node pointed to by pCur is empty, set the new node as the left child of the tree node, and join the queue through tail interpolation to update the tail pointer; If the right child is empty at this time, set the new node as the right child of the tree node and update the end of the queue pointer, because the left and right children of the tree node pointed to by the pCur pointer are full at this time, making the pCur pointer move to the right. The next time the new node joins the queue, the left child of the tree node pointed to by the pCur pointer will be empty again.
4. The difficulty of hierarchical tree building is that it is complex and difficult to understand. Finally, it can be summarized: define tree nodes and chain queue nodes. The data field of queue nodes is the address of tree nodes (BiTNode *p type). When the tree node enters the tree, first enter the queue node through the tail insertion method, and get the address of the corresponding tree node through the data field of the queue node pointed to by the pCur pointer, then empty the left and right children, and then enter the tree.
5. In this code, pCur is redefined every time the tree is built, so at the end of the tree building, release and set it to NULL. If you don't do so, you can set pCur as a global variable. You can also define the head and tail pointers inside the queue, which can make the tree building function BuildBinaryTree() pass fewer parameters. In short, there are many methods that can be implemented.

Code practice

#include <iostream>

#define MaxSize 10 / / the maximum number of elements in the stack

using namespace std;

typedef char ElemType;

// tree
struct BiTNode {
    ElemType data;            // Data domain
    BiTNode *lchild, *rchild; // Left child, right child
};

// The auxiliary queue node, not the leading node, is accessed through the header pointer phead
struct LinkNode {
    BiTNode *p; // Address of the corresponding node in the tree
    LinkNode *pNext;
};

typedef BiTNode *BiTree;     // Referential binary tree
typedef LinkNode *LinkQueue; // Referential chain queue

// Tree initialization
bool InitTree(BiTree &T) {
    T = NULL;
    return true;
}

//Hierarchical tree building
void BuildBinaryTree(BiTree &T, LinkNode *&phead, LinkNode *&ptail, ElemType val) {
    // If you apply for space here, you can't use new. It will enter a dead cycle. I don't know why
    BiTNode *pTreeNew = (BiTNode *)calloc(1, sizeof(BiTNode)); // Apply for space for tree nodes
    LinkNode *pQueueNew = (LinkNode *)calloc(1, sizeof(LinkNode)); // Apply for space for queue nodes
    LinkNode *pCur = phead; // Always point to the current operating position

    pTreeNew->data = val;    // Tree node assignment
    pQueueNew->p = pTreeNew; // The data field of the new node of the queue is the new node of the tree

    if (T == NULL) { // When the tree is empty, the new node is set as the tree root
        T = pTreeNew;
        phead = pQueueNew;
        ptail = pQueueNew;
    } else {
        ptail->pNext = pQueueNew; //Tail interpolation
        ptail = pQueueNew;        // Update tail pointer

        if (pCur->p->lchild == NULL) { // Left child is empty
            pCur->p->lchild = pTreeNew;
        } else if (pCur->p->rchild == NULL) { // Right child is empty
            pCur->p->rchild = pTreeNew;
            phead = pCur->pNext; //The left and right children of this node are full, and the team head pointer moves back
            free(pCur); // In this code, PCur is redefined every time the tree is built, so at the end of building the tree, it should be released and set to NULL 
            pCur = NULL;
        }
    }
}

//Preorder traversal (depth first traversal): about the root
void PreOrder(BiTNode *p) {
    if (p != NULL) {
        putchar(p->data);
        PreOrder(p->lchild);
        PreOrder(p->rchild);
    }
}

// Middle order traversal: left root right
void InOrder(BiTNode *p) {
    if (p != NULL) {
        InOrder(p->lchild);
        putchar(p->data);
        InOrder(p->rchild);
    }
}

// Post order traversal: left and right roots
void PostOrder(BiTNode *p) {
    if (p != NULL) {
        PostOrder(p->lchild);
        PostOrder(p->rchild);
        putchar(p->data);
    }
}

int main() {
    ElemType val;
    BiTree T;
    InitTree(T);

    LinkNode *phead = NULL;
    LinkNode *ptail = NULL; // Head pointer
    while (scanf("%c", &val) != EOF) {
        if (val == '\n') {
            break;
        } else {
            BuildBinaryTree(T, phead, ptail, val);
        }
    }

    cout << "-----Preorder traversal-----" << endl;
    PreOrder(T);
    cout << endl;

    cout << "-----Middle order traversal-----" << endl;
    InOrder(T);
    cout << endl;

    cout << "-----Postorder traversal-----" << endl;
    PostOrder(T);
    cout << endl;

    return 0;
}