二叉树的基本操作与实现：C语言深度剖析

代码整体框架

1. #define _CRT_SECURE_NO_WARNINGS

2. 头文件引入

3. typedef int BTtype;

4. 二叉树节点结构体定义

二叉树的创建

1. BuyNode 函数

2. CreatNode 函数

二叉树的遍历

前序遍历

中序遍历

后序遍历

二叉树属性的计算

节点个数

1. 原静态变量 count 方式

2. 指针传递 count 方式

3. 优化后的递归方式

树的高度

1. 原高时间复杂度写法

2. 优化后写法

第K层节点个数

主函数与测试

在数据结构的领域中，二叉树是一种极为重要且基础的数据结构，它在许多算法和实际应用中都扮演着关键角色。本文将通过一段C语言代码，深入探讨二叉树的创建、遍历以及一些基本属性的计算。

作者主页：共享家9527-CSDN博客

代码整体框架


c#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int BTtype;typedef struct BTtree
{BTtype date;struct BTtree* left;struct BTtree* right;}BTNode;

1. #define _CRT_SECURE_NO_WARNINGS

- 原理：在使用Visual Studio等编译器时，为了增强代码安全性，一些传统的C函数（如 scanf 、 strcpy 等）会被视为不安全，并给出警告。这个宏定义的作用就是忽略这些关于函数安全性的警告。

- 作用：让开发者在使用这些传统函数时，代码编译过程更加简洁，避免大量警告信息干扰开发流程。

- 要点：虽然它方便了开发，但从安全角度考虑，在实际生产环境中，应尽量使用更安全的函数替代，如 scanf_s 、 strcpy_s 等。

2. 头文件引入

- stdio.h ：提供标准输入输出函数，如 printf 用于输出信息， scanf 用于获取用户输入等。

- assert.h ：包含断言机制， assert 宏用于在程序中插入调试断言。当断言条件为假时，程序会终止并给出错误信息，有助于在开发过程中快速定位逻辑错误。

- stdlib.h ：包含一些标准的库函数，如动态内存分配函数 malloc 、 free ，以及数值转换函数等。在这里主要用于 malloc 为二叉树节点分配内存。

3. typedef int BTtype;

- 原理：使用 typedef 关键字为 int 类型定义一个别名 BTtype 。这样在后续代码中， BTtype 就等同于 int 。

- 作用：提高代码的可维护性和可读性。如果后续需要更改二叉树节点数据类型，只需要在这一处修改 typedef 定义即可，而不需要在整个代码中逐一修改 int 。

- 要点：使用别名时要确保其含义清晰，避免造成混淆。

4. 二叉树节点结构体定义

- 原理：定义了一个名为 BTNode 的结构体，包含一个数据成员 date 用于存储节点的数据，以及两个指针成员 left 和 right ，分别指向左子节点和右子节点。通过这种链式结构，构建出二叉树的层级关系。

- 作用：它是构建二叉树的基本单元，通过节点之间的指针连接，实现二叉树的各种操作，如遍历、插入、删除等。

- 要点：在操作节点时，要时刻注意指针的有效性，避免空指针引用等错误。

二叉树的创建


c// 申请一个新节点
BTNode* BuyNode(BTtype x)
{// 分配一个BTNode大小的内存块BTNode* node = (BTNode*)malloc(sizeof(BTNode));// 检查内存分配是否成功if (node == NULL){// 如果分配失败，打印错误信息perror("malloc fail");return;}// 初始化节点的数据为传入的值xnode->date = x;// 初始化左子节点指针为NULLnode->left = NULL;// 初始化右子节点指针为NULLnode->right = NULL;// 返回新创建的节点return node;
}// 创建一棵特定结构的二叉树
BTNode* CreatNode()
{// 创建节点1BTNode* node1 = BuyNode(1);// 创建节点2BTNode* node2 = BuyNode(2);// 创建节点3BTNode* node3 = BuyNode(3);// 创建节点4BTNode* node4 = BuyNode(4);// 创建节点5BTNode* node5 = BuyNode(5);// 创建节点6BTNode* node6 = BuyNode(6);// 设置节点1的左子节点为node2node1->left = node2;// 设置节点1的右子节点为node4node1->right = node4;// 设置节点2的左子节点为node3node2->left = node3;// 设置节点4的左子节点为node5node4->left = node5;// 设置节点5的右子节点为node6node5->right = node6;// 返回根节点return node1;
}

