【数据结构】二叉树的创建和遍历:前序遍历,中序遍历,后序遍历,层次遍历

目录

一、二叉树的定义

1、二叉树的定义

2、二叉树的五种形态 

 二叉树的子树 :

3、满二叉树与完全二叉树 

4、二叉树的性质 

5、二叉树的存储结构

1、顺序存储

​编辑

2、链式存储

 二、二叉树的遍历

按照前序序列构建二叉树

1、前 (先) 序遍历(Preorder Traversal )

前序遍历动态过程图:  

 下面是前序遍历的递归图解:

前序遍历代码及注释 :

2. 中序遍历(Inorder Traversal) 

中序遍历动态过程图: 

中序遍历代码及注释: 

3. 后序遍历(Postorder Traversal)

后序遍历动态过程图:  

后序遍历代码及注释: 

4、层序遍历 

层序遍历代码及注释: 


一、二叉树的定义

1、二叉树的定义

二叉树(Binary Tree)是有n(n≥0)个结点的有限集合:
(1)  该集合或者为空(n=0);
(2)或者由一个根结点及两个不相交的分别称为左子树和右子树组成的非空树;
(3)左子树和右子树同样又都是二叉树。
在一棵非空的二叉树中,每个结点至多只有两棵子树,分别称为左子树和右子树,且左右子树的次序不能任意交换。所以,二叉树是特殊的有序树。值得注意的是,由于二叉树上任结点的子树有左、右之分,因此即使一个结点只有一棵非空子树,仍须区别它是该结点的左子树还是右子树,这是与树不同的。


2、二叉树的五种形态 

 二叉树的子树 :

        在二叉树中,一个子树是指由二叉树中的某个节点及其后代节点组成的树。换句话说,对于一个给定的二叉树,可以选择其中的一个节点作为子树的根节点,并且包含该节点的所有后代节点,形成一个新的子树。

具体定义如下:
        在一个二叉树中,每个节点最多只有两个子节点,分别为左子节点和右子节点。对于任意一个节点,在它的左子节点和右子节点上又可以分别构成两个独立的子树,这样就形成了一个递归的结构。


3、满二叉树与完全二叉树 

1. 满二叉树:一个二叉树,如果每一个层的结点数都达到最大值,则这个二叉树就是满二叉树。也就是说,如果一个二叉树的层数为K,且结点总数是 ,则它就是满二叉树。                                     
2. 完全二叉树:完全二叉树是效率很高的数据结构,完全二叉树是由满二叉树而引出来的。对于深度为K的,有n个结点的二叉树,当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。特点:树高为h时,前h-1层节点为满。 要注意的是满二叉树是一种特殊的完全二叉树


4、二叉树的性质 

  1. 若规定根节点的层数为1,则一棵非空二叉树的第i层上最多有2^(i-1)个结点。
  2. 若规定根节点的层数为1,则深度为h的二叉树的最大结点数是2^h-1。
  3. 对任何一棵二叉树, 如果度为0的叶结点个数为n0,度为2的分支结点个数为n2,则有 n0 = n2 + 1。
  4. 若规定根节点的层数为1,具有n个结点的满二叉树的深度h= log2(n+1)。(这里的log是以2为底的对数)
  5. 对于具有n个结点的完全二叉树,如果按照从上至下从左至右的数组顺序对所有节点从0开始编号,则对于序号为i的结点有:
    a. 若i > 0,i位置节点的双亲序号为(i-1)/2,若i = 0,则i为根节点编号,无双亲节点。
    b. 若2i+1 < n,左孩子序号为2i+1,若2i+1 >= n,则无左孩子。
    c. 若2i+2 < n,右孩子序号为2i+2,若2i+2 >= n,则无右孩子。

5、二叉树的存储结构

二叉树一般可以使用两种结构存储,一种顺序结构,一种链式结构。

1、顺序存储

顺序结构存储就是使用数组来存储,一般使用数组只适合表示完全二叉树,因为不是完全二叉树会有空间的浪费。而现实中使用中只有堆才会使用数组来存储,关于堆我们后面的博客会专门讲解。二叉树顺序存储在物理上是一个数组,在逻辑上是一颗二叉树。


