数据结构实战：如何用C语言实现凹入表打印二叉树（附完整代码解析）

很多C语言学习者在掌握了链表、栈、队列这些线性结构后，第一次面对二叉树时，总会感觉有些“抽象”。我们能在脑子里想象出它的树形分叉，但如何让计算机在屏幕上直观地展示这种层次关系，却成了一个小挑战。尤其是当你调试一个复杂的二叉树算法，想看看自己构建的树到底长什么样时，如果只有一串遍历输出，那简直像在摸黑走路。凹入表打印，就是一种能把二叉树“立”在终端里的可视化技巧，它用缩进来表示节点间的父子层级，让整个结构一目了然。今天，我们就抛开理论课本，直接从代码层面切入，手把手带你实现一个功能完整的凹入表打印程序。这篇文章适合那些已经写过链表、对指针不再陌生，并渴望通过实战来深化对树形结构理解的开发者。我们会从最基础的节点定义开始，一步步走到递归构建、深度计算，最终实现那个能让你清晰“看见”二叉树的打印函数，过程中每一个容易踩坑的细节，都会掰开揉碎了讲清楚。

1. 理解核心：二叉树与凹入表打印的本质

在动手写代码之前，我们必须先搞清楚两件事：计算机内存中的二叉树是如何组织的，以及凹入表这种打印形式到底想表达什么。这能帮你从根源上理解后续的每一个设计决策。

二叉树在C语言中的物理形态，本质上就是一个由结构体节点通过指针链接而成的网络。每个节点是一个独立的内存块，里面存储着数据（比如一个字符或整数），以及两个至关重要的指针：一个指向左孩子节点，另一个指向右孩子节点。如果某个孩子不存在，对应的指针就是 NULL。这种结构决定了二叉树的访问路径是单向的——从根节点出发，可以顺着指针找到子孙，但无法从子节点直接回溯到父节点（除非额外存储父指针）。因此，我们后续所有的操作，无论是创建、遍历还是打印，都严重依赖于递归或栈这种能够“记住来路”的机制。

那么，凹入表打印的目标，就是把上述这种内存中的指针网络，转化为人眼易于理解的二维层次化文本图形。它的核心规则非常简单：

• 层次即缩进：节点在树中的深度（第几层）决定了它在打印输出中前面有多少个制表符或空格。
• 视觉上的“右-根-左”：为了在控制台从上到下阅读时，形成一种类似树根在左、枝叶向右展开的视觉效果，打印顺序通常采用一种特殊的遍历：先递归打印右子树，然后打印当前节点，最后递归打印左子树。这样，右子树（在视觉上更“高”或更“上”）会先被打印，当前根节点居中，左子树在后。

我们可以用一个极简单的例子来建立直觉。假设有一颗二叉树：

    A
   / \
  B   C

如果采用先右后左的凹入表打印，输出可能会是这样：

    C
A
    B

这里，根节点A位于中间层，它的右孩子C因为先被打印且带有缩进，出现在上方；左孩子B后被打印，同样带有缩进，出现在下方。整个结构虽然旋转了90度，但层级关系清晰可见。

提示：凹入表打印有多种变体，有的让根节点在最左侧，枝叶向右延伸。本文实现的风格是“根在中间，右上左下”，这在展示不平衡的树时尤为直观。

理解了这些，我们就知道代码需要完成几个关键任务：

1. 定义节点结构，用于在内存中承载数据与关系。
2. 实现树的构建函数，将用户的输入序列转化为内存中的树。
3. 实现计算树深度的函数，这对理解递归和后续调试有帮助。
4. 最终实现打印函数，它需要知道当前节点的深度，以决定缩进量，并按照正确的顺序递归调用自身。

2. 从零构建：定义数据结构与创建二叉树

现在，让我们进入实战环节，打开编辑器，开始编写代码。第一个步骤，就是为二叉树打造它的“基本单元”。

2.1 定义二叉链表节点结构

在C语言中，我们使用结构体来定义节点。这里我们选择存储字符型数据，使其足够简单以聚焦于结构本身。

#include <stdio.h>
#include <stdlib.h>

typedef char TElemType; // 将二叉树元素类型定义为字符，便于输入测试

