• 算法 二叉树的遍历（迭代法/递归法）

    文章目录

    前言

    在这里插入图片描述

    一、前序遍历（根->左->右）

    1. 题意

    题目链接
    在这里插入图片描述

    2. 代码

    （1）递归法
    void preorderTravlMethod(struct TreeNode* root, int* returnSize, int* array)
{
    if (!root) return;

    array[(*returnSize)++] = root->val;

    preorderTravlMethod(root->left, returnSize, array);
    preorderTravlMethod(root->right, returnSize, array);
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = 0;
    if (root == NULL)
    {
        return NULL;
    }

    int *array = (int*)malloc(sizeof(int) * 100);
    array[(*returnSize)++] = root->val;

    preorderTravlMethod(root->left, returnSize, array);
    preorderTravlMethod(root->right, returnSize, array);

    return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    （2）迭代法

    迭代法 本质上也是递归，自己内部实现了递归栈。用迭代方法实现递归函数，与递归等价。

    递归栈的实现，使用了链表结构，并且将新链表节点采用“头接法”，接入到链表的前面，形成栈的“后入先出”结构。

    //迭代法 本质上也是递归，自己内部实现了递归栈
struct stack_tree {
    struct TreeNode* node;
    struct stack_tree* next;
};

struct stack_tree* new_stack_tree(struct TreeNode* node)
{
    struct stack_tree* stack_tree_node = (struct stack_tree*)malloc(sizeof(*stack_tree_node));
    stack_tree_node->node = node;
    stack_tree_node->next = NULL;

    return stack_tree_node;
}

int* preorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = 0;
    if (root == NULL)
    {
        return NULL;
    }

    struct stack_tree *tmp, *new_node;
    struct stack_tree *head = new_stack_tree(root);
    int *array = (int*)malloc(sizeof(int) * 100);

    while (head)
    {
        tmp = head;
        head = head->next;
        array[(*returnSize)++] = tmp->node->val;
        
        if(tmp->node->right)
        {
            new_node = new_stack_tree(tmp->node->right);
            new_node->next = head;
            head = new_node;
        }
        if(tmp->node->left)
        {
            new_node = new_stack_tree(tmp->node->left);
            new_node->next = head;
            head = new_node;
        }
    }
    
    return array;
}


    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50

    二、中序遍历（左->根->右）

    1. 题意

    题目链接

    在这里插入图片描述

    2. 代码

    （1）递归法
    //递归法