2、链式存储

 二叉树的链式存储结构是指,用链表来表示一棵二叉树,即用链来指示元素的逻辑关系。 通常的方法是链表中每个结点由三个域组成,数据域和左右指针域,左右指针分别用来给出该结点左孩子和右孩子所在的链结点的存储地址 。链式结构又分为二叉链和三叉链,本节内容我们主要讲解二叉链式存储结构。

链式二叉树结点定义如下:

typedef char BTDataType; // 使用typedef关键字给char类型取了一个别名BTDataType

typedef struct BTNode // 使用struct关键字定义了一个名为BTNode的结构体
{
    BTDataType data;        // 二叉树节点的数据域,用于存储具体的数据值
    struct BTNode* left;    // 二叉树节点的左子节点指针,指向左子节点
    struct BTNode* right;   // 二叉树节点的右子节点指针,指向右子节点
} BTNode;   // 使用BTNode作为该结构体类型的别名


 二、二叉树的遍历

按照前序序列构建二叉树

在对二叉树进行遍历之前我们先对通过前序遍历的数组"ABD##E#H##CF##G##"构建一颗二叉树。注意:'#' 字符代表该节点为空。

// 前序建立二叉树的函数
BTNode* CreateBinaryTreePre(BTDataType* a, int n, int* pi)
{
    // 如果数组索引超出数组长度,返回空指针
    if (*pi >= n)
    {
        return NULL;
    }
    
    // 如果当前位置的值为 '#',表示当前位置为空节点,将数组索引向后移动,并返回空指针
    if (a[*pi] == '#')
    {
        (*pi)++;
        return NULL;
    }
    
    // 动态分配一个新的二叉树节点
    BTNode* root = (BTNode*)malloc(sizeof(BTNode));
    
    // 如果内存分配成功
    if (root)
    {
        // 将当前位置的值存储到新节点的数据域中
        root->data = a[(*pi)++];
        
        // 递归调用CreateBinaryTreePre函数,构建新节点的左子树
        root->left = CreateBinaryTreePre(a, n, pi);
        
        // 递归调用CreateBinaryTreePre函数,构建新节点的右子树
        root->right = CreateBinaryTreePre(a, n, pi);
    }
    else
    {
        // 如果内存分配失败,打印错误信息并退出程序
        perror("malloc fail!");
        exit(-1);
    }
    
    return root;  // 返回根节点
}

// 主函数
int main()
{
    BTNode* root;   // 定义二叉树的根节点指针
    BTDataType a[] = { 'A','B','D','#','#',
                      'E','#','H','#','#','C','F','#','#','G','#','#' ,'\0' };
    int n = strlen(a);
    int pi = 0;   // 定义一个变量用于追踪数组的索引位置
    
    // 调用CreateBinaryTreePre函数,传入数组a、数组长度n和索引位置的指针pi,
    //生成二叉树,并返回根节点指针
    root = CreateBinaryTreePre(a, n, &pi);
    
    return 0;
}

1、前 (先) 序遍历(Preorder Traversal )

 访问根结点的操作发生在遍历其左右子树之前——即: 根节点 -> 左子树 -> 右子树。

     前序遍历二叉树的算法可以按照如下的步骤实现:

  1. 如果二叉树为空,直接返回。
  2. 访问当前节点,即输出当前节点的值。
  3. 对当前节点的左子树进行前序遍历。
  4. 对当前节点的右子树进行前序遍历。

我们如何理解遍历顺序呢?博主在这里分享一下自己的方法:

        对于一棵二叉树,我们先找到其根节点,打印出根结点的值后,我们对其左子树进行遍历。由于一颗二叉树可以划分出许多子树,那么遍历左子树时我们即可将当前节点(即根结点的左孩子结点)看作左子树的根结点,然后对当前子树再进行根节点 -> 左子树 -> 右子树 的遍历方法,如果当前结点为空,返回上一层递归。在当前根节点的左子树遍历完成时我们再对右子树进行遍历,如此循环往复,直至遍历完整棵树停止。

        简而言之,就是当遍历到一个新结点时,把当前结点当作根节点,接着去遍历当前结点的左右子树。进入下一个子树遍历时,继续把当前结点当作根节点,如此循环往复下去,直至遇到空结点,递归开始回溯。


