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

2024-01-08 09:28:35

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

🎬个人简介：一个全栈工程师的升级之路！
📋个人专栏：数据结构
🎀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
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：veading@qq.com进行投诉反馈，一经查实，立即删除！