二叉树链式结构的前序_中序_后续_层序遍历【详细图解】

本文主要是介绍二叉树链式结构的前序_中序_后续_层序遍历【详细图解】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

P. S.:以下代码均在VS2019环境下测试,不代表所有编译器均可通过。
P. S.:测试代码均未展示头文件stdio.h的声明,使用时请自行添加。

  

在这里插入图片描述

                                           博主主页:LiUEEEEE
                                              C语言专栏
                                            数据结构专栏
                                         力扣牛客经典题目专栏

目录

  • 1、前言
  • 2、前序遍历
  • 3、中序遍历
  • 4、后序遍历
  • 5、层序遍历
  • 6、完整代码展示
  • 7、结语

1、前言


  有关二叉树链式结构的四种遍历方式,是基于二叉树由链式结构组成,故本文不再讲解如何实现二叉树的链式结构,以手搓链式结构的方式进行四种遍历方式的讲解。
  • 结点结构及相关定义展示:
typedef int TreeDataType;typedef struct TreeNode
{TreeDataType val;struct TreeNode* left;struct TreeNode* right;
}TNode;TNode* BuyNode(TreeDataType x);创建二叉树结点TNode* CreateTree();串连结点组成树
  • BuyNode
TNode* BuyNode(TreeDataType x)
{TNode* tmp = (TNode*)malloc(sizeof(TNode));if (tmp == NULL){perror("BuyNode: malloc fail");return NULL;}tmp->val = x;tmp->left = tmp->right = NULL;return tmp;
}
  • CreateTree
TNode* CreateTree()
{TNode* node1 = BuyNode(1);TNode* node2 = BuyNode(2);TNode* node3 = BuyNode(3);TNode* node4 = BuyNode(4);TNode* node5 = BuyNode(5);TNode* node6 = BuyNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}

  再此基础上我们所构建的书逻辑图如下所示:
在这里插入图片描述
PS.图中子树未连接部分均为NULL。




2、前序遍历


  遍历的命名规则为,以每一颗树的根为主要节点(整个树的根以及子树的根),以根出现的次序进行命名,下文中的中序后续皆可以此理解。
  前序遍历:遍历的顺序依次为:根,左子树,右子树。
  例如上文中我们手搓的二叉树,通过前序遍历的过程并打印的结果如下图所示:

在这里插入图片描述

  • 前序遍历代码实现
void PreOrder(TNode* root)
{if (root == NULL)return;printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}




3、中序遍历


  中序遍历:遍历的顺序依次为:左子树,根,右子树。
  例如上文中我们手搓的二叉树,通过中序遍历的过程并打印的结果如下图所示:

在这里插入图片描述

  • 中序遍历代码实现
void InOrder(TNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}




4、后序遍历


  后序遍历:遍历的顺序依次为:左子树,右子树,根。
  例如上文中我们手搓的二叉树,通过后序遍历的过程并打印的结果如下图所示:

在这里插入图片描述

  • 后序遍历代码实现
void PostOrder(TNode* root)
{if (root == NULL)return;PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}




5、层序遍历


  层序遍历是指按照层数从每层的最左侧向右依次打印二叉树的节点值,如下图所示:

在这里插入图片描述


  但我们实际中很难使用递归来操作,使得再打印完2时,通过结点1找到结点3的值打印,故我们需要借助其他工具进行实现,即队列。


  操作原则是,先将根结点1输入到队列中,在打印根结点1时,将结点1的左结点与右结点依次输入进队列,并将结点1从队列中删除,以此往复,直至在队列中遇见空结点。
  对此本文不再对队列相关的知识进行讲解,如有需要回看博文:

                     队列的实现(使用链表)


  逻辑思路如下图所示:

在这里插入图片描述

  • 层序遍历代码实现
void LevelOrder(TNode* root)
{Queue pq;QueueInit(&pq);if (root)QueuePush(&pq, root);while (!QueueEmpty(&pq)){TNode* front = QueueFront(&pq);QueuePop(&pq);printf("%d ", front->val);if (front->left)QueuePush(&pq, front->left);if (front->right)QueuePush(&pq, front->right);}QueueDestroy(&pq);
}
  • 四种遍历方式结果展示
    在这里插入图片描述




6、完整代码展示


   P,S.本章节所展示代码不包含队列代码,如有需求请自行添加。
  • Tree.h
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>typedef int TreeDataType;typedef struct TreeNode
{TreeDataType val;struct TreeNode* left;struct TreeNode* right;
}TNode;TNode* BuyNode(TreeDataType x);TNode* CreateTree();void PreOrder(TNode* root);void InOrder(TNode* root);void PostOrder(TNode* root);void LevelOrder(TNode* root);
  • Tree.c