前序遍历动态过程图:  


 下面是前序遍历的递归图解:


前序遍历代码及注释 :
// 前序遍历二叉树
void PrintPreOrder(BTNode* root)
{
    // 如果当前节点为空,返回
    if (!root)
    {
        return;
    }
    
    // 打印当前节点的值
    printf("%c ", root->data);
    
    // 递归遍历左子树
    PrintPreOrder(root->left);
    
    // 递归遍历右子树
    PrintPreOrder(root->right);
}

2. 中序遍历(Inorder Traversal) 

访问根结点的操作发生在遍历其左右子树之中(间)——即: 左子树 --> 根节点 --> 右子树。

中序遍历二叉树的算法可以按照如下步骤实现:

  1. 如果二叉树为空,直接返回。
  2. 对当前节点的左子树进行中序遍历。
  3. 访问当前节点,即输出当前节点的值。
  4. 对当前节点的右子树进行中序遍历。

 对于中序遍历,我们采取类似的方法。当我们遍历时,将当前结点当作子树的根节点,先去寻找该根节点有没有左孩子,如果有,我们就向左进行遍历,当到达新结点时,我们依旧将其看作根节点去寻找该结点的左孩子,如果当前结点为空,再回溯到其父结点打印数据,再去寻找它的右孩子。当当前子树遍历完成时,我们回溯到此子树根节点的上一层的节点,打印节点数据之后再去找该结点的右孩子。如此循环往复,直至遍历完整棵树停止。


中序遍历动态过程图: 


中序遍历代码及注释: 
// 中序遍历
void PrintInOrder(BTNode* root)
{
    // 如果当前节点为空,即已经到达叶子节点或者是空树的情况,直接返回
    if (!root)
    {
        return;
    }
  
    // 递归调用中序遍历函数,遍历左子树
    PrintInOrder(root->left);
  
    // 打印当前节点的数据
    printf("%c ", root->data);
  
    // 递归调用中序遍历函数,遍历右子树
    PrintInOrder(root->right);
}

3. 后序遍历(Postorder Traversal)

访问根结点的操作发生在遍历其左右子树之后——即: 左子树 -->右子树 --> 根节点 。

后序遍历二叉树的算法可以按照如下的步骤实现:

  1. 如果二叉树为空,直接返回。
  2. 对当前节点的左子树进行后序遍历。
  3. 对当前节点的右子树进行后序遍历。
  4. 访问当前节点,即输出当前节点的值。

 对于后序遍历,我们依然按照之前的方法。当我们遍历时,将当前结点当作子树的根节点,先去寻找该根节点有没有左孩子,如果有,我们就向左进行遍历,直至树的底部;如果当前结点为空,返回上一层递归,再去判断当前节点有没有右孩子,如果有我们再向右遍历,重复上面的过程。当当前子树左右孩子遍历完后,我们回退至子树的根结点打印数据。如此循环往复,直至遍历完整棵树停止。


后序遍历动态过程图:  


后序遍历代码及注释: 
// 后序遍历
void PrintPostOrder(BTNode* root)
{
    // 如果当前节点为空,直接返回
    if (!root)
    {
        return;
    }
  
    // 递归调用后序遍历函数,遍历左子树
    PrintPostOrder(root->left);
  
    // 递归调用后序遍历函数,遍历右子树
    PrintPostOrder(root->right);
  
    // 打印当前节点的数据
    printf("%c ", root->data);
}

4、层序遍历 

层序遍历是二叉树中最常用的遍历方法之一,它依次按层遍历二叉树中的结点。