1. BuyNode 函数

- 原理：通过 malloc 函数从堆内存中分配一块大小为 sizeof(BTNode) 的内存空间，用于创建一个新的二叉树节点。分配成功后，对节点的数据成员和指针成员进行初始化，最后返回指向新节点的指针。

- 作用：为构建二叉树提供新的节点，是创建二叉树的基础操作。

- 要点：使用 malloc 后必须检查返回值是否为 NULL ，防止内存分配失败导致程序后续出现空指针错误。同时，当不再使用该节点时，要记得使用 free 释放内存，避免内存泄漏。

2. CreatNode 函数

- 原理：多次调用 BuyNode 函数创建多个节点，并通过手动设置每个节点的 left 和 right 指针，建立起节点之间的父子关系，从而构建出一棵具有特定结构的二叉树。

- 作用：快速构建一个用于测试和演示二叉树操作的示例树，方便后续对二叉树的遍历、属性计算等操作进行验证。

- 要点：构建过程中要确保节点之间的连接关系正确，否则会导致二叉树结构错误，影响后续操作的正确性。

二叉树的遍历

前序遍历

c// 前序遍历二叉树
void Preorder(BTNode* root)
{// 如果根节点为空，打印NULL并返回if (root == NULL){printf("NULL ");return;}// 先打印根节点的数据printf("%d ", root->date);// 递归前序遍历左子树Preorder(root->left);// 递归前序遍历右子树Preorder(root->right);
}

1. 原理：前序遍历按照“根 - 左 - 右”的顺序访问二叉树的节点。首先访问根节点，然后递归地对左子树进行前序遍历，最后递归地对右子树进行前序遍历。当遇到空节点（ root == NULL ）时，打印 NULL 并返回，以标记空节点位置，这有助于在输出中完整展示二叉树的结构。

2. 作用：常用于需要先处理根节点信息，再处理子树信息的场景。例如，在复制二叉树时，可以先复制根节点，再递归复制左右子树。

3. 要点：递归调用是实现前序遍历的关键，要确保递归的终止条件（即 root == NULL ）正确，否则会导致栈溢出等错误。同时，由于是递归操作，要注意函数调用栈的深度限制。

中序遍历

c// 中序遍历二叉树
void Inorder(BTNode* root)
{// 如果根节点为空，打印NULL并返回if (root == NULL){printf("NULL ");return;}// 递归中序遍历左子树Inorder(root->left);// 打印根节点的数据printf("%d ", root->date);// 递归中序遍历右子树Inorder(root->right);
}

1. 原理：中序遍历按照“左 - 根 - 右”的顺序访问二叉树节点。先递归地对左子树进行中序遍历，然后访问根节点，最后递归地对右子树进行中序遍历。对于二叉搜索树，中序遍历会按照从小到大的顺序输出节点的值，这是由二叉搜索树的特性决定的（左子树节点值小于根节点值，右子树节点值大于根节点值）。

2. 作用：在二叉搜索树中，中序遍历可以用于按顺序获取树中的所有元素，常用于数据排序展示或查找特定元素的场景。

3. 要点：同样要注意递归的终止条件。在处理二叉搜索树时，利用中序遍历的有序性可以优化一些查找和比较操作，但对于普通二叉树，中序遍历的顺序并无特定规律。

后序遍历


c// 后序遍历二叉树
void Postorder(BTNode* root)
{// 如果根节点为空，打印NULL并返回if (root == NULL){printf("NULL ");return;}// 递归后序遍历左子树Postorder(root->left);// 递归后序遍历右子树Postorder(root->right);// 打印根节点的数据printf("%d ", root->date);
}

1. 原理：后序遍历按照“左 - 右 - 根”的顺序访问二叉树节点。先递归地对左子树进行后序遍历，然后递归地对右子树进行后序遍历，最后访问根节点。这种遍历方式在一些需要先处理完子树所有节点，再处理根节点的场景中非常有用，比如计算树的高度、释放树的内存等。

2. 作用：在计算二叉树的一些属性（如节点个数、高度）时，后序遍历可以确保先获取子树的相关信息，再根据子树信息计算根节点的属性。在释放二叉树内存时，后序遍历可以先释放子树节点内存，最后释放根节点内存，避免内存泄漏和悬空指针问题。

