【二叉树】- 四种遍历方式

🕗 发布于 2024-01-08 11:17 数据结构 算法 C c++ 二叉树

本文主要介绍二叉树的四种遍历方式，并实现了四种遍历方式，期间介绍了二叉树以及满二叉树和完全二叉树。

🎬个人简介：一个全栈工程师的升级之路！
📋个人专栏：数据结构
🎀CSDN主页发狂的小花
🌄人生秘诀：学习的本质就是极致重复!

1 二叉树

1 二叉树

二叉树是一种特殊的树形结构，每个节点最多有两个子节点，分别称为左子节点和右子节点。

二叉树每个节点都有一个值，并且满足从根节点到叶子节点的所有路径上的值都是递增或递减的。根据二叉树的性质，我们还可以知道，二叉树中，第 i 层最多有 $2^{k-1}$ 个结点，如果二叉树的深度为 K，那么此二叉树最多有 $2^k - 1$ 个结点。

此外，对于二叉树的遍历方式有三种：前序遍历、中序遍历和后序遍历。

前序遍历的顺序是首先访问根结点，然后递归地遍历左子树，最后递归地遍历右子树；

中序遍历的顺序是首先递归地遍历左子树，然后访问根结点，最后递归地遍历右子树；

后序遍历的顺序是首先递归地遍历左子树，然后递归地遍历右子树，最后访问根结点。

2 完全二叉树和满二叉树

满二叉树与完全二叉树是两种相关但具有不同特点的二叉树结构。

满二叉树是指一个二叉树的所有层都完全填满，且每层的节点数均达到最大值。

完全二叉树则是指除最后一层外，其它各层的节点数均达到最大值，最后一层从左向右连续填充。

具体来说，如果设二叉树的深度为h，那么对于满二叉树来说，每一层的结点数都达到了最大值 $2^{h-1}$ ，即每一层的节点数都是满的；而对于完全二叉树来说，除去最后一层，其它各层的节点数也都达到了最大值，但是最后一层可能并未满。

满二叉树和完全二叉树的主要区别在于：满二叉树的每一层都是满的，即每一层的节点数都达到了最大值；而完全二叉树则是除了最后一层外，其它层都是满的，但最后一层可能不满。

2.1 深度计算

对于有n个节点的满二叉树和完全二叉树：

满二叉树：满二叉树的深度为 $k=log(2*(n+1))$ 。

完全二叉树：在完全二叉树中，具有n个结点的完全二叉树深度为 $log(2*n)+1$ ,其中 $log(2*n)+1$ 是向下取整。

3 二叉树的遍历

二叉树的遍历是指从根结点出发，按照某种次序依次访问二叉树中所有的节点，确保每个节点只被访问一次。

二叉树的遍历方式有以下四种：

（1）先序遍历（根左右）

首先访问根结点，然后递归地遍历左子树，最后遍历右子树。例如对于二叉树：1 2 3 4 5 6 7 8 9 10 11，先序遍历的结果为：1->2->4->8->9->5->10->11->3->6->7。

（2）中序遍历（左根右）

首先遍历左子树，然后访问根结点，最后遍历右子树。例如对于二叉树：1 2 3 4 5 6 7 8 9 10 11，中序遍历的结果为：8->4->9->2->10->5->11->1->6->3->7。

（3）后序遍历（左右根）

首先遍历左子树，然后遍历右子树，最后访问根结点。例如对于二叉树：1 2 3 4 5 6 7 8 9 10 11，后序遍历的结果为：8->9->4->10->11->5->2->6->7->3->1。

（4）层序遍历

它是按广度优先搜索的策略，从根结点出发，依次访问每一层上的节点。这种策略在实际应用中使用较多，如在计算机图形学中用于渲染场景图等。例如对于二叉树：1 2 3 4 5 6 7 8 9 10 11，层次遍历的结果为：1->2->3->4->5->6->7->8->9->10->11

3.1 先序遍历

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void preorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->val);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}

int main() {
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->left->left->left = createNode(8);
    root->left->left->right = createNode(9);
    root->left->right->left = createNode(10);
    root->left->right->right = createNode(11);

    printf("前序遍历二叉树结果：");
    preorderTraversal(root);
    printf("\n");

    return 0;
}

运行结果：

3.2 中序遍历

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void inorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    inorderTraversal(root->left);
    printf("%d ", root->val);
    inorderTraversal(root->right);
}

int main() {
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->left->left->left = createNode(8);
    root->left->left->right = createNode(9);
    root->left->right->left = createNode(10);
    root->left->right->right = createNode(11);

    printf("中序遍历二叉树结果：");
    inorderTraversal(root);
    printf("\n");

    return 0;
}

运行结果：

3.3 后序遍历

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void postorderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->val);
}