#include "Tree.h"
#include "Queue.h"TNode* BuyNode(TreeDataType x)
{TNode* tmp = (TNode*)malloc(sizeof(TNode));if (tmp == NULL){perror("BuyNode: malloc fail");return NULL;}tmp->val = x;tmp->left = tmp->right = NULL;return tmp;
}TNode* CreateTree()
{TNode* node1 = BuyNode(1);TNode* node2 = BuyNode(2);TNode* node3 = BuyNode(3);TNode* node4 = BuyNode(4);TNode* node5 = BuyNode(5);TNode* node6 = BuyNode(6);node1->left = node2;node1->right = node3;node2->left = node4;node2->right = node5;node3->left = node6;return node1;
}void PreOrder(TNode* root)
{if (root == NULL)return;printf("%d ", root->val);PreOrder(root->left);PreOrder(root->right);
}void InOrder(TNode* root)
{if (root == NULL)return;InOrder(root->left);printf("%d ", root->val);InOrder(root->right);
}void PostOrder(TNode* root)
{if (root == NULL)return;PostOrder(root->left);PostOrder(root->right);printf("%d ", root->val);
}void LevelOrder(TNode* root)
{Queue pq;QueueInit(&pq);if (root)QueuePush(&pq, root);while (!QueueEmpty(&pq)){TNode* front = QueueFront(&pq);QueuePop(&pq);printf("%d ", front->val);if (front->left)QueuePush(&pq, front->left);if (front->right)QueuePush(&pq, front->right);}QueueDestroy(&pq);
}
  • TreeTest.c
#include "Tree.h"void test()
{TNode* root = CreateTree();printf("前序遍历结果:");PreOrder(root);printf("\n");printf("中序遍历结果:");InOrder(root);printf("\n");printf("后序遍历结果:");PostOrder(root);printf("\n");printf("层序遍历结果:");LevelOrder(root);printf("\n");
}int main()
{test();return 0;
}




7、结语


在这里插入图片描述

  十分感谢您观看我的原创文章。
  本文主要用于个人学习和知识分享,学习路漫漫,如有错误,感谢指正。
  如需引用,注明地址。

这篇关于二叉树链式结构的前序_中序_后续_层序遍历【详细图解】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1016438

相关文章

使用Java实现通用树形结构构建工具类

《使用Java实现通用树形结构构建工具类》这篇文章主要为大家详细介绍了如何使用Java实现通用树形结构构建工具类,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录完整代码一、设计思想与核心功能二、核心实现原理1. 数据结构准备阶段2. 循环依赖检测算法3. 树形结构构建4. 搜索子

利用Python开发Markdown表格结构转换为Excel工具

《利用Python开发Markdown表格结构转换为Excel工具》在数据管理和文档编写过程中,我们经常使用Markdown来记录表格数据,但它没有Excel使用方便,所以本文将使用Python编写一... 目录1.完整代码2. 项目概述3. 代码解析3.1 依赖库3.2 GUI 设计3.3 解析 Mark

通过Docker Compose部署MySQL的详细教程

《通过DockerCompose部署MySQL的详细教程》DockerCompose作为Docker官方的容器编排工具,为MySQL数据库部署带来了显著优势,下面小编就来为大家详细介绍一... 目录一、docker Compose 部署 mysql 的优势二、环境准备与基础配置2.1 项目目录结构2.2 基

Linux系统中配置静态IP地址的详细步骤

《Linux系统中配置静态IP地址的详细步骤》本文详细介绍了在Linux系统中配置静态IP地址的五个步骤,包括打开终端、编辑网络配置文件、配置IP地址、保存并重启网络服务,这对于系统管理员和新手都极具... 目录步骤一:打开终端步骤二:编辑网络配置文件步骤三:配置静态IP地址步骤四:保存并关闭文件步骤五:重

Centos环境下Tomcat虚拟主机配置详细教程

《Centos环境下Tomcat虚拟主机配置详细教程》这篇文章主要讲的是在CentOS系统上,如何一步步配置Tomcat的虚拟主机,内容很简单,从目录准备到配置文件修改,再到重启和测试,手把手带你搞定... 目录1. 准备虚拟主机的目录和内容创建目录添加测试文件2. 修改 Tomcat 的 server.X

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

Spring Boot拦截器Interceptor与过滤器Filter详细教程(示例详解)

《SpringBoot拦截器Interceptor与过滤器Filter详细教程(示例详解)》本文详细介绍了SpringBoot中的拦截器(Interceptor)和过滤器(Filter),包括它们的... 目录Spring Boot拦截器(Interceptor)与过滤器(Filter)详细教程1. 概述1

使用Dify访问mysql数据库详细代码示例

《使用Dify访问mysql数据库详细代码示例》:本文主要介绍使用Dify访问mysql数据库的相关资料,并详细讲解了如何在本地搭建数据库访问服务,使用ngrok暴露到公网,并创建知识库、数据库访... 1、在本地搭建数据库访问的服务,并使用ngrok暴露到公网。#sql_tools.pyfrom

java导出pdf文件的详细实现方法

《java导出pdf文件的详细实现方法》:本文主要介绍java导出pdf文件的详细实现方法,包括制作模板、获取中文字体文件、实现后端服务以及前端发起请求并生成下载链接,需要的朋友可以参考下... 目录使用注意点包含内容1、制作pdf模板2、获取pdf导出中文需要的文件3、实现4、前端发起请求并生成下载链接使

IDEA连接达梦数据库的详细配置指南

《IDEA连接达梦数据库的详细配置指南》达梦数据库(DMDatabase)作为国产关系型数据库的代表,广泛应用于企业级系统开发,本文将详细介绍如何在IntelliJIDEA中配置并连接达梦数据库,助力... 目录准备工作1. 下载达梦JDBC驱动配置步骤1. 将驱动添加到IDEA2. 创建数据库连接连接参数