数据结构之二叉树详解及遍历算法（C/C#/C++）

🕗 发布于 2024-07-18 12:16 数据结构 算法 c语言 c++ c#

文章目录

一、二叉树的基本概念
二、二叉树的遍历
三、C语言实现
四、C#语言实现
五、C++语言实现
总结

当涉及到数据结构中的二叉树及其遍历方式时，了解如何正确操作和遍历二叉树是至关重要的。以下是关于二叉树及其三种常见遍历方式（前序、中序、后序）的详细解释和示例，适用于C、C#和C++语言。这篇博客将深入讨论二叉树的定义、每种遍历方式的原理、实现方法和示例代码。

一、二叉树的基本概念

概念

二叉树是每个节点最多有两个子树的树结构。通常，每个节点包含一个数据元素和两个指向其子节点的指针。二叉树具有以下特点：

每个节点最多有两个子节点，分别称为左子节点和右子节点。
左子节点的值小于父节点的值，右子节点的值大于父节点的值（这是二叉搜索树的特点）。
以下是二叉树的一个示例：

    A
   /  \
  B    C
 /  \    \
D    E    F

二叉树的类型

根据节点的排列方式和特性，可以将二叉树分为不同的类型：

满二叉树（Full Binary Tree）：每个节点要么是叶子节点，要么有两个子节点。
完全二叉树（Complete Binary Tree）：在满二叉树的基础上，从左到右填充节点，直到最后一层，且最后一层的节点都靠左对齐。
平衡二叉树（Balanced Binary Tree）：任意节点的左右子树的高度差不超过1。

二、二叉树的遍历

二叉树的遍历是指按照某种顺序访问树中的所有节点。常见的遍历方法有三种：前序遍历、中序遍历和后序遍历。

1. 前序遍历

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

示例：A -> B -> D -> E -> C -> F

2. 中序遍历

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

示例：D -> B -> E -> A -> C -> F

3. 后序遍历

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

示例：D -> E -> B -> F -> C -> A

下面分别用C、C#、C++三种语言实现二叉树的遍历。

三、C语言实现

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

typedef struct TreeNode {
    char data;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(char data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 前序遍历
void preorderTraversal(TreeNode* root) {
    if (root != NULL) {
        printf("%c ", root->data);
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root != NULL) {
        inorderTraversal(root->left);
        printf("%c ", root->data);
        inorderTraversal(root->right);
    }
}

// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root != NULL) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        printf("%c ", root->data);
    }
}

int main() {
    TreeNode* root = createNode('A');
    root->left = createNode('B');
    root->right = createNode('C');
    root->left->left = createNode('D');
    root->left->right = createNode('E');
    root->right->right = createNode('F');

    printf("前序遍历：");
    preorderTraversal(root);
    printf("\n");

    printf("中序遍历：");
    inorderTraversal(root);
    printf("\n");

    printf("后序遍历：");
    postorderTraversal(root);
    printf("\n");

    return 0;
}

四、C#语言实现

using System;

public class TreeNode {
    public char Data { get; set; }
    public TreeNode Left { get; set; }
    public TreeNode Right { get; set; }

    public TreeNode(char data) {
        Data = data;
        Left = null;
        Right = null;
    }
}

public class BinaryTree {
    public TreeNode Root { get; set; }

    public BinaryTree() {
        Root = null;
    }

    // 前序遍历
    public void PreorderTraversal(TreeNode root) {
        if (root != null) {
            Console.Write(root.Data + " ");
            PreorderTraversal(root.Left);
            PreorderTraversal(root.Right);
        }
    }

    // 中序遍历
    public void InorderTraversal(TreeNode root) {
        if (root != null) {
            InorderTraversal(root.Left);
            Console.Write(root.Data + " ");
            InorderTraversal(root.Right);
        }
    }
// 后序遍历
    public void PostorderTraversal(TreeNode root) {
        if (root != null) {
            PostorderTraversal(root.Left);
            PostorderTraversal(root.Right);
            Console.Write(root.Data + " ");
        }
    }

    public static void Main(string[] args) {
        BinaryTree tree = new BinaryTree();
        tree.Root = new TreeNode('A');
        tree.Root.Left = new TreeNode('B');
        tree.Root.Right = new TreeNode('C');
        tree.Root.Left.Left = new TreeNode('D');
        tree.Root.Left.Right = new TreeNode('E');
        tree.Root.Right.Right = new TreeNode('F');

        Console.WriteLine("前序遍历：");
        tree.PreorderTraversal(tree.Root);
        Console.WriteLine();

        Console.WriteLine("中序遍历：");
        tree.InorderTraversal(tree.Root);
        Console.WriteLine();

        Console.WriteLine("后序遍历：");
        tree.PostorderTraversal(tree.Root);
        Console.WriteLine();
    }
}

