C_数据结构_链式二叉树

# include <stdio.h>
# include <malloc.h>

struct BTNode
{
    int data;
    struct BTNode * pLchild; // p 是指针   L 是左   child 是孩子
    struct BTNode * pRchild; // 表示右孩子
};

struct BTNode * CreateBTree(void); //静态创建二叉树
void PreTraverseBTree(struct BTNode * pT); //先序遍历
void InTraverseBTree(struct BTNode * pT); //中序遍历
void PostTraverseBTree(struct BTNode * pT); //后续遍历

int main(void)
{
    BTNode pT = CreateBTree(); //这里不能加 void
    
    PreTraverseBTree(pT); //先序遍历
    InTraverseBTree(pT); //中序遍历
    PostTraverseBTree(pT); //后续遍历
    
    return 0;
}

void PostTraverseBTree(struct BTNode * pT) //后续遍历
{
    if (pT != NULL)
    {
        if (NULL != pT->pLchild)
        {
            PostTraverseBTree(pT->pLchild); // pT->pLchild可以代表整个左子树
        }
        if (NULL != pT->pRchild)
        {
            PostTraverseBTree(pT->pRchild);
        }
        
        printf("%c\n", pT->data);
    } 
}

void InTraverseBTree(struct BTNode * pT) //中序遍历
{
    if (pT != NULL)
    {
        if (NULL != pT->pLchild)
        {
            InTraverseBTree(pT->pLchild); // pT->pLchild可以代表整个左子树
        }
        
        printf("%c\n", pT->data);
        
        if (NULL != pT->pRchild)
        {
            InTraverseBTree(pT->pRchild);
        }
    } 
}

void PreTraverseBTree(struct BTNode * pT) //先序遍历
{
    if (pT != NULL)
    {
        printf("%c\n", pT->data);
        
        if (NULL != pT->pLchild)
        {
            PreTraverseBTree(pT->pLchild); // pT->pLchild可以代表整个左子树
        }
        
        if (NULL != pT->pRchild)
        {
            PreTraverseBTree(pT->pRchild);
        }
    } // if 判断不能省略
    
    
/*   //伪算法

    先访问跟节点
    再先序访问左子树
    在先序访问右子树
*/
}

struct BTNode * CreateBTree(void)
{
    struct BTNode pA = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pB = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pC = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pD = (struct BTNode *)malloc(sizeof(struct BTNode));
    struct BTNode pE = (struct BTNode *)malloc(sizeof(struct BTNode));
    
    pA->data = ‘A‘;
    pB->data = ‘B‘;
    pC->data = ‘C‘;
    pD->data = ‘D‘;
    pE->data = ‘E‘;
    
    pA->pLchild = pB;
    pA->pRchild = pC;
    pB->pLchild = pB->pRchild = NULL;
    pC->pLchild = pD;
    pC->pRchild = NULL;
    pD->pLchild = NULL;
    pD->pRchild = pE;
    pE->pLchild = pE->pRchild = NULL;
    
    return pA;
}