3. 要点：递归实现时注意终止条件和函数调用栈深度。在进行内存释放等操作时，要确保所有节点都能被正确释放，避免内存管理错误。

二叉树属性的计算

节点个数

 
c// 计算二叉树的节点个数
// 原先是用静态变量count来计数，但是有局限性，比如多次调用会累计计数，与实际不符
// 改进版本是通过指针传递count，虽然解决了累计计数问题，但代码稍显繁琐
// 最终优化为以下递归方式，简洁且高效
int testsize(BTNode* root)
{// 如果根节点为空，返回0，否则递归计算左右子树节点个数并加上根节点本身return root == NULL? 0 : testsize(root->left) + testsize(root->right) + 1;
}

1. 原静态变量 count 方式

- 原理：使用静态变量 count ，在递归遍历二叉树的过程中，每访问一个节点就将 count 加1。由于静态变量的生命周期是整个程序运行期间，且只初始化一次，所以在多次调用计算节点个数的函数时， count 会累计计数，而不是针对每次传入的二叉树独立计算。

- 局限性：无法准确计算每次传入的二叉树的节点个数，特别是在多次调用该函数计算不同二叉树节点个数时，结果会出错。

2. 指针传递 count 方式

- 原理：通过传入一个指向 count 变量的指针，在递归遍历过程中，每次访问节点时，通过指针修改 count 的值（ ++(*count) ）。这样在不同的函数调用中，可以使用不同的 count 变量，解决了静态变量累计计数的问题。

- 缺点：代码实现相对繁琐，需要额外处理指针的传递和操作，增加了代码的复杂性和出错的可能性。

3. 优化后的递归方式

- 原理：利用递归的思想，对于空树（ root == NULL ），节点个数为0；对于非空树，节点个数等于左子树节点个数加上右子树节点个数再加上根节点本身（即1）。通过递归调用自身，不断分解问题，直到处理到空树，从而得到整棵树的节点个数。

- 优点：代码简洁明了，逻辑清晰，避免了静态变量的局限性和指针传递的复杂性，是一种高效且优雅的实现方式。

树的高度


c// 计算二叉树的高度
// 之前的写法虽然逻辑正确，但是时间复杂度为N^2，因为每次比较大小都要重新计算子树高度
// 优化后的代码先计算左右子树高度，再比较，时间复杂度降为N
int treehigh(BTNode* root)
{// 如果根节点为空，返回0if (root == NULL)return 0;// 计算左子树高度int left = treehigh(root->left);// 计算右子树高度int right = treehigh(root->right);// 返回左右子树中较大高度加1（加上根节点这一层）return left > right? left + 1 : right + 1;
}

1. 原高时间复杂度写法

- 原理：每次计算树的高度时，先分别递归计算左子树和右子树的高度，然后比较两者大小，取较大值加1作为树的高度。然而，在比较大小时，每次都要重新递归计算左子树和右子树的高度，导致大量重复计算。

- 时间复杂度分析：由于每次比较都要重新计算子树高度，对于有 N 个节点的二叉树，计算高度的时间复杂度为 O(N^2) ，效率较低。

2. 优化后写法

- 原理：先分别计算左子树和右子树的高度，并将结果存储在 left 和 right 变量中。然后比较这两个变量的值，取较大值加1作为树的高度。这样每个子树的高度只计算一次，避免了重复计算。

- 时间复杂度分析：对于每个节点，只需要计算一次其左右子树的高度，所以时间复杂度为 O(N) ，其中 N 是二叉树的节点个数，大大提高了计算效率。

第K层节点个数


c// 计算二叉树第k层的节点个数
int treeKlevel(BTNode* root, int k)
{// 如果根节点为空，返回0if (root == NULL)return 0;//如果k等于1，说明当前节点就是第k层，返回1if (k == 1)return 1;// 递归计算左子树中第k - 1层的节点个数int leftk = treeKlevel(root->left, k - 1);// 递归计算右子树中第k - 1层的节点个数int rightk = treeKlevel(root->right, k - 1);//返回左右子树中第k - 1层节点个数之和return leftk + rightk;
}