五、C++语言实现

#include <iostream>

struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;

    TreeNode(char x) : data(x), left(nullptr), right(nullptr) {}
};

// 前序遍历
void preorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        std::cout << root->data << " ";
        preorderTraversal(root->left);
        preorderTraversal(root->right);
    }
}

// 中序遍历
void inorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        inorderTraversal(root->left);
        std::cout << root->data << " ";
        inorderTraversal(root->right);
    }
}

// 后序遍历
void postorderTraversal(TreeNode* root) {
    if (root != nullptr) {
        postorderTraversal(root->left);
        postorderTraversal(root->right);
        std::cout << root->data << " ";
    }
}

int main() {
    TreeNode* root = new TreeNode('A');
    root->left = new TreeNode('B');
    root->right = new TreeNode('C');
    root->left->left = new TreeNode('D');
    root->left->right = new TreeNode('E');
    root->right->right = new TreeNode('F');

    std::cout << "前序遍历：";
    preorderTraversal(root);
    std::cout << std::endl;

    std::cout << "中序遍历：";
    inorderTraversal(root);
    std::cout << std::endl;

    std::cout << "后序遍历：";
    postorderTraversal(root);
    std::cout << std::endl;

    return 0;
}

总结

二叉树的遍历是深入理解和操作树形数据结构的基础。通过前序、中序和后序遍历，可以有效地访问并处理二叉树中的所有节点。在实际应用中，这些遍历方式具有各自的特点和应用场景，可以根据具体需求选择合适的遍历方式来操作二叉树数据。

通过本文提供的示例代码和解释，希望读者能够清晰地理解二叉树的结构和遍历方式，为编写高效的树操作算法打下坚实的基础。

原文地址：https://blog.csdn.net/qq_35320456/article/details/140499855

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

上一篇：基于asp.net小区物业信息管理系统设计与实现
下一篇：大白话讲解设计原则及其优缺点

leetcode289:生命游戏
根据，简称为，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。给定一个包含m × n个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态：1即为（live），或0即为
阅读更多2024-10-20
MongoDB数据恢复
注意：两个MongoDB的版本要一致，本文使用的是mongo:4.2.24。先把K8S上面的MongoDB 容器停止（可以把副本改成0）。1、将容器挂载MongoDB的数据目录备份到本地。经常是数据文
阅读更多2024-10-20
C#中实现事务
C#中实现事务
阅读更多2024-10-20
【LeetCode每日一题】——560.和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数。子数组是数组中元素的连续非空序列。
阅读更多2024-10-20
「漏洞复现」满客宝智慧食堂系统 selectUserByOrgId 未授权访问漏洞
请勿利用文章内的相关技术从事非法测试，由于传播、利用此文所提供的信息而造成的任何直接或者间接的后果及损失，均由使用者本人负责，作者不为此承担任何责任。工具来自网络，安全性自测，如有侵权请联系删除。本次
阅读更多2024-10-20
React面试题目（从基本到高级）
React前端面试常见题目涵盖了React的基础概念、组件、状态管理、生命周期、性能优化等多个方面。
阅读更多2024-10-20
12.个人博客系统（Java项目基于spring和vue）
1 在校学习的学生，可用于日常学习使用或是毕业设计使用 2 毕业一到两年的开发人员，用于锻炼自己的独立功能模块设计能力，增强代码编写能力。 3 亦可以部署为商化项目使用。 4 需要完整资料及源码
阅读更多2024-10-20
YoloV8改进策略：注意力改进|DeBiFormer，可变形双级路由注意力|引入DeBiLevelRoutingAttention注意力模块（全网首发）
本次改进的核心在于将DeBiLevelRoutingAttention模块嵌入到YoloV8的主干网络中，具体位置是在SPPF（Spatial Pyramid Pooling Fast）模块之后。这一
阅读更多2024-10-20
word取消自动单词首字母大写
情况说明：在word输入单词后首字母会自动变成大写取消单词首字母大写步骤：（1）点击菜单栏文件（2）点击“更多”——>“选项”（3）点击“校对”——>“自动更正选项”（4）取消“句首字母大
阅读更多2024-10-20
web前端网页用户注册页面
【代码】web前端网页用户注册页面。
阅读更多2024-10-20