AIPRO AIPRO

二叉树遍历：递归与层序的深度剖析，轻松征服算法岗

5小时前发布 gsjqwyl
1 0 0

文章标题：二叉树遍历：递归法与层序法的透彻解读，助力算法岗位

文章内容：

震撼！二叉树遍历的递归魔法与层序奥秘全面剖析，助你在算法岗面试中脱颖而出

  • 二 叉 树
    • 定 义
  • 前 序 遍 历
    • 定 义
    • 递 归 实 现
  • 中 序 遍 历
    • 定 义
    • 递 归 实 现
  • 后 序 遍 历
    • 定 义
    • 递 归 实 现
  • 层 序 遍 历
    • 定 义
    • 代 码 实 现
  • 第 k 层 结 点 的 个 数
  • 计 算 树 的 高 度
  • 计 算 树 的 节 点 数 目
  • 判 断 是 否 为 完 全 二 叉 树
  • 销 毁 二 叉 树
  • 总 结

二叉树是计算机科学中至关重要的数据结构，在搜索、排序等领域应用广泛。遍历作为其核心操作，包含前序、中序、后序及层序等方式，是理解树结构和实现相关算法的基础。本文将剖析二叉树遍历机制及衍生应用。

二 叉 树

对于二叉树而言，普通的无序二叉树在增删查改方面没有实际价值，原因在于其结构复杂，不如链表实用。

定 义

二叉树遍历指的是按照特定规则，依次对二叉树中的节点进行操作，且每个节点仅操作一次。一棵二叉树由根节点、左子树和右子树组成。

前 序 遍 历

定 义

前序遍历也叫前根遍历，按照根节点、左子树、右子树的顺序依次进行访问。

例如图中所示的二叉树，前序遍历的访问顺序依次为1、2、3、NULL（3的左子树）、NULL（3的右子树）、NULL（2的右子树）、4、5、NULL（5的左子树）、NULL（5的右子树）、6、NULL（6的左子树）、NULL（6的右子树）。

递 归 实 现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}
//     1
//  2     4 
//3     5   6
BTNode* CreatTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    BTNode* node7 = BuyNode(7);
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}
//前序遍历
void PreOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    printf("%d ", root->data);
    PreOrder(root->left);
    PreOrder(root->right);
}
int main()
{
    BTNode* root = CreatTree();
    PreOrder(root);
    return 0; 
}

（1）当根节点不为空时，访问并输出根节点。
（2）根节点1的左子树不为空，遍历节点2。
（3）节点2的左子树不为空，遍历节点3。
（4）节点3的左子树为空，输出NULL后返回节点3。
（5）节点3的右子树为空，输出NULL后返回节点3。
（6）返回节点3后，回退到节点2，节点2的右子树为空，输出NULL后回退到根节点1。
（7）根节点1的右子树不为空，遍历其右子树。
（8）节点4的左子树不为空，遍历节点5。
（9）节点5的左子树为空，输出NULL后返回节点5。
（10）节点5的右子树为空，输出NULL后返回节点4。
（11）节点4的右子树不为空，输出节点6。
（12）节点6的左子树为空，输出NULL后返回节点6。
（13）节点6的右子树为空，输出NULL后返回根节点，前序遍历结束。

中 序 遍 历

定 义

中序遍历也叫中根遍历，按照左子树、根节点、右子树的顺序依次进行访问。需注意左树访问完成后才能访问根节点。

例如图中所示的二叉树，中序遍历的访问顺序依次为NULL（3的左子树）、3、NULL（3的右子树）、2、NULL（2的右子树）、1、NULL（5的左子树）、5、NULL（5的右子树）、4、NULL（6的左子树）、6、NULL（6的右子树）。

递 归 实 现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}
//     1
//  2     4 
//3     5   6
BTNode* CreatTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    BTNode* node7 = BuyNode(7);
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}
//中序遍历
void InOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    InOrder(root->left);
    printf("%d ", root->data);
    InOrder(root->right);
}
int main()
{
    BTNode* root = CreatTree();
    InOrder(root);
    return 0; 
}