1. 原理：采用递归的方法计算第 k 层节点个数。如果根节点为空，说明树为空，第 k 层节点个数为0。当 k 等于1时，当前节点就是第 k 层，返回1。对于 k > 1 的情况，通过递归分别计算左子树和右子树中第 k - 1 层的节点个数，然后将这两个结果相加，得到整棵树第 k 层的节点个数。

2. 作用：用于获取二叉树中特定层的节点数量，在一些需要按层处理二叉树数据的算法中非常有用，比如层序遍历的优化、按层统计节点信息等。

3. 要点：递归的终止条件很关键， root == NULL 和 k == 1 这两个条件确保了递归能够正确结束，避免无限递归。同时，要理解递归过程中 k 值的变化，以及如何通过子树的第 k - 1 层节点个数推导出整棵树第 k 层的节点个数。

主函数与测试


cint main()
{// 创建二叉树BTNode* root = CreatNode();// 前序遍历并输出Preorder(root);printf("\n");// 中序遍历并输出Inorder(root);printf("\n");// 后序遍历并输出Postorder(root);printf("\n");// 计算并输出二叉树的节点个数printf("Size：%d", testsize(root));printf("\n");// 计算并输出二叉树的高度，这里减1是因为代码中高度计算包含根节点，而实际概念中根节点算第1层printf("High：%d", treehigh(root) - 1);return 0;
}

1. 创建二叉树：调用 CreatNode 函数创建一棵特定结构的二叉树，并将返回的根节点指针存储在 root 变量中。这是后续对二叉树进行各种操作的基础。

2. 遍历操作：分别调用 Preorder 、 Inorder 和 Postorder 函数对二叉树进行前序、中序和后序遍历，并将遍历结果输出到控制台后，这一系列操作的意义和作用十分关键。通过输出遍历结果，开发者能够直观地验证二叉树的结构是否符合预期，以及遍历函数的实现是否正确。

- 前序遍历结果分析：前序遍历按照“根 - 左 - 右”的顺序访问节点。输出的结果顺序能够反映出二叉树从根节点开始，逐层向左子树和右子树扩展的访问路径。如果二叉树的构建正确，前序遍历结果中，根节点总是第一个被输出，然后是左子树的节点，按照相同的前序规则依次输出，最后是右子树的节点。通过观察前序遍历结果，我们可以检查节点之间的父子关系是否正确建立，以及整个遍历过程是否符合前序遍历的逻辑。

- 中序遍历结果分析：对于普通二叉树，中序遍历结果呈现出一种从左到右逐步深入的节点访问顺序。而对于二叉搜索树，中序遍历的结果应该是一个有序序列。在这个测试中，通过输出中序遍历结果，我们可以验证二叉树是否满足二叉搜索树的特性（如果它本应是一棵二叉搜索树的话）。即使不是二叉搜索树，中序遍历结果也能帮助我们了解节点在左子树和右子树之间的分布情况，以及整个树的中序遍历逻辑是否正确实现。

- 后序遍历结果分析：后序遍历按照“左 - 右 - 根”的顺序访问节点。输出的后序遍历结果中，根节点总是最后一个被输出，这符合后序遍历先处理子树再处理根节点的特性。通过分析后序遍历结果，我们可以检查在处理复杂的二叉树结构时，是否能够正确地先完成子树的遍历，再处理根节点，确保整个遍历过程的正确性和完整性。

3. 计算并输出二叉树的节点个数：调用 testsize 函数计算二叉树的节点个数，这个函数采用递归方式，简洁高效地完成了计算任务。然后通过 printf 函数将节点个数输出，格式化为“Size：[节点个数]”，方便直观地查看结果。

4. 计算并输出二叉树的高度：调用 treehigh 函数计算二叉树的高度，在代码实现中，树的高度计算是从0开始计数（根节点高度计为0，根节点的子节点高度计为1，以此类推），但在通常的二叉树高度概念中，根节点所在层算第1层，所以需要将 treehigh 函数返回的值减1后再输出。通过 printf 函数将高度值输出，格式化为“High：[高度值]”。

5. 返回值： main 函数返回0，表示程序正常结束。在C语言中， main 函数的返回值用于向操作系统传递程序的结束状态，0通常表示程序执行过程中没有出现错误。

通过 main 函数中的这些操作，可以对之前定义的二叉树创建、遍历以及属性计算等功能进行全面的测试和验证，确保代码的正确性和可靠性。