文章目录

二叉树的遍历

二叉树的遍历可以分为深度优先遍历（Depth-First Traversal）和广度优先遍历（Breadth-First Traversal），它们是两种不同的遍历策略。

1.深度优先遍历（Depth-First Traversal）：

​ 深度优先遍历是沿着树的深度遍历树的节点，尽可能深地搜索树的分支。

​ 深度优先遍历可以进一步分为前序遍历、中序遍历和后序遍历。

​ 在二叉树中，深度优先遍历一般使用递归实现，但也可以使用栈来模拟递归的过程。

2.广度优先遍历（Breadth-First Traversal）：

​ 广度优先遍历是按层次从上到下逐层访问树的节点。

​ 广度优先遍历一般使用队列来实现，从根节点开始，将每一层的节点按顺序加入队列，然后依次访问。

下面分别介绍二叉树的深度优先遍历和广度优先遍历的具体实现方法：

深度优先遍历（Depth-First Traversal）：

​ 前序遍历（Preorder Traversal）：根节点 -> 左子树 -> 右子树

​ 中序遍历（Inorder Traversal）：左子树 -> 根节点 -> 右子树

​ 后序遍历（Postorder Traversal）：左子树 -> 右子树 -> 根节点

广度优先遍历（Breadth-First Traversal）：

​ 从根节点开始，依次按层次遍历每个节点，可以使用队列来辅助实现。

1.二叉树的递归遍历

二叉树的递归遍历是一种直观且常用的遍历方式，它通过递归函数来实现对二叉树节点的访问。递归遍历主要包括前序遍历、中序遍历和后序遍历。

下面是三种递归遍历的具体实现方法：

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

// 定义二叉树节点结构
struct TreeNode {
    int value;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 前序遍历
void preorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        printf("%d ", root->value);  // 访问根节点
        preorderTraversal(root->left);  // 递归遍历左子树
        preorderTraversal(root->right);  // 递归遍历右子树
    }
}

// 中序遍历
void inorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);  // 递归遍历左子树
        printf("%d ", root->value);  // 访问根节点
        inorderTraversal(root->right);  // 递归遍历右子树
    }
}

// 后序遍历
void postorderTraversal(struct TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);  // 递归遍历左子树
        postorderTraversal(root->right);  // 递归遍历右子树
        printf("%d ", root->value);  // 访问根节点
    }
}

// 创建二叉树节点
struct TreeNode* createNode(int value) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    if (newNode != NULL) {
        newNode->value = value;
        newNode->left = NULL;
        newNode->right = NULL;
    }
    return newNode;
}

// 主函数
int main() {
    // 构建一棵二叉树
    struct TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    // 输出各种遍历结果
    printf("Preorder traversal: ");
    preorderTraversal(root);
    printf("\n");

    printf("Inorder traversal: ");
    inorderTraversal(root);
    printf("\n");

    printf("Postorder traversal: ");
    postorderTraversal(root);
    printf("\n");

    // 释放二叉树节点内存
    free(root->left->right);
    free(root->left->left);
    free(root->right);
    free(root->left);
    free(root);

    return 0;
}

下面我们以力扣中的前序遍历（中序遍历，后序遍历同理）一题来举例：

144. 二叉树的前序遍历

在这里插入图片描述

// 前序遍历函数
void preorder(struct TreeNode* root, int* ans, int* resSize) {
    // 如果当前节点为空，则返回
    if (root == NULL)
        return;
    // 将当前节点的值加入到结果数组中，并更新结果数组大小
    ans[(*resSize)++] = root->val; 
    // 递归地对左子树进行前序遍历
    preorder(root->left, ans, resSize);
    // 递归地对右子树进行前序遍历
    preorder(root->right, ans, resSize);
}
// 返回二叉树的前序遍历结果
int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    // 分配存储结果的数组内存空间
    int* ans = (int*)malloc(sizeof(int) * 10000);
    // 初始化返回结果的大小为0
    *returnSize = 0;
    // 调用前序遍历函数
    preorder(root, ans, returnSize);
    // 返回结果数组指针
    return ans;
}

2.二叉树的迭代遍历

迭代遍历二叉树可以使用栈或队列来辅助实现。以下是迭代遍历二叉树的一般步骤：

1.前序遍历的迭代版本：

​ 使用栈来辅助实现。

​ 根据前序遍历的顺序，先将根节点压入栈中。

​ 当栈不为空时，弹出栈顶节点，访问该节点，并依次将其右子节点和左子节点压入栈中（注意顺序）。

​ 重复上述过程，直到栈为空。

2.中序遍历的迭代版本：

​ 使用栈来辅助实现。

​ 从根节点开始，将当前节点及其所有左子节点压入栈中，直到最左下的叶子节点。

​ 弹出栈顶节点，访问该节点，并将其右子节点作为当前节点。

​ 重复上述步骤，直到栈为空且当前节点为null。

3.后序遍历的迭代版本：

​ 使用两个栈来辅助实现。

