二叉树递归实现

二叉树链式结构的实现详解（C语言）

前置说明

在学习二叉树的基本操作前，需先创建一棵二叉树。为降低学习成本，我们手动快速构建一棵简单二叉树，待掌握基本操作后再深入研究真正的创建方式（如通过前序序列构建）。

节点定义

typedefintBTDataType;typedefstructBinaryTreeNode{BTDataType _data;structBinaryTreeNode*_left;structBinaryTreeNode*_right;}BTNode;

手动创建节点，用于测试代码

BTNode*BuyNode(BTDataType x){BTNode*node=(BTNode*)malloc(sizeof(BTNode));node->_data=x;node->_left=NULL;node->_right=NULL;returnnode;}BTNode*CreatBinaryTree(){BTNode*node1=BuyNode(1);BTNode*node2=BuyNode(2);BTNode*node3=BuyNode(3);BTNode*node4=BuyNode(4);BTNode*node5=BuyNode(5);BTNode*node6=BuyNode(6);node1->_left=node2;node1->_right=node4;node2->_left=node3;node4->_left=node5;node4->_right=node6;returnnode1;}

4.2 二叉树的遍历

二叉树的遍历（Traversal）是指按照某种特定的规则，依次访问二叉树中的每个节点，且每个节点仅被访问一次。遍历是二叉树上最基本也是最重要的操作之一，是实现查找、插入、删除、销毁等其他运算的基础。

由于二叉树具有递归结构（每个子树本身也是一棵二叉树），其遍历通常采用递归方式实现。根据访问根节点的时机不同，可分为以下三种经典遍历方式：

前序、中序、后序遍历（递归实现）

记忆技巧：

• “前、中、后” 指的是根节点被访问的顺序位置。
• 例如，“前序” = 根在“前”，“后序” = 根在“后”。

voidBinaryTreePrevOrder(BTNode*root)//前序遍历{if(root==NULL){printf("N ");return;}printf("%d ",root->_data);BinaryTreePrevOrder(root->_left);BinaryTreePrevOrder(root->_right);//这种方法虽然可以遍历数组，但是没有保存返回值，整个函数无返回值，在应用这种方法时，需要针对题目要求，适当使用变量保存返回值。}voidBinaryTreeInOrder(BTNode*root)//中序遍历{if(root==NULL){printf("N ");return;}BinaryTreeInOrder(root->_left);printf("%d ",root->_data);//打印根的节点就相当于访问根的实际，弹栈时会回到根。BinaryTreeInOrder(root->_right);}voidBinaryTreePostOrder(BTNode*root){if(root==NULL){printf("N ");return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);printf("%d ",root->_data);////打印根的节点就相当于访问根的实际，弹栈时会回到根。}

其实我们可以发现，三种遍历的核心代码都是

if(root==NULL){return;}BinaryTreePostOrder(root->_left);BinaryTreePostOrder(root->_right);

前序、中序、后序遍历的递归逻辑结构完全相同，都是对二叉树进行深度优先搜索（DFS）的过程。
它们的唯一区别在于：访问当前节点（即“打印”或“处理”根节点）的时机不同：

• 前序遍历：在递归左子树之前访问根；
• 中序遍历：在递归左子树之后、递归右子树之前访问根；
• 后序遍历：在递归左右子树之后访问根。

层序遍历（BFS）

层序遍历（Level Order Traversal）是指按照从上到下、从左到右的顺序逐层访问二叉树的节点。它属于广度优先搜索（BFS, Breadth-First Search）的典型应用。

由于需要按层级顺序处理节点，必须借助队列（Queue）这一数据结构来实现。

实现步骤

1. 将根节点入队；
2. 循环执行以下操作，直到队列为空：
   • 出队一个节点，并访问（如打印其值）；
   • 若该节点的左孩子非空，则将其左孩子入队；
   • 若该节点的右孩子非空，则将其右孩子入队；
3. 队列为空时，遍历结束。

核心思想：利用队列的“先进先出”（FIFO）特性，确保上一层的节点总是在下一层节点之前被处理，从而实现逐层从左到右的访问顺序。也就是在根节点出队时，将他的孩子入队，就可以保证始终按照层序遍历

voidBinaryTreeLevelOrder(BTNode*root){if(root==NULL)return;Queue p;QueueInit(&p);QueuePush(&p,root);while(!QueueEmpty(&p)){BTNode*temp=QueueFront(&p);printf("%d",temp->_data);QueuePop(&p);if(temp->_left){QueuePush(&p,temp->_left);}if(temp->_right){QueuePush(&p,temp->_right);}}Destroy(&p);}

判断完全二叉树

完全二叉树的定义

一棵深度为k kk的二叉树，若其前k − 1 k-1k−1层是满的，且第k kk层的节点都连续集中在最左边，则称该二叉树为完全二叉树。

通俗理解：

• 所有层都填满，除了最后一层；
• 最后一层的节点必须从左到右连续排列，中间不能有空缺；
• 一旦出现空节点（NULL），其后不能再有任何非空节点。

层序遍历 + NULL 标记

利用队列进行层序遍历，并将空指针（NULL）也入队。关键逻辑如下：

