首页 > 其他分享 >C ++ 从单链表到创建二叉树到二叉树的遍历(结构体)

C ++ 从单链表到创建二叉树到二叉树的遍历(结构体)

时间:2024-09-09 19:53:41浏览次数:11  
标签:right TreeNode ++ 表到 int 二叉树 new root left

首先我们要了解二叉树的数据结构是什么,本质上二叉树是一个有两个节点的链表,我们先了解的单链表的相关定义

单链表

创建一个朴素的单链表

#include <iostream>

using namespace std;

struct Node{
    int val;
    Node* next;

    Node(int x) : val(x), next(nullptr) {}
};

int main()
{
    return 0;
}
Node(int value) : data(value), next(nullptr) {}
  1. 构造函数定义: Node(int value) 是构造函数的声明,它接受一个 int 类型的参数 value

  2. 成员初始化列表: : data(value), next(nullptr) 是成员初始化列表,用于初始化类成员。

    • data(value) 将构造函数的参数 value 赋给 data 成员变量。
    • next(nullptr)next 指针初始化为 nullptr,表示该节点最初不指向任何其他节点。
  3. 空体: {} 表示构造函数的主体,这里是空的,因为所有初始化工作都在成员初始化列表中完成了。

简而言之,这个构造函数创建一个 Node 对象时,设置 data 为提供的 value 值,而 next 则默认指向空,表示没有下一个节点。

创建一颗二叉树

比如我想要创建一颗这样的二叉树

在结构体当中定义两个结点,并且初始化这棵树

#include <iostream>

using namespace std;

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

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 初始化
void init(TreeNode* root){
    root -> left = new TreeNode(2);
    root -> right = new TreeNode(3);
    root -> left -> left = new TreeNode(4);
    root -> left -> right = new TreeNode(5);
    root -> right -> left = new TreeNode(6);
    root -> right -> right = new TreeNode(7);
}

int main()
{
    // 初始化根节点是1
    TreeNode* root = new TreeNode(1); 

    init(root);

    return 0;
}

前序遍历、中序遍历、后序遍历

这里是利用了递归的思想,详细请看洛谷B3642 二叉树的遍历(前序、中序、后序)-CSDN博客

前序的代码如下,中序、后序就不展示了

#include <iostream>

using namespace std;

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

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 初始化
void init(TreeNode* root){
    root -> left = new TreeNode(2);
    root -> right = new TreeNode(3);
    root -> left -> left = new TreeNode(4);
    root -> left -> right = new TreeNode(5);
    root -> right -> left = new TreeNode(6);
    root -> right -> right = new TreeNode(7);
}

void dfs(TreeNode* root){
    if(root == nullptr) return;

    cout << root -> val << " ";
    dfs(root -> left);
    dfs(root -> right);
}

int main()
{
    // 初始化根节点是1
    TreeNode* root = new TreeNode(1); 

    init(root);

    dfs(root);

    return 0;
}

层次遍历

这里讲一下层次遍历以上面那棵树为例

首先要对队列很熟悉,层次遍历是每一层从左往右依此遍历,那么这棵树的层次遍历就是1234567

那就很明确了,从第一层开始,从左往右加入队列即可

#include <iostream>
#include <queue>

using namespace std;

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

    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

// 初始化
void init(TreeNode* root){
    root -> left = new TreeNode(2);
    root -> right = new TreeNode(3);
    root -> left -> left = new TreeNode(4);
    root -> left -> right = new TreeNode(5);
    root -> right -> left = new TreeNode(6);
    root -> right -> right = new TreeNode(7);
}