具体实现思路如下:

  1. 创建一个队列,将根节点插入队列中。
  2. 取出队列的首个节点,访问该节点。
  3. 若该节点有左子节点,将左子节点插入队列中。
  4. 若该节点有右子节点,将右子节点插入队列中。
  5. 重复步骤 2 ~ 4,直到队列为空为止。


层序遍历代码及注释: 
typedef char BTDataType;  // 二叉树中每个节点所存储的数据类型为 char

typedef struct BTNode
{
	BTDataType data;  // 节点存储的数据
	struct BTNode* left;  // 左子节点
	struct BTNode* right;  // 右子节点
}BTNode;  // 定义二叉树结构体

typedef BTNode* QueueDataType;  // 队列中每个节点所存储的数据类型为 BTNode 指针

typedef struct QNode
{
	QueueDataType val;  // 节点存储的数据
	struct QNode* next;  // 指向下一个节点的指针
}QNode;  // 定义队列节点结构体

typedef struct Queue
{
	QNode* front;  // 队头指针
	QNode* rear;  // 队尾指针
	int size;  // 队列中元素的个数
}Queue;  // 定义队列结构体

// 初始化队列
void QueueInit(Queue* q)
{
    assert(q);
    q->front = NULL;
    q->rear = NULL;
    q->size = 0;
}

// 入队
void QueuePush(Queue* q, QueueDataType x)
{
    assert(q);
    QNode* temp = (QNode*)malloc(sizeof(QNode));
    if (temp == NULL)
    {
        perror("malloc fail!");
        exit(-1);
    }
    temp->val = x;
    temp->next = NULL;
    if (q->front == NULL)
    {
        q->front = q->rear = temp;  // 队列为空时,新元素既是队头也是队尾
    }
    else
    {
        q->rear->next = temp;  // 把新元素连接到队尾后
        q->rear = temp;  // 更新队尾指针为新的元素
    }
    q->size++;  // 队列元素个数加1
}

// 判断队列是否为空
bool QueueEmpty(Queue* q)
{
    assert(q);
    if (q->front == NULL)
    {
        return true;  // 队列为空
    }
    return false;  // 队列不为空
}

// 获取队头元素
QueueDataType QueueTop(Queue* q)
{
    assert(q);
    if (!QueueEmpty(q))
    {
        return q->front->val;  // 返回队头元素的值
    }
    else
    {
        printf("队空,无法获取队头元素!\n");
        exit(-1);
    }
}

// 出队
void QueuePop(Queue* q)
{
    assert(q);
    if (!QueueEmpty(q))
    {
        QNode* temp = q->front;  // 保存队头指针
        q->front = q->front->next;  // 移动队头指针到下一个元素
        free(temp);  // 释放原队头节点的内存空间
        q->size--;  // 队列元素个数减1
    }
    else
    {
        printf("队空,无法删除队头元素!\n");
        exit(-1);
    }
}

// 获取队列元素个数
int QueueSize(Queue* q)
{
    assert(q);
    return q->size;  // 返回队列元素个数
}