void inorderTravlMethod(struct TreeNode* root, int* returnSize, int* array)
{
    if (!root) return;

    inorderTravlMethod(root->left, returnSize, array);
    array[(*returnSize)++] = root->val;
    inorderTravlMethod(root->right, returnSize, array);
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = 0;
    if (root == NULL)
    {
        return NULL;
    }

    int *array = (int*)malloc(sizeof(int) * 100);

    inorderTravlMethod(root->left, returnSize, array);
    array[(*returnSize)++] = root->val;
    inorderTravlMethod(root->right, returnSize, array);

    return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    （2）迭代法

    依然使用“头插法”创建链表，形成栈结构。

    注意：因为是中序遍历，所以会先后把右节点，根节点，和左节点入栈。

    当左节点出栈处理结束，就轮到根节点出栈了。此时处理根节点时，就不能再把根节点的左右节点入栈；因为前面已经将左右节点入栈了，不能重复入栈。

    所以，需要先把根节点的左右节点保存为临时变量，再将根节点的左右指针归零。之后按照右节点变量，根节点，左节点变量入栈。之后就进行出栈处理即可。

    //迭代法 本质上也是递归，自己内部实现了递归栈
struct stack_tree {
    struct TreeNode* node;
    struct stack_tree* next;
};

struct stack_tree* new_stack_tree(struct TreeNode* node)
{
    struct stack_tree* stack_tree_node = (struct stack_tree*)malloc(sizeof(*stack_tree_node));
    stack_tree_node->node = node;
    stack_tree_node->next = NULL;

    return stack_tree_node;
}

int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = 0;
    if (root == NULL)
    {
        return NULL;
    }

    struct stack_tree *new_node;
    struct stack_tree *head = NULL; //= new_stack_tree(root);
    int *array = (int*)malloc(sizeof(int) * 100);

    while (root || head)
    {
        while (root)
        {
            new_node = new_stack_tree(root);
            new_node->next = head;
            head = new_node;

            root = root->left;
        }
        
        root = head->node;
        head = head->next;

        array[(*returnSize)++] = root->val;

        root = root->right;
        
    }
    
    return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49

    三、后序遍历（左->右->根）

    1. 题意

    题目链接
    在这里插入图片描述

    2. 代码

    （1）递归法
    //递归法
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
void postorderTravlMethod(struct TreeNode* root, int* returnSize, int* array)
{
    if (!root) return;

    postorderTravlMethod(root->left, returnSize, array);
    postorderTravlMethod(root->right, returnSize, array);
    array[(*returnSize)++] = root->val;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = 0;
    if (root == NULL)
    {
        return NULL;
    }

    int *array = (int*)malloc(sizeof(int) * 100);

    postorderTravlMethod(root->left, returnSize, array);
    postorderTravlMethod(root->right, returnSize, array);
    array[(*returnSize)++] = root->val;

    return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    （2）迭代法

    依然使用“头插法”创建链表，形成栈结构。

    注意：因为是后序遍历，所以会先后把左节点，右节点，和根节点入栈。

    当左节点和右节点出栈处理结束，就轮到根节点出栈了。此时处理根节点时，就不能再把根节点的左右节点入栈；因为前面已经将左右节点入栈了，不能重复入栈。

    所以，需要先把根节点的左右节点保存为临时变量，再将根节点的左右指针归零。之后按照根节点，右节点变量，左节点变量，入栈。之后就进行出栈处理即可。

    struct stack_tree {
    struct TreeNode* node;
    struct stack_tree* next;
};

struct stack_tree* new_stack_tree(struct TreeNode* node)
{
    struct stack_tree* stack_tree_node = (struct stack_tree*)malloc(sizeof(*stack_tree_node));
    stack_tree_node->node = node;
    stack_tree_node->next = NULL;

    return stack_tree_node;
}

int* postorderTraversal(struct TreeNode* root, int* returnSize)
{
    *returnSize = 0;
    if (root == NULL)
    {
        return NULL;
    }

    struct stack_tree *prev_node,  *new_node;
    struct stack_tree *head = NULL;
    int *array = (int*)malloc(sizeof(int) * 100);

    while (root || head)
    {
        while (root)
        {
            new_node = new_stack_tree(root);
            new_node->next = head;
            head = new_node;

            root = root->left;
        }

        root = head->node;
        head = head->next;

        if (root->right == NULL || root->right == prev_node)
        {
            array[(*returnSize)++] = root->val;
            prev_node = root;
            root = NULL;
        }
        else
        {
            new_node = new_stack_tree(root);
            new_node->next = head;
            head = new_node;

            root = root->right;
        }
    }
    
    return array;
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58

    四、层序遍历

    层序遍历：按照层级，从上往下，从左到右。使用广度优先搜索算法。

    如下图所示，层序遍历即是，先将第一层的所有节点全部处理后，再处理第二层的所有节点，接着处理第三层的所有节点，以此类推。

    在这里插入图片描述

    1. 代码

    （1）递归法

    这里我们可以使用两条链表，两条链表都属于队列结构。

    第一条链表首先挂上了根节点，称为“待处理链表”，此链表上的所有节点属于队列结构，从头向后依次处理。

    第二条链表称为“待填充链表”，用来装载 第一条链表上的所有节点的左右节点，并且使用“尾插法”形成“先进先出”的队列。

    可以想象，有这么一个递归函数，参数列表为一个“待处理链表”和一个“待填充链表”。

    第一次轮回：“待处理链表”只有一个根节点，即树的第一层；我们将根节点的左右节点装进“待填充链表”，并且对根节点做用户指定的处理（如打印根节点的val）。此时，对函数自身进行递归调用，传入的参数为：当前的参数“待填充链表”由于装满了节点，成为下一次递归的“待处理链表”，当前的参数“待处理链表”由于所有节点处理完毕，成为了下一次递归的“待填充链表”。

    第二次轮回：“待处理链表”为树根节点的左右节点，即树的第二层；进行同样的处理后，第二层节点的子节点又装载到了“待填充链表”中，“待填充链表”中的节点即为第三层节点。由此继续进行递归，直到“待处理链表”中没有节点，即递归结束并返回。

    （2）迭代法

    迭代法很简单，也是用到了队列结构。只需要定义一个队列，并将根节点入队。后面对这个队列进行迭代处理：只要队列中有节点，就把队列头的节点取出，做处理操作后，再把节点的左右节点依次入队。这样，第一层的节点会把第二层的节点全部入队；第二层的节点把第三次的节点全部入队，以此类推。

    在这里插入图片描述

  • 相关阅读:
    QT中闹钟的设置
    【SwiftUI模块】0024、SwiftUI创建一个时尚的3D轮播滑块
    从供给面到需求面研究方法论的转变-中国视角下的宏观经济
    基于微信小程序的校园活动平台的设计与实现
    数据结构：KMP算法的原理图解和代码解析
    Hive--07---函数简介--常用函数1
    微机原理与接口技术
    2022年湖北天门中级工程师职称评审要求是什么呢？如何评审呢？甘建二
    华夏ERP打包手册
    python中的抽象方法
  • 原文地址：https://blog.csdn.net/weixin_42109053/article/details/126356851