// 定义二叉树的节点结构
typedef struct BiTNode {
    TElemType data;               // 节点存储的数据
    struct BiTNode *lchild;       // 指向左子树的指针
    struct BiTNode *rchild;       // 指向右子树的指针
} BiTNode, *BiTree;               // BiTNode是结构体类型，BiTree是指向该结构体的指针类型

这段代码做了两件关键事：一是定义了存储数据的 data 字段和两个指针字段；二是通过 typedef 创建了 BiTree 这个类型别名，它代表“指向二叉树节点的指针”。在后续函数中，使用 BiTree T 就声明了一个可以指向树根（或任何节点）的指针，这比每次都写 struct BiTNode* 要简洁得多。

2.2 通过先序序列递归创建二叉树

有了结构，接下来就要“无中生有”，把用户输入的一串字符变成一棵树。我们采用先序递归的方式构建，这是最符合人类输入习惯的方式之一。函数需要接收一个指向指针的指针（BiTree *T），因为我们需要修改调用者传入的根指针本身。

void CreateBiTree(BiTree *T) {
    char ch;
    // 注意：这里使用scanf按字符读取，输入时通常需要一次性连续输入
    scanf("%c", &ch);

    // 递归终止条件：我们约定输入空格' '代表空节点
    if (ch == ' ') {
        *T = NULL;
    } else {
        // 分配一个新节点
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (*T == NULL) {
            printf("内存分配失败！\n");
            exit(1); // 分配失败则退出程序
        }
        // 设置节点数据
        (*T)->data = ch;
        // 递归创建左子树和右子树
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

这个函数的逻辑是经典的“根-左-右”先序递归：

1. 读入一个字符。
2. 如果是终止符（这里用空格），则将当前指针设为 NULL，表示这是一棵空树。
3. 否则，为新节点申请内存，存入数据。
4. 然后，立刻递归调用自身去构建这个新节点的左子树，完成后，再递归调用自身去构建右子树。

这里有一个极其重要的细节：输入序列必须能唯一确定一棵二叉树。对于先序构建，我们需要用特殊字符（如原示例中的#或这里的空格）明确标出所有空孩子的位置。例如，要构建一个只有根节点A的树，输入必须是A （A后面跟两个空格，分别表示左、右空孩子）。如果输入不完整，递归就会因为等待更多输入而“卡住”，或者错误地解析结构。

注意：在实际调试时，你可能会发现 scanf 连续读字符会读取到之前输入留下的回车符。一个更健壮的方案是使用 getchar() 并在循环中过滤掉空白符，或者改用字符串输入再解析。为了示例清晰，我们暂用 scanf，但你在自己的项目中需要处理这个边界情况。

为了更直观地理解不同输入对应的树形，可以参考下表：

输入序列 (先序，空格表空)	对应的二叉树结构	说明
A	A (仅有根节点)	A后接两个空格，表示左右孩子皆空
A B C	A 的左孩子为 B，右孩子为 C	每个非空节点后都必须跟其左右子树的定义
A B D E C	结构稍复杂的树	需要仔细对照先序顺序：根A，左子树根B，B的左D...

3. 深度计算与遍历：理解树的度量与访问

在实现打印之前，我们先完成两个辅助功能：计算树的深度和进行遍历。这不仅能验证树的构建是否正确，其递归思想也是打印功能的核心。

3.1 递归计算二叉树的深度

树的深度（高度）定义为从根节点到最远叶子节点的最长路径上的节点数。计算它的递归定义非常优美：

• 如果树为空，深度为0。
• 否则，深度 = 1 + max(左子树深度, 右子树深度)。

int BiTreeDepth(BiTree T) {
    int left_depth, right_depth;
    if (T == NULL) {
        return 0; // 空树深度为0
    } else {
        left_depth = BiTreeDepth(T->lchild);  // 计算左子树深度
        right_depth = BiTreeDepth(T->rchild); // 计算右子树深度
        // 当前树的深度是左右子树深度的较大值加1
        return (left_depth > right_depth ? left_depth : right_depth) + 1;
    }
}

这个函数是理解递归的绝佳例子。它从根节点开始，问左子树“你有多深？”，再问右子树“你有多深？”，然后取两者的最大值，加上自己这一层（+1），就是总深度。这个过程会一直递归到叶子节点（其左右子树深度均为0），然后结果像涟漪一样回溯回来。

3.2 实现一种遍历：RDL（右-根-左）

为了后续打印做准备，也为了检查树的结构，我们实现一种不常用的遍历顺序：RDL（访问右子树、访问根节点、访问左子树）。这在凹入表打印中会用到。

void RDLTraverse(BiTree T) {
    if (T) { // 如果当前节点不为空
        RDLTraverse(T->rchild); // 先遍历右子树
        printf("%c ", T->data);  // 然后访问根节点数据
        RDLTraverse(T->lchild); // 最后遍历左子树
    }
}

在 main 函数中调用这个函数，你可以看到节点以“右-根-左”的顺序被打印出来。这本身并不是常规的遍历需求，但它输出的顺序，恰好与我们即将实现的凹入表打印中，节点纵向出现的顺序是一致的。

4. 核心实现：凹入表打印算法详解

终于来到最核心的部分。凹入表打印函数 print 需要两个参数：当前要打印的子树的根 T，以及这个根节点所在的深度 n（根节点的深度通常从0开始）。深度值直接决定了打印时的缩进量。

4.1 打印函数的代码实现

void print(BiTree T, int depth) {
    int i;
    if (T != NULL) { // 只处理非空节点
        // 1. 递归打印右子树，深度加1
        print(T->rchild, depth + 1);

        // 2. 打印当前节点：先缩进，再打印数据
        for (i = 0; i < depth; i++) {
            printf("    "); // 使用4个空格作为一个缩进单位，比制表符更可控
        }
        printf("%c\n", T->data); // 打印节点数据并换行

        // 3. 递归打印左子树，深度同样加1
        print(T->lchild, depth + 1);
    }
    // 如果T为空，函数直接返回，不产生任何输出，这对应着树上“空缺”的位置
}

让我们拆解这个函数的执行过程，假设我们要打印一棵简单的树，其先序输入为 A B C （即A是根，B是左孩子，C是右孩子）。

1. 首次调用 print(T, 0)，T 指向 A，depth=0。
2. 进入函数，T 非空，执行 print(T->rchild, 1) 去打印 A 的右子树（即以 C 为根的树）。
3. 在打印 C 的函数调用中，depth=1。它又先递归调用自己的右孩子（NULL），直接返回。然后执行缩进：循环1次，打印4个空格，接着打印字符 C 并换行。最后递归调用自己的左孩子（NULL）并返回。
4. 控制权回到 A 的打印函数中。此时右子树已打完，接下来为 A 自身执行缩进：depth=0，循环0次，不缩进，直接打印 A 并换行。
5. 最后，A 调用 print(T->lchild, 1) 去打印左子树 B。过程与打印 C 类似，B 前会有4个空格的缩进。 最终输出为：

    C
A
    B

看，一棵旋转了90度的树跃然屏上。右孩子 C 在上方（缩进多），根 A 在中间，左孩子 B 在下方（缩进多）。

4.2 关键逻辑与常见陷阱分析

这个看似简单的函数里，藏着几个容易出错的点：

• 递归顺序是灵魂：必须是右子树 -> 根 -> 左子树。任何顺序的改变都会导致打印出的层级关系错乱。你可以尝试改成“左-根-右”看看输出会变成什么样，这能帮助你加深理解。
• 深度参数的传递：每次递归调用时，传入的深度是 depth + 1。这保证了子节点比父节点多一层缩进。千万不能写成 depth++ 或 ++depth，这会改变当前函数栈帧中的 depth 值，导致后续逻辑错误。
• 空节点的处理：函数开头判断 if (T != NULL) 是递归的终止条件之一。对于空节点，函数什么都不做，直接返回。这意味着凹入表打印不会为缺失的节点占位，这符合大多数情况下的视觉需求。如果你需要为完全二叉树保留结构，可能需要不同的处理。
• 缩进字符的选择：示例中使用4个空格 (" ")。相比制表符 \t，空格的显示在不同环境下更一致。你可以根据需要调整缩进单位的宽度。

5. 整合测试：完整程序与调试技巧

现在，我们将所有模块组装起来，形成一个可以运行和测试的完整程序。

5.1 完整的C语言程序代码

#include <stdio.h>
#include <stdlib.h>

typedef char TElemType;

typedef struct BiTNode {
    TElemType data;
    struct BiTNode *lchild, *rchild;
} BiTNode, *BiTree;

void CreateBiTree(BiTree *T) {
    char ch;
    scanf("%c", &ch);
    if (ch == ' ') {
        *T = NULL;
    } else {
        *T = (BiTree)malloc(sizeof(BiTNode));
        if (!(*T)) exit(1);
        (*T)->data = ch;
        CreateBiTree(&(*T)->lchild);
        CreateBiTree(&(*T)->rchild);
    }
}

int BiTreeDepth(BiTree T) {
    int left, right;
    if (!T) return 0;
    left = BiTreeDepth(T->lchild);
    right = BiTreeDepth(T->rchild);
    return (left > right ? left : right) + 1;
}

void RDLTraverse(BiTree T) {
    if (T) {
        RDLTraverse(T->rchild);
        printf("%c ", T->data);
        RDLTraverse(T->lchild);
    }
}

void print(BiTree T, int depth) {
    int i;
    if (T) {
        print(T->rchild, depth + 1);
        for (i = 0; i < depth; i++) printf("    ");
        printf("%c\n", T->data);
        print(T->lchild, depth + 1);
    }
}

int main() {
    BiTree T = NULL;
    printf("请按先序输入二叉树（用空格表示空节点，如：A B  C  ）: \n");
    CreateBiTree(&T);

    printf("\nRDL遍历结果: ");
    RDLTraverse(T);
    printf("\n");

    printf("树的深度: %d\n", BiTreeDepth(T));
    printf("\n凹入表形式打印二叉树:\n");
    print(T, 0);
    printf("\n");

    // 注意：实际项目中应编写DestroyBiTree函数来释放内存，此处从简
    return 0;
}

5.2 编译、运行与测试用例

将上述代码保存为 binary_tree_print.c。在Linux或macOS终端，或者Windows的MinGW、Cygwin环境下，使用gcc编译：

gcc -o tree_print binary_tree_print.c

然后运行程序：

./tree_print

程序会提示你输入。输入时需要一次性输入完整的先序序列，中间不要有回车，直到序列结束。例如，对于之前提到的树（A为根，B为左孩子，C为右孩子），你应该输入：A B C （字母和空格），然后按回车。

下面提供几个测试用例，你可以对比输出，检查程序是否正确：

测试目的	输入序列 (先序)	预期凹入表打印输出 (大致形态)	验证点
单节点树	A	A	无缩进，只有根节点
完全二叉树	A B D E C F G	一个对称的、有四层的树状结构	观察左右子树的对称缩进
左斜树	A B C D	所有节点向右下角倾斜成一列	每个新节点都比前一个多一层缩进
右斜树	A B C D	所有节点向右上角倾斜成一列	每个新节点都比前一个多一层缩进

5.3 调试与问题排查

如果你得到的输出不符合预期，可以按以下步骤排查：

1. 检查输入：确认是否严格按照先序、并用空格填充了所有空位。这是最常见的问题源。一个技巧是，叶子节点后面必须跟两个空格（分别代表其左右空孩子）。
2. 验证树结构：在 main 函数中，在调用 print 之前，先调用 RDLTraverse 并观察输出顺序。结合先序输入，手动画出这棵树，看遍历顺序是否合理。
3. 跟踪递归：在 print 函数开头添加调试语句，例如 printf("当前节点: %c (深度: %d)\n", T?T->data:'#', depth);。这会让你清晰地看到递归的调用路径和深度值的变化。
4. 内存与指针：确保在输入时空格确实被正确读作空节点。如果程序在创建树时崩溃，检查 malloc 的返回值，并确认指针操作（如 (*T)->data）只在 T 非空时进行。

凹入表打印实现后，它就成了你调试二叉树相关算法的一个强大可视化工具。无论是检查插入、删除操作的结果，还是观察平衡二叉树（如AVL树）的旋转效果，都能让你从抽象的指针操作中跳出来，获得最直观的反馈。我最初在实现红黑树时，就是靠一个类似的打印函数，才把那些复杂的旋转规则真正理清，每次操作后打印一下，哪里错了就一目了然。