void bfs(TreeNode* root){
    queue<TreeNode*> q;
    q.push(root);

    while(!q.empty()){
        TreeNode* node = q.front();
        q.pop();

        cout << node -> val << " ";

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

int main()
{
    // 初始化根节点是1
    TreeNode* root = new TreeNode(1); 

    init(root);

    bfs(root);

    return 0;
}

加油

标签:right,TreeNode,++,表到,int,二叉树,new,root,left
From: https://blog.csdn.net/AuRoRamth/article/details/142066909

相关文章

  • 【C++基础概念理解——std::unique_ptr如何管理动态分配的对象的生命周期?】
    文章目录问题解释问题std::unique_ptr用于管理动态分配的对象的生命周期,那么这种智能指针怎么实现管理生命周期的呢?解释用于确保对象不再使用时自动释放,从而避免内存泄漏。std::unique_ptr独占管理对象的所有权,同一时间只能有一个std::unique_ptr指向该对象。确保......
  • C++: set与map容器的介绍与使用
    本文索引前言1.二叉搜索树1.1概念1.2二叉搜索树操作1.2.1查找与插入1.2.2删除1.2.3二叉搜索树实现代码2.树形结构的关联式容器2.1set的介绍与使用2.1.1set的构造函数2.1.2set的迭代器2.1.3set的容量2.1.4set的修改操作2.2map的介绍与使用2.2.1map的构造......
  • ubuntu 20.04安装GCC G++ 6.2,支持c++ 14
    1.下载源码包wgethttp://ftp.gnu.org/gnu/gcc/gcc-6.2.0/gcc-6.2.0.tar.bz22.解压tarjxfgcc-6.2.0.tar.bz23.下载编译依赖cdgcc-6.2.0./contrib/download_prerequisites4.生成makefile文件mkdirgcc-build-6.2.0cdgcc-build-6.2.0/../configure-......
  • C++创建与调用dll动态链接库(MinGW64 Dev-C++)
    本文使用的是dev-c++,如果涉及到VC++中不一样的操作,也会适当进行区分。项目一:创建DLL1、创建一个DLL类型的项目,当前命名为dlltest,并选择合适的路径进行保存。 2、在生成的预设置代码中,加入如下代码//这是头文件dll.h#ifndef_DLL_H_#define_DLL_H_#ifBUILDING......
  • Qt/C++ 音视频开发: 使用 mpv 进行录像存储
    Qt/C++音视频开发:使用mpv进行录像存储介绍在现代应用中,音视频处理与存储是非常常见的需求。mpv是一个开源的视频播放器,具有强大的功能,可以通过其API进行定制化开发。本文将详细介绍如何使用Qt/C++和mpv实现录像存储功能。应用使用场景视频监控系统:实时采集......
  • 【C++】C++ STL 探索:List使用与背后底层逻辑
    C++语法相关知识点可以通过点击以下链接进行学习一起加油!命名空间缺省参数与函数重载C++相关特性类和对象-上篇类和对象-中篇类和对象-下篇日期类C/C++内存管理模板初阶String使用String模拟实现Vector使用及其模拟实现本文将通过模拟实现List,从多个角度深入剖析其底层机......
  • C++ 多线程代码性能分析——Oracle Developer Studio工具教程
        最近写项目的时候,为了提升性能,把原来一些单线程的代码改成了并行运行。这里我用到的用于评估性能提升效果的工具是OracleDeveloperStudio,不过刚上手时,发现网上相关的教程和博客较少,有些功能的使用也是摸索着过来的,这一过程可谓是十分痛苦了……如今距离初次接触......
  • C++20 协程:异步编程的新纪元
    C++20引入了协程(coroutines),这是一种全新的异步编程模型,使得编写异步代码变得更加简洁和直观。本文将详细介绍C++20协程的概念、功能演变及其在实际项目中的应用。通过本文,你将了解到协程的基本原理、语法和如何利用协程来简化异步编程。1.协程的概念协程(coroutine)是......
  • C++---内存管理
    1C/C++内存分布栈区:由编译器自动分配和释放,存放运行时候的局部变量,函数参数,返回数据,返回地址。堆区:一般由程序员自己分配,然后自己释放,例如栈的实现malloc开辟的数组空间。数据段(静态区):存放全局变量,静态数据,常量,程序结束后自动释放。代码段(常量区):存放常量字符串和可执行代......
  • C++--static成员和友元
    1static声明为static的类成员称为类的静态成员,用static修饰的成员变量,称之为静态成员变量;用static修饰的成员函数,称之为静态成员函数。静态成员变量一定要在类外进行初始化静态定义的成员变量在类外定义,变量类型类名::变量名=value的形式。此外,static还可以在类里面定义......