（1）首先遍历3的左子树，为空，输出NULL后返回节点3。
（2）遍历节点3后，遍历其右子树。
（3）节点3的右子树为空，输出NULL后，返回到节点2。
（4）遍历节点2后，遍历其右子树。
（5）节点2的右子树为空，输出NULL后，返回到根节点。
（6）根节点不为空，遍历根节点后遍历5的左子树。
（7）节点5的左子树为空，输出NULL后返回节点5。
（8）遍历节点5后，遍历其右子树。
（9）节点5的右子树为空，输出NULL后返回节点4。
（10）遍历节点4后，遍历6的左子树。
（11）节点6的左子树为空，输出NULL后返回节点6。
（12）遍历节点6后，遍历其右子树。
（13）节点6的右子树为空，输出NULL后返回根节点，中序遍历结束。

后 序 遍 历

定 义

后序遍历也叫后根遍历，按照左子树、右子树、根节点的顺序依次进行访问。

例如图中所示的二叉树，后序遍历的访问顺序依次为NULL（3的左子树）、NULL（3的右子树）、3、NULL（2的右子树）、2、NULL（5的左子树）、NULL（5的右子树）、5、NULL（6的左子树）、NULL（6的右子树）、6、4、1。

递 归 实 现

#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
typedef int BTDataType;
typedef struct BinaryTreeNode
{
    BTDataType data;
    struct BinaryTreeNode* left;
    struct BinaryTreeNode* right;
}BTNode;
BTNode* BuyNode(BTDataType x)
{
    BTNode* node = (BTNode*)malloc(sizeof(BTNode));
    if (node == NULL)
    {
        perror("malloc fail");
        return NULL;
    }
    node->data = x;
    node->left = NULL;
    node->right = NULL;
    return node;
}
//     1
//  2     4 
//3     5   6
BTNode* CreatTree()
{
    BTNode* node1 = BuyNode(1);
    BTNode* node2 = BuyNode(2);
    BTNode* node3 = BuyNode(3);
    BTNode* node4 = BuyNode(4);
    BTNode* node5 = BuyNode(5);
    BTNode* node6 = BuyNode(6);
    BTNode* node7 = BuyNode(7);
    node1->left = node2;
    node1->right = node4;
    node2->left = node3;
    node4->left = node5;
    node4->right = node6;
    return node1;
}
//后序遍历
void PostOrder(BTNode* root)
{
    if (root == NULL)
    {
        printf("NULL ");
        return;
    }
    PostOrder(root->left);
    PostOrder(root->right);
    printf("%d ", root->data);
}
int main()
{
    BTNode* root = CreatTree();
    PostOrder(root);
    return 0; 
}

（1）首先遍历3的左子树，为空，输出NULL。
（2）遍历3的右子树，为空，输出NULL后返回节点3。
（3）遍历节点3后返回2的右子树。
（4）2的右子树为空，输出NULL后，返回到节点2。
（5）遍历节点2后返回到5的左子树。
（6）5的左子树为空，输出NULL后，返回到5的右子树。
（7）5的右子树为空，输出NULL后，返回到5。
（8）遍历5后返回到6的左子树。
（9）6的左子树为空，输出NULL后，返回到6的右子树。
（10）6的右子树为空，输出NULL后，返回到6。
（11）遍历6后返回到4。
（12）遍历4后返回到根节点。
（13）遍历根节点。

层 序 遍 历

定 义

从根节点出发，按照“从上到下、从左到右”的层次顺序，逐层访问树的节点。例如二叉树有多层节点，先访问完第1层（根节点），再依次访问第2层、第3层……同层节点按从左到右顺序处理。图中所示的二叉树层序遍历的访问顺序依次为1、2、3、4、5、6。

代 码 实 现

使用队列进行层序遍历。

Queue.h

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

typedef struct BinaryTreeNode* QDataType;
typedef struct QueueNode
{
    struct QueueNode* next;
    QDataType data;
}QNode;

