二叉链表的结构描述，二叉树的建立，二叉树的先序中序和后序遍历算法

1. 二叉链表的结构描述

二叉链表是一种二叉树的链式存储结构，每个结点包含三个域：数据域、左子树指针域和右子树指针域。二叉链表的结构描述如下：

typedef struct BiTNode
{
    int data;               // 数据域
    struct BiTNode *lchild; // 左子树指针域
    struct BiTNode *rchild; // 右子树指针域
} BiTNode, *BiTree;

2. 二叉树的建立

二叉树可以通过递归的方式进行建立。如果当前结点的左子树或右子树为空，则创建一个新的结点，否则递归地创建左子树和右子树。建立二叉树的算法如下：

void createBiTree(BiTree *T)
{
    int data;
    scanf("%d", &data);
    if (data == 0) // 如果输入的数据为0，则表示当前结点为空
    {
        *T = NULL;
    }
    else
    {
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = data;
        createBiTree(&(*T)->lchild); // 递归建立左子树
        createBiTree(&(*T)->rchild); // 递归建立右子树
    }
}

3. 二叉树的先序中序和后序遍历算法

先序遍历的算法是先访问当前结点，然后递归遍历左子树和右子树；中序遍历的算法是先递归遍历左子树，然后访问当前结点，最后递归遍历右子树；后序遍历的算法是先递归遍历左子树和右子树，然后访问当前结点。二叉树的先序中序和后序遍历算法如下：

// 先序遍历
void preOrderTraverse(BiTree T)
{
    if (T != NULL)
    {
        printf("%d ", T->data); // 访问当前结点
        preOrderTraverse(T->lchild); // 递归遍历左子树
        preOrderTraverse(T->rchild); // 递归遍历右子树
    }
}

// 中序遍历
void inOrderTraverse(BiTree T)
{
    if (T != NULL)
    {
        inOrderTraverse(T->lchild); // 递归遍历左子树
        printf("%d ", T->data); // 访问当前结点
        inOrderTraverse(T->rchild); // 递归遍历右子树
    }
}

// 后序遍历
void postOrderTraverse(BiTree T)
{
    if (T != NULL)
    {
        postOrderTraverse(T->lchild); // 递归遍历左子树
        postOrderTraverse(T->rchild); // 递归遍历右子树
        printf("%d ", T->data); // 访问当前结点
    }
}