// 二叉树的层序遍历
void BinaryTreeLevelOrder(BTNode* root)
{
    assert(root);
    Queue q;
    QueueInit(&q);  // 初始化队列
    QueuePush(&q, root);  // 将根节点入队
    int TSize = 1;
    while (!QueueEmpty(&q))
    {
        // 遍历当前层级的结点
        while (TSize > 0)
        {
            BTNode* cur = QueueTop(&q);  // 获取队头元素
            QueuePop(&q);  // 出队
            printf("%c ", cur->data);  // 输出当前结点的数据
            if (cur->left)
            {
                QueuePush(&q, cur->left);  // 左子节点入队
            }
            if (cur->right)
            {
                QueuePush(&q, cur->right);  // 右子节点入队
            }
            TSize--;  // 减少当前层级元素个数
        }
        printf("\n");  // 输出换行符表示当前层级遍历结束
        TSize = QueueSize(&q);  // 更新当前层级元素个数
    }
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/290112.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

使用Python和Pygame库创建简单的的彩球效果

简介 Pygame是一款强大的游戏开发库&#xff0c;可以用于创建各种有趣的图形效果。为了更好地了解Pygame的功能&#xff0c;今天我们将要做的是在屏幕上随机生成一些彩色的小球&#xff0c;并使它们以不同的速度和方向移动。当小球碰到屏幕边缘时&#xff0c;它们将反弹。 功能…

为什么会去华为 OD?网传的 OD 转华为正编,真的假的?

目录 专栏导读一、为什么会去华为 OD二、华为 OD 的工作内容三、OD 与华为自有员工的对比四、那&#xff0c;到底要不要去华为 OD&#xff1f;五、网传的 OD 转华为正编&#xff0c;真的假的&#xff1f;1、连续两次绩效 A2、通过可信专业级认证 六、最后&#xff0c;真的感谢 …

GitHub上的15000个Go模块存储库易受劫持攻击

内容概要&#xff1a; 目前研究发现&#xff0c;GitHub上超过15000个Go模块存储库容易受到一种名为“重新劫持”的攻击。 由于GitHub用户名的更改会造成9000多个存储库容易被重新劫持&#xff0c;同时因为帐户删除&#xff0c;会对6000多个存储库造成重新劫持的危机。目前统计…

CentOS 7 实战指南:文件或目录的权限操作命令详解

前言 这篇文章详细介绍了文件和目录的常用权限操作命令&#xff0c;并提供了全面的技术解析。通过本文&#xff0c;你将学习如何使用 chmod 和 chown 命令来管理文件和目录的权限&#xff0c;控制用户和用户组的访问权限。无论你是初学者还是有经验的系统管理员&#xff0c;这…

代码随想录刷题笔记(DAY 8)

今日总结&#xff1a;最后一道题解决的比较糟糕&#xff0c;后续会补上新解法&#xff0c;今天还是将中心放在了前端。 Day 8 01. 反转字符串&#xff08;No. 344&#xff09; 题目链接 代码随想录题解 1.1 题目 编写一个函数&#xff0c;其作用是将输入的字符串反转过来。…

如何解决大模型的「幻觉」问题?

欢迎关注博主 Mindtechnist 或加入【智能科技社区】一起学习和分享Linux、C、C、Python、Matlab&#xff0c;机器人运动控制、多机器人协作&#xff0c;智能优化算法&#xff0c;贝叶斯滤波与Kalman估计、多传感器信息融合&#xff0c;机器学习&#xff0c;人工智能&#xff0c…

【12】ES6:模块化

一、JavaScript 模块化 JavaScript 模块化是一种组织和管理 JavaScript 代码的方法&#xff0c;它将代码分割为独立的模块&#xff0c;每个模块都有自己的作用域&#xff0c;并且可以导出和导入功能。模块化可以提高代码的可维护性、可重用性和可扩展性。 在JavaScript中&…

FCN学习-----第一课

语义分割中的全卷积网络 CVPR IEEE国际计算机视觉与模式识别会议 PAMI IEEE模式分析与机器智能汇刊 需要会的知识点&#xff1a; 神经网络&#xff1a;前向传播和反向传播 卷积神经网络&#xff1a;CNN&#xff0c;卷积&#xff0c;池化&#xff0c;上采样 分类网络&#xff1a…

CCF模拟题 202312-1 仓库规划

问题描述 试题编号&#xff1a; 202312-1 试题名称&#xff1a; 仓库规划 时间限制&#xff1a; 1.0s 内存限制&#xff1a; 512.0MB 问题描述&#xff1a; 输入格式 输出格式 样例输入 4 2 0 0 -1 -1 1 2 0 -1样例输出 3 1 0 3样例解释 Java实现代码&#xff1a; import …

Spring高手之路-Spring Bean、Java Bean和对象的区别与联系

目录 什么是Spring Bean 什么是Java Bean 什么是对象 Spring Bean与Java Bean与对象的联系与区别 联系 区别 什么是Spring Bean 在Spring官方文档中对Bean的解释如下&#xff1a; In Spring, the objects that form the backbone of your application and that are manage…

贪吃蛇C语言实现(有源码)

前言 之前学了一点easyx图形库的使用&#xff0c;掌握一些基本用法后就用贪吃蛇来进行实战了&#xff0c;运行视频放在csdn视频那一栏了&#xff0c;之前的烟花也是。 1.头文件 #define _CRT_SECURE_NO_WARNINGS 1 #include<easyx.h> #include<conio.h> #includ…

odoo17 | 基本视图

前言 我们在上一章中已经看到Odoo能够为给定模型生成默认视图。在实践中&#xff0c;默认视图是绝对不可接受的用于商业应用程序。相反&#xff0c;我们至少应该以逻辑方式组织各种字段。 视图在带有动作和菜单的XML文件中定义。它们是ir.ui.view模型的实例。 在我们的房地产…

YOLO+SlowFast+DeepSORT 简单实现视频行为识别

前段时间刷短视频看到过别人用摄像头自动化监控员工上班状态&#xff0c;比如标注员工是不是离开了工位&#xff0c;在位置上是不是摸鱼。虽然是段子&#xff0c;但是这个是可以用识别技术实现一下&#xff0c;于是我在网上找&#xff0c;知道发现了 SlowFast&#xff0c;那么下…

Sharding-JDBC快速使用【笔记】

1 引言 最近在使用Sharding-JDBC实现项目中数据分片、读写分离需求&#xff0c;参考官方文档&#xff08;Sharding官方文档&#xff09;感觉内容庞杂不够有条理&#xff0c;重复内容比较多&#xff1b;现结合项目应用整理笔记如下供大家参考和自己回忆使用&#xff1b; 在…

苹果手机数据删除怎么恢复?这几个方法值得一试!

不小心删除了iPhone里的照片&#xff1f;别担心&#xff0c;数据恢复是有可能的&#xff01; 从这里&#xff0c;你可以找到你的备份并恢复丢失的数据。如果你没有备份&#xff0c;那么数据恢复软件可能可以帮助你。它们可以扫描你的iPhone或iTunes备份&#xff0c;找到你删除…

打字练习(Python代码模拟打字练习软件效果)

Python代码模拟打字练习软件效果&#xff0c;循环进行单行打字练习&#xff0c;结束时输出平均速度和综合正确率。 (笔记模板由python脚本于2024年01月03日 22:36:34创建&#xff0c;本篇笔记适合熟悉Python字符串和列表基本数据类型的coder翻阅) 【学习的细节是欢悦的历程】 P…

如何利用Oracle官方网站不登录账号下载和安装非最新版本的JDK(版本自由选择)

一、JDK概述 JDK&#xff08;Java Development Kit&#xff09;是Java开发工具集&#xff0c;是针对Java编程语言的软件开发环境。它包含了Java编译器、JRE&#xff08;Java运行时环境&#xff09;以及其他一些用于开发、调试和测试Java应用程序的工具&#xff0c;是Java开发人…

通用Mapper怎么开接口扫描

作者简介&#xff1a;大家好&#xff0c;我是smart哥&#xff0c;前中兴通讯、美团架构师&#xff0c;现某互联网公司CTO 联系qq&#xff1a;184480602&#xff0c;加我进群&#xff0c;大家一起学习&#xff0c;一起进步&#xff0c;一起对抗互联网寒冬 学习必须往深处挖&…

三维模型数据的几何坐标变换的点云重建并行计算技术方法分析

三维模型数据的几何坐标变换的点云重建并行计算技术方法分析 倾斜摄影三维模型数据的几何坐标变换与点云重建并行计算技术的探讨主要涉及以下几个方面&#xff1a; 1、坐标系定义与转换&#xff1a;在进行坐标变换前&#xff0c;需要确定各个参考系的定义并实现坐标系之间的转…

[Angular] 笔记 15:模板驱动表单 - 表单验证

油管视频&#xff1a; Form Validation 有三种类型的验证&#xff1a; valid, pristine(是否被编辑过&#xff0c;被改过)&#xff0c;以及 touched 相反的属性&#xff1a; invalid, dirty, untouched pokemon-template-form.component.html 代码修改&#xff1a; 任何时候…