​ 使用一个栈按照根、右、左的顺序遍历二叉树，将遍历结果存储到另一个栈中。

​ 当遍历完成后，从存储结果的栈中弹出元素即为后序遍历的结果。

1>前序遍历

二叉树的迭代法前序遍历有两种不同的形式。

第一种：

第一种方法大概思路就是从根节点开始，先把根节点存进栈中，取出来一个放进答案中，后分别向栈中该节点的右，左孩子节点（不为空），再取出来一个放进答案中并向栈中存进它的右，左孩子节点，直到栈为空，我们也就实现了前序遍历。

动态展示如下：

二叉树前序遍历（迭代法）

代码实现如下：

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = malloc(sizeof(int) * 101);
    *returnSize = 0;
    // 如果根节点为空，直接返回结果数组
    if (root == NULL) {
        return res;
    }

    // 声明一个数组作为栈，用于辅助遍历二叉树
    struct TreeNode* stk[2000];
    // 初始化栈顶指针
    int stk_top = 0;
    // 将根节点压入栈中
    stk[stk_top++] = root;

    // 当栈不为空时，进行遍历
    while (stk_top > 0) {
        // 弹出栈顶的节点
        struct TreeNode* node = stk[--stk_top];//这里是得到指针，没有*就是浅拷贝
        // 将节点的值存储到结果数组中
        res[(*returnSize)++] = node->val;
        // 如果节点有右子节点，则将右子节点压入栈中
        if (node->right) {
            stk[stk_top++] = node->right;
        }
        // 如果节点有左子节点，则将左子节点压入栈中
        if (node->left) {
            stk[stk_top++] = node->left;
        }
    }

    // 返回遍历结果数组
    return res;
}
第二种：

第二种方法大概思路就是从根节点开始遍历，一直向左孩子节点遍历，边遍历边存储，直到为空后向上返回一层，将右孩子节点变为新的根节点，然后一直循环，直到遍历完所有的节点。

下面我们来看代码：

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    int* res = (int*)malloc(sizeof(int) * 2000);
    *returnSize = 0;
    if (root == NULL)
        return res;

    struct TreeNode* stk[2000];
    struct TreeNode* node = root;
    int stk_top = 0; 
    while (stk_top > 0 || node != NULL) {
        while (node != NULL) {
            res[(*returnSize)++] = node->val;
            stk[stk_top++] = node;
            node = node->left;
        }
        node = stk[--stk_top];
        node = node->right;
    }
    
    return res;
}
2>后序遍历

后序遍历也分为两种办法。

第一种：

第一种对前序遍历的第一种方法进行修改就可以得到。

​ 前序遍历的顺序是：中->右->左

​ 得到的结果是：中->左->右

而后续我们需要得到的顺序是：左->右->中

那么我们可以把遍历顺序改为：中->左->右

​ 得到的结果是：中->右->左

我们在整体交换一下顺序，便可以得到：左->右->中

有了思路，我们下来直接来看代码吧：

void reverse(int* arr, int* returnSize) {
    int left = 0;
    int right = (*returnSize) - 1;
    while (left < right) {
        int temp = arr[left];
        arr[left++] = arr[right];
        arr[right--] = temp;
    }
}

int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if (root == NULL) {
        return NULL;
    }
    int* ret = (int*)malloc(sizeof(int) * 101);
    struct TreeNode* stack[101];
    int stacktop = 0;
    stack[stacktop++] = root;
    while (stacktop > 0) {
        struct TreeNode* node = stack[--stacktop];
        ret[(*returnSize)++] = node->val;
        if (node->left) {
            stack[stacktop++] = node->left;
        }
        if (node->right) {
            stack[stacktop++] = node->right;
        }
    }
    reverse(ret, returnSize);
    return ret;
}
第二种：

我们先来看代码：

int *postorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = malloc(sizeof(int) * 2001);
    *returnSize = 0;
    if (root == NULL) {
        return res;
    }
    struct TreeNode **stk = malloc(sizeof(struct TreeNode *) * 2001);
    int top = 0;
    struct TreeNode *prev = NULL;
    while (root != NULL || top > 0) {
        while (root != NULL) {
            stk[top++] = root;
            root = root->left;
        }
        root = stk[--top];
        if (root->right == NULL || root->right == prev) {
            res[(*returnSize)++] = root->val;
            prev = root;
            root = NULL;
        } else {
            stk[top++] = root;
            root = root->right;
        }
    }
    return res;
}

第二种方法也是借助一个栈去实现，先向左遍历并入栈，到达NULL后返回一层。

但是我们在记录的时候需要进行判断：root->right == NULL || root->right == prev，这行代码是用来判断右孩子节点为空或者已经被访问过了，在进行记录。

可以借助下面的例子更好地理解：

假设我们有以下二叉树：

        1
       / \
      2   3
     / \
    4   5

首先，根据输入的树结构，我们传入树的根节点 root，并初始化一个大小为2001的结果数组 res 和一个辅助栈 stk。

进入循环，由于根节点不为空，将根节点及其左子树依次入栈，直到当前节点为NULL：