1. 从根开始，将节点（包括NULL）按层序入队；
2. 遍历过程中：
   • 一旦遇到NULL节点，标记“已出现空洞”；
   • 此后若再遇到非空节点，则不是完全二叉树；
3. 若遍历完整个队列都未违反规则，则是完全二叉树。

核心思想：完全二叉树的层序序列中，所有非空节点必须连续出现在前面，空节点只能出现在末尾。

代码实现（C语言）

intBinaryTreeComplete(BTNode*root){intk=1;if(root==NULL)return1;Queue p;QueueInit(&p);QueuePush(&p,root);while(!QueueEmpty(&p)){BTNode*temp=QueueFront(&p);QueuePop(&p);if(temp==NULL){k=0;continue;}if(temp->_left){if(k==0)return-1;QueuePush(&p,temp->_left);}elseQueuePush(&p,NULL);if(temp->_right){if(k==0)return-1;QueuePush(&p,temp->_right);}elseQueuePush(&p,NULL);}Destroy(&p);return1;}

二叉树的创建与销毁

在实际应用中，二叉树通常不会像教学示例那样手动构建，而是通过序列化数据（如前序遍历序列）动态创建。同时，为避免内存泄漏，使用完毕后必须正确释放所有节点。

1. 通过前序遍历序列创建二叉树

输入格式

使用扩展前序遍历序列（也称“带空标记的前序序列”），用特殊字符（如#）表示空节点。
例如："ABD##E#H##CF##G##"表示如下二叉树：

实现思路

• 使用一个全局或传引用的索引pi遍历字符数组；
• 若当前字符为#，返回NULL；
• 否则创建新节点，并递归构建左右子树。

数组a[]是储存了要求按前序建立树的字符串的顺序 BTNode*BinaryTreeCreate(BTDataType*a,int*pi){if(a[*pi]=='#')//不在此处自加是为了防止在非空节点除指针自己移动。{(*pi)++;//一定要在内部自增,*pi才是真正的下标，别搞混了returnNULL;}BTNode*root=(BTNode*)malloc(sizeof(BTNode));root->_data=a[(*pi)++];root->_left=BinaryTreeCreate(a,pi);root->_right=BinaryTreeCreate(a,pi);returnroot;}//前序建树(通过输入对数组进行前序建树)

二叉树的销毁

为避免内存泄漏和悬空指针（野指针）问题，二叉树的销毁必须遵循以下原则：

销毁原则

1. 必须采用后序遍历顺序释放节点：
   先递归释放左子树，再递归释放右子树，最后释放当前根节点。

   若先释放根节点，则无法再通过root->_left或root->_right访问子节点，导致子树内存泄漏。

2. 避免访问已释放的内存：
   一旦调用free()释放某节点，其所有成员（包括_left、_right）均变为无效，不可再被读取或解引用。

3. 主函数中的根指针应被置为NULL：
   仅释放内存而不置空指针，会导致主函数中保留一个指向已释放内存的悬空指针，后续误用将引发未定义行为（如程序崩溃、数据损坏）。

   通过二级指针传递，可在销毁函数内部直接修改主函数的指针变量，将其安全置NULL。

voidBinaryTreeDestory(BTNode**root)//必须使用后续释放，其他序列释放会导致根节点提前被释放，root->_left,root->_right无法访问{if(*root==NULL)return;BinaryTreeDestory(&(*root)->_left);//传入值是二级指针，所以此处要取地址BinaryTreeDestory(&(*root)->_right);free(*root);*root=NULL;//利用二级指针置空后代码更健壮，使用一级指针只释放也可以，只是安全性不够}

1. 二叉树节点总数（BinaryTreeSize）

思路：
每次访问节点都使记录值加1；

intBinaryTreeSize(BTNode*root){if(root==NULL)return0;returnBinaryTreeSize(root->_left)+BinaryTreeSize(root->_right)+1;}

叶子节点个数（BinaryTreeLeafSize）

定义：叶子节点是左右孩子均为空的节点（即度为 0 的节点）。

思路：

若当前节点为叶子节点（root->_left == NULL && root->_right == NULL），则返回1；

intBinaryTreeLeafSize(BTNode*root){if(root==NULL)return0;if(root->_left==NULL&&root->_right==NULL){return1;}returnBinaryTreeLeafSize(root->_right)+BinaryTreeLeafSize(root->_left);}

3. 查找值为x的节点（BinaryTreeFind）

要求：
若树中存在多个值为x的节点，返回任意一个即可；通常按先序遍历顺序返回第一个匹配的节点。

思路：
若当前节点的值等于x，直接返回当前节点；

BTNode*BinaryTreeFind(BTNode*root,BTDataType x)//找特定值节点{if(root==NULL)returnNULL;if(root->_data==x)returnroot;BTNode*node1=BinaryTreeFind(root->_left,x);//找到后，会直接将该节点作为返回值返回给他的根节点，根节点又会继续执行下面的if判断，此时node1没变，继续返回，由此实现了将节点传递回去if(node1){returnnode1;}BTNode*node2=BinaryTreeFind(root->_right,x);if(node2){returnnode2;}}

我们可以注意到，其实二叉树递归的大部分代码实现都依托于左树递归和右数递归来遍历数组，在合适的时候访问数组