【初探数据结构】二叉树的链式结构——分治的暴力美学

二叉树是数据结构中的重要概念，广泛应用于算法和程序设计中。本文将基于C语言实现二叉树的核心操作，并通过代码解析帮助读者理解其原理。

1. 二叉树节点定义

typedef struct BinaryTreeNode {
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
} BTNode;

• 使用左右指针实现树形结构
• data字段存储节点值（示例中为char类型）

2.遍历算法

2.1 前序遍历：根->左->右

1. 访问结点
2. 递归左子树，直至为空子树时（递归结束条件），回归
3. 递归右子树，直至为空子树时，回归 前序遍历图解：

void BinaryTreePrevOrder(BTNode* root)
{
    if (root == NULL)
        return;

    printf("%c ", root->data);//根
    BinaryTreePrevOrder(root->left);//左子树
    BinaryTreePrevOrder(root->right);//右子树
}

当我们对递归代码理解模糊时，可以画出代码的递归图，能够帮助我们很好的理清代码逻辑。 如下为前序遍历的代码递归图：

2.2 中序遍历：左->根->右

1. 递归左子树，直至为空子树时（递归结束条件），回归
2. 访问结点
3. 递归右子树，直至为空子树时，回归

void BinaryTreeInOrder(BTNode* root)
{
    if (root == NULL)
        return;
    
    BinaryTreeInOrder(root->left);//左子树
    printf("%c ", root->data);//根
    BinaryTreeInOrder(root->right);//右子树
}

2.3 后序遍历：左->右->根

1. 递归左子树，直至为空子树时（递归结束条件），回归
2. 递归右子树，直至为空子树时，回归
3. 访问结点

void BinaryTreePostOrder(BTNode* root)
{
    if (root == NULL)
        return;

    BinaryTreePostOrder(root->left);//左子树
    BinaryTreePostOrder(root->right);//右子树
    printf("%c ", root->data);//根
}

2.4 层序遍历：使用队列辅助实现

思路：创建一个队列，如果二叉树不为空，入根节点，之后遵循一个逻辑：队列每出一个结点，就将这个结点的孩子节点都入队列。 如此往复循环，直至队列为空时，遍历结束。 这里所需要用到的队列不再赘述，如有疑问，建议读者去学习我过去的文章~