typedef struct Queue
{
    QNode* head;
    QNode* tail;
    int size;
}Queue;

//初始化队列
void QueueInit(Queue* pq);

//销毁队列
void QueueDestory(Queue* pq);

//队尾入队列
void QueuePush(Queue* pq,QDataType x);

//队头出队列
void QueuePop(Queue* pq);

//获取队列中有效元素个数
int QueueSize(Queue* pq);

//检查队列是否为空
bool QueueEmpty(Queue* pq);

//取出队头的数据
QDataType QueueFront(Queue* pq);

//取出队尾的数据
QDataType QueueBack(Queue* pq);

//输出队列
void QueuePrint(Queue* pq);

void QueueMiddlePush(void(*pf)(Queue* pq, QDataType x), Queue* pq);

void QueueMiddle(Queue* pq, int num);

//保存队列到文件中
void QueueSave(Queue* pq);

//从文件中加载队列
void QueueLoad(Queue* pq);

//输出队列元素时删除队列元素
void QueuePrintDestory(Queue* pq);

Queue.c

“`c

define _CRT_SECURE_NO_WARNINGS 1

include “Queue.h”

void QueueInit(Queue* pq)
{
assert(pq);
pq->head = pq->tail = NULL;
pq->size = 0;
QueueLoad(pq);
}

void QueueDestory(Queue pq)
{
assert(pq);
QNode cur = pq->head;
while (cur)
{
QNode next = cur->next;
free(cur);
cur = next;
}
pq->head = pq->tail = NULL;
pq->size = 0;
}
void QueuePush(Queue pq, QDataType x)
{
assert(pq);
QNode newnode = (QNode)malloc(sizeof(QNode));
if (newnode == NULL)
{
perror(“newnode”);
return;
}
newnode->data = x;
newnode->next = NULL;
if (pq->head == NULL)
{
assert(pq->tail == NULL);
pq->head = pq->tail = newnode;
}
else
{
pq->tail->next = newnode;
pq->tail = newnode;
}
pq->size++;
}

void QueuePop(Queue pq)
{
assert(pq);
assert(pq->head != NULL);
//方法1
//QNode next = pq->head->next;
//free(pq->head);
//pq->head = next;
//if (pq->head == NULL)
//{
// pq->tail = NULL;
//}
//方法2
if (pq->head->next == NULL)
{
free(pq->head);
pq->tail = pq->head = NULL;
}
else
{
QNode next = pq->head->next;
free(pq->head);
pq->head = next;
}
pq->size–;
}
int QueueSize(Queue pq)
{
assert(pq);
return pq->size;
}
bool QueueEmpty(Queue* pq)
{
assert(pq);
//return pq->size == 0;
return pq->head == NULL && pq->tail == NULL;
}

QDataType QueueFront(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->head->data;
}

QDataType QueueBack(Queue* pq)
{
assert(pq);
assert(!QueueEmpty(pq));
return pq->tail->data;
}

void QueuePrint(Queue pq)
{
assert(pq);
QNode cur = pq->head;
if (QueueEmpty(pq))

© 版权声明
文章版权归作者所有，未经允许请勿转载。
上一篇

没有更多了...

下一篇

没有更多了...

相关文章

Python类的数据组织变革：首章——类替临时结构之举
gsjqwyl
0
🚀 2025最新PyCharm永久激活教程｜破解补丁+激活码一键搞定（支持2099年）
gsjqwyl
20
Java微信小程序开发SDK应用指南
gsjqwyl
53
🚀 2025年最新IDEA激活码 & 永久破解教程（支持JetBrains全家桶）
gsjqwyl
18
2025年最新DataGrip永久破解教程（附激活码/注册码）🔥
gsjqwyl
56
2025年最新PyCharm激活码分享 | 永久破解PyCharm教程（支持2099年）
gsjqwyl
8

暂无评论

暂无评论...
添加小工具
点此为“正文侧边栏”添加小工具
Copyright © 2025 AIPRO 陇ICP备2022001249号-4