int main() {
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->left->left->left = createNode(8);
    root->left->left->right = createNode(9);
    root->left->right->left = createNode(10);
    root->left->right->right = createNode(11);

    printf("后序遍历二叉树结果：");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

运行结果：

3.4 层次遍历

层次遍历使用queue实现比较好，这里提供C++代码，对于C语言需要自己写一个queue的数据结构。

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

TreeNode* createNode(int val) {
    TreeNode *newNode = (TreeNode *)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

void levelOrderTraversal(TreeNode *root) {
    if (root == NULL) {
        return;
    }

    std::queue<TreeNode *> q;
    q.push(root);

    while (!q.empty()) {
        TreeNode *node = q.front();
        q.pop();
        printf("%d ", node->val);

        if (node->left != NULL) {
            q.push(node->left);
        }
        if (node->right != NULL) {
            q.push(node->right);
        }
    }
}

int main() {
    TreeNode *root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    root->left->left->left = createNode(8);
    root->left->left->right = createNode(9);
    root->left->right->left = createNode(10);
    root->left->right->right = createNode(11);

    printf("层次遍历二叉树结果：");
    levelOrderTraversal(root);
    printf("\n");

    return 0;
}

🌈我的分享也就到此结束啦🌈
如果我的分享也能对你有帮助，那就太好了！
若有不足，还请大家多多指正，我们一起学习交流！
📢未来的富豪们：点赞👍→收藏⭐→关注🔍，如果能评论下就太惊喜了！
感谢大家的观看和支持！最后，☺祝愿大家每天有钱赚！！！欢迎关注、关注！

原文地址：https://blog.csdn.net/m0_47324800/article/details/135445120

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Zabbix相关问题及答案（2024）
下一篇：聚观早报 |苹果计划发布生成式AI工具；苏磁科技获超亿元A轮融资

Java项目:校园宿舍管理系统(优质版)(Springboot3+Maven+Mybatis Plus+Vue3+ Element Plus+Mysql)
Springboot3+Maven+Mybatis Plus+Vue3+ Element Plus+Mysql 开发的前后端分离的校园宿舍管理系统。
阅读更多2024-11-16
IntelliJ IDEA新建项目或导入未识别为maven解决
1.首先，我的情况是我新建了一个springboot项目，然后选择类型是Maven但是建立后不是maven项目。当然，前提是你的maven已经在idea上做好配置了。2.打开项目后，从File --》
阅读更多2024-11-16
Gin HTML 模板渲染
Gin HTML模板入门
阅读更多2024-11-16
未来的车网互动如何重塑我们的城市生活
设想一下，在一个寒冷的冬日，你的车辆通过车网互动得知前方桥梁可能结冰，它会自动降低速度，并提醒你注意驾驶安全。公众的参与同样重要，只有当越来越多的车辆加入到车网互动系统中，才能真正发挥其潜力，提高整个
阅读更多2024-11-16
人工智能技术的应用前景及其对生活和工作方式的影响
人工智能技术的应用前景广阔，它不仅在医疗、企业和日常生活中带来了显著的变化，还将继续推动社会的创新和发展。面对 AI 技术带来的机遇和挑战，我们需要共同努力，确保技术的发展能够造福人类社会，创造一个更
阅读更多2024-11-16
《AI技术，让生活更简单》
想象一下，你回到家，灯自动亮了，空调调到你喜欢的温度，冰箱告诉你牛奶快没了，甚至还能帮你预约超市送货。这不是科幻电影，这就是AI技术正在做的事情。
阅读更多2024-11-16
sychronized锁
sychronized 关键字能成为锁的原因，是因为它提供了**内置锁（Intrinsic Lock）**机制，用于线程同步，确保同一时刻只有一个线程能够访问被标记为 synchronized 的代码
阅读更多2024-11-16
SpringBoot 2.2.10 无法执行Test单元测试
同样的Idea版本，现有的项目却可以执行，按照C老师的提示增加对junit5的引用支持，依然没有，StackOverflow上也是提示增加依赖，依赖加完之后执行报错一个 EnginListener N
阅读更多2024-11-16
springMVC 全局异常统一处理
进⾏异常处理，具有集成简单、有良好的扩展性、对已有代码没有⼊侵性等优点，但该⽅法仅能获取到异常信息，若在出现异常时，对需要获取除异常以外的数据的情况不适⽤。Unchecked Exception，⽽
阅读更多2024-11-16
thinkphp6配置多应用项目及多域名访问路由app配置
ThinkPHP 多应用模式初探
阅读更多2024-11-16

【二叉树】- 四种遍历方式

1 二叉树

2 完全二叉树和满二叉树

2.1 深度计算

3 二叉树的遍历

3.1 先序遍历

3.2 中序遍历

3.3 后序遍历

3.4 层次遍历

相关文章