root = 1
stack = [1]
root = 2
stack = [1, 2]
root = 4
stack = [1, 2, 4]

当栈不为空时，开始出栈处理节点：

root = 4 (stack = [1, 2], top = 2)

由于4的右子树为空，或者右子树已经被访问过（此时 prev 为4），将4加入结果数组，更新 prev 为4，将 root 置为NULL。

res = [4], returnSize = 1

继续出栈处理节点：

root = 2 (stack = [1], top = 1)

由于2的右子树不为空且未被访问过，将2重新入栈，然后将 root 指向2的右子树3，继续遍历右子树。

stack = [1, 2], root = 3

将3及其左子树入栈，直到当前节点为NULL：

stack = [1, 2, 3]

开始出栈处理节点：

root = 3 (stack = [1, 2], top = 2)

由于3的右子树为空，或者右子树已经被访问过（此时 prev 为3），将3加入结果数组，更新 prev 为3，将 root 置为NULL。

res = [4, 3], returnSize = 2

继续出栈处理节点：

root = 2 (stack = [1], top = 1)

由于2的右子树已经被访问过（此时 prev 为2），将2加入结果数组，更新 prev 为2，将 root 置为NULL。

res = [4, 3, 2], returnSize = 3

继续出栈处理节点：

root = 1 (stack = [], top = 0)

由于1的右子树不为空且未被访问过，将1重新入栈，然后将 root 指向1的右子树NULL，继续遍历右子树。

stack = [1], root = NULL

开始出栈处理节点：

root = 1 (stack = [], top = 0)

由于1的右子树为空，或者右子树已经被访问过（此时 prev 为1），将1加入结果数组，更新 prev 为1，将 root 置为NULL。

res = [4, 3, 2, 1], returnSize = 4

最后，遍历结束，函数返回结果数组 [4, 3, 2, 1]，其中存储了二叉树的后序遍历结果。

3>中序遍历

中序遍历类似于前序遍历，只使用一个栈可以实现，只不过不用边向左遍历边记录，而是在返回的时候记录答案。

下面直接展示代码：

int* inorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    int* res = malloc(sizeof(int) * 501);
    struct TreeNode** stk = malloc(sizeof(struct TreeNode*) * 501);
    int top = 0;

    while (root != NULL || top > 0) {
        while (root != NULL) {
            stk[top++] = root; 
            root = root->left; 
        }
        root = stk[--top];
        res[(*returnSize)++] = root->val;
        root = root->right;
    }
    return res;
}

3.二叉树的层序遍历

层序遍历（Level Order Traversal）是一种按层次顺序逐层访问树节点的遍历方式，通常使用队列来实现。

下面是动态演示：

102二叉树的层序遍历

下面直接展示代码：

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
    // 分配结果数组的内存并初始化变量
    int **ret = malloc(sizeof(int*) * 2010); // 假设最大层数为 2010
    *returnColumnSizes = malloc(sizeof(int) * 2010); // 假设最大层数为 2010
    typedef struct TreeNode TreeNode;
    TreeNode **que = malloc(sizeof(TreeNode*) * 2010); // 使用队列执行层次遍历
    int front, rear;
    front = rear = 0;
    
    // 如果根节点为空，则返回空结果
    if (root == NULL) {
        *returnSize = 0;
        return ret;
    }
    
    // 将根节点入队
    que[rear++] = root;
    
    // 使用队列执行层次遍历
    while (rear != front) {
        // 获取当前层节点的数量
        int count = rear - front;
        
        // 为当前层的值分配内存
        int* r = malloc(sizeof(int) * count);
        
        // 遍历当前层，并将值存储到数组中
        for (int i = 0; i < count; ++i) {
            TreeNode* t = que[front++];
            r[i] = t->val;
            // 如果左右子节点不为空，则入队
            if (t->left != NULL)
                que[rear++] = t->left;
            if (t->right != NULL)
                que[rear++] = t->right;
        }
        // 存储当前层的列大小
        (*returnColumnSizes)[*returnSize] = count;
        // 存储当前层的结果数组
        ret[(*returnSize)++] = r;
    }
    // 返回结果数组的大小
    return ret;
}

参考资料来源：代码随想录

已经到底啦！！

# 深度优先 # 算法
Logo
开放原子开发者工作坊

开放原子开发者工作坊旨在鼓励更多人参与开源活动，与志同道合的开发者们相互交流开发经验、分享开发心得、获取前沿技术趋势。工作坊有多种形式的开发者活动，如meetup、训练营等，主打技术交流，干货满满，真诚地邀请各位开发者共同参与！

更多推荐

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

第二届开放原子大赛首批创新成果集结武汉，诚邀广大开发者共鉴开源技术盛宴

avatar 开放原子开发者工作坊

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

诚邀报名 | 开源基础设施能力建设分论坛：打造开源生态的“心脏”

avatar 开放原子开发者工作坊

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

诚邀报名 | 编程语言分论坛：AI时代的技术革新与开源实践

avatar 开放原子开发者工作坊