静态 链式二叉树

此为静态的链式二叉树。

/**
 *       A
 *   B       C
 *        D
 *            E
 **/
# include <stdio.h>
# include <malloc.h>

typedef struct BTNode
{
    char data; // 数据域
    struct BTNode* pLchild; // 左子树指针域 p是指针 L是左孩子 R是右孩子
    struct BTNode* pRchild; // 右子树指针域
}BTNODE, *PBTNODE;

PBTNODE CreateBTree(void); // 创建二叉树，并返回二叉树根节点地址
void PreTraverseBTree(struct BTNode * pT);   //先序遍历二叉树
void InTraverseBTree(struct BTNode * pT);    //中序遍历二叉树
void PostTraverseBTree(struct BTNode * pT);  //后续遍历二叉树

int main(void)
{
    PBTNODE pT = CreateBTree();
    
    printf("先序遍历二叉树：\n");
    PreTraverseBTree(pT);
    
    printf("中序遍历二叉树：\n");
    InTraverseBTree(pT);
    
    printf("后序遍历二叉树：\n");
    PostTraverseBTree(pT);
    
    return 0;
}

PBTNODE CreateBTree(void)
{
    // 创建5个节点
    PBTNODE pA = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pB = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pC = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pD = (PBTNODE)malloc(sizeof(BTNODE));
    PBTNODE pE = (PBTNODE)malloc(sizeof(BTNODE));
    
    // 给5个节点分配数据
    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; // 返回二叉树根节点地址
}

void PreTraverseBTree(struct BTNode * pT) // 先序遍历二叉树
{
    // pT->pLchild可以代表整个左子树
    // pT->pRchild可以代表整个右子树
    
    if( NULL != pT ) // 根节点地址不为空时才创建二叉树
    {
        printf("%c\n", pT->data);         // 先序遍历根节点
        
        if( NULL != pT->pLchild )// 根节点左子树不为空时才遍历
        {
            PreTraverseBTree(pT->pLchild); // 先序遍历左子树
        }
        
        if( NULL != pT->pRchild )// 根节点右子树不为空时才遍历
        {
            PreTraverseBTree(pT->pRchild);  // 先序遍历右子树
        }
    }
}

void InTraverseBTree(struct BTNode * pT) // 中序遍历
{
    if( NULL != pT )
    {
        if( NULL != pT->pLchild )
        {
            InTraverseBTree(pT->pLchild); // 中序遍历左子树
        }
        
        printf("%c\n", pT->data);         // 中序遍历根节点
        
        if( NULL != pT->pRchild )
        {
            InTraverseBTree(pT->pRchild); // 中序遍历右子树
        }
    }
}

void PostTraverseBTree(struct BTNode * pT) // 后序遍历
{
    if( NULL != pT )
    { 
        if( NULL != pT->pLchild )
        {
            PostTraverseBTree(pT->pLchild);  // 后序遍历左子树
        }
        
        if( NULL != pT->pRchild )
        {
            PostTraverseBTree(pT->pRchild);  // 后序遍历右子树
        }
        
        printf("%c\n", pT->data);            // 后序遍历根节点
    }
}