数据结构课程设计二叉树的遍历c语言

### 数据结构课程设计 C语言 实现 二叉树 前序 中序 后序 层次 遍历

#### 定义二叉树结点结构体
为了实现二叉树的各种遍历方法，首先定义一个表示二叉树节点的结构体。

typedef struct TreeNode {
    char data;
    struct TreeNode *left, *right;
} TreeNode;

#### 创建新节点函数
创建一个新的二叉树节点用于构建具体的二叉树实例。

TreeNode* createNode(char value) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

#### 构建测试用例中的二叉树
基于给定的例子来建立一棵简单的二叉树以便于展示不同类型的遍历算法效果。

TreeNode* buildSampleTree() {
    /* Construct the following tree:
             H
           /   \
          B     Z
         / \     \
        D   U     A
       /
      A
    */
    
    TreeNode* root = createNode('H');
    root->left = createNode('B');
    root->right = createNode('Z');

    root->left->left = createNode('D');
    root->left->right = createNode('U');
    root->left->left->left = createNode('A');

    root->right->right = createNode('A');
    
    return root;
}

#### 前序遍历（先访问根节点）
按照访问顺序为：根 -> 左子树 -> 右子树的方式打印各节点字符[^1]。

void preorderTraversal(TreeNode* node) {
    if (!node) return;

    printf("%c ", node->data); // 访问当前节点
    preorderTraversal(node->left); // 进入左子树继续前序遍历
    preorderTraversal(node->right); // 进入右子树继续前序遍历
}

#### 中序遍历（先访问左子树再访问根最后访问右子树）
遵循左子树 -> 根 -> 右子树这样的路径依次输出各个顶点上的字母。

void inorderTraversal(TreeNode* node) {
    if (!node) return;

    inorderTraversal(node->left);
    printf("%c ", node->data);
    inorderTraversal(node->right);
}

#### 后序遍历（最后才处理根节点的信息）
采取的是先走到底部最左边的孩子开始逐级向上回溯并记录经过的所有节点直到遇到分支转向右边重复相同过程直至整棵树被完全探索完毕之后才会回到最初的起点即根的位置进行最终的操作。

void postorderTraversal(TreeNode* node) {
    if (!node) return;

    postorderTraversal(node->left);
    postorderTraversal(node->right);
    printf("%c ", node->data);
}

#### 层次遍历（广度优先搜索）
层次遍历是从上到下按层读取每一行的内容。这里采用队列辅助完成这一操作[^3]。

#include <queue>

void levelOrderTraversal(TreeNode* root){
    std::queue<TreeNode*> q;
    if(root != nullptr)
        q.push(root);

    while(!q.empty()){
        TreeNode* current = q.front();
        q.pop();

        printf("%c ",current->data);

        if(current->left!=nullptr)
            q.push(current->left);
        
        if(current->right!=nullptr)
            q.push(current->right);
    }
}

以上就是完整的C语言版本对于二叉树四种基本遍历模式的具体编码实践案例说明。