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

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

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调用DeepSeek API的最佳实践及详细代码示例

《Java调用DeepSeekAPI的最佳实践及详细代码示例》:本文主要介绍如何使用Java调用DeepSeekAPI,包括获取API密钥、添加HTTP客户端依赖、创建HTTP请求、处理响应、... 目录1. 获取API密钥2. 添加HTTP客户端依赖3. 创建HTTP请求4. 处理响应5. 错误处理6.

Spring AI集成DeepSeek的详细步骤

《SpringAI集成DeepSeek的详细步骤》DeepSeek作为一款卓越的国产AI模型,越来越多的公司考虑在自己的应用中集成,对于Java应用来说,我们可以借助SpringAI集成DeepSe... 目录DeepSeek 介绍Spring AI 是什么?1、环境准备2、构建项目2.1、pom依赖2.2

Goland debug失效详细解决步骤(合集)

《Golanddebug失效详细解决步骤(合集)》今天用Goland开发时,打断点,以debug方式运行,发现程序并没有断住,程序跳过了断点,直接运行结束,网上搜寻了大量文章,最后得以解决,特此在这... 目录Bug:Goland debug失效详细解决步骤【合集】情况一:Go或Goland架构不对情况二:

Python中顺序结构和循环结构示例代码

《Python中顺序结构和循环结构示例代码》:本文主要介绍Python中的条件语句和循环语句,条件语句用于根据条件执行不同的代码块,循环语句用于重复执行一段代码,文章还详细说明了range函数的使... 目录一、条件语句(1)条件语句的定义(2)条件语句的语法(a)单分支 if(b)双分支 if-else(

Python itertools中accumulate函数用法及使用运用详细讲解

《Pythonitertools中accumulate函数用法及使用运用详细讲解》:本文主要介绍Python的itertools库中的accumulate函数,该函数可以计算累积和或通过指定函数... 目录1.1前言:1.2定义:1.3衍生用法:1.3Leetcode的实际运用:总结 1.1前言:本文将详

Deepseek R1模型本地化部署+API接口调用详细教程(释放AI生产力)

《DeepseekR1模型本地化部署+API接口调用详细教程(释放AI生产力)》本文介绍了本地部署DeepSeekR1模型和通过API调用将其集成到VSCode中的过程,作者详细步骤展示了如何下载和... 目录前言一、deepseek R1模型与chatGPT o1系列模型对比二、本地部署步骤1.安装oll

Spring Boot整合log4j2日志配置的详细教程

《SpringBoot整合log4j2日志配置的详细教程》:本文主要介绍SpringBoot项目中整合Log4j2日志框架的步骤和配置,包括常用日志框架的比较、配置参数介绍、Log4j2配置详解... 目录前言一、常用日志框架二、配置参数介绍1. 日志级别2. 输出形式3. 日志格式3.1 PatternL

Springboot 中使用Sentinel的详细步骤

《Springboot中使用Sentinel的详细步骤》文章介绍了如何在SpringBoot中使用Sentinel进行限流和熔断降级,首先添加依赖,配置Sentinel控制台地址,定义受保护的资源,... 目录步骤 1: 添加 Sentinel 依赖步骤 2: 配置 Sentinel步骤 3: 定义受保护的

使用Navicat工具比对两个数据库所有表结构的差异案例详解

《使用Navicat工具比对两个数据库所有表结构的差异案例详解》:本文主要介绍如何使用Navicat工具对比两个数据库test_old和test_new,并生成相应的DDLSQL语句,以便将te... 目录概要案例一、如图两个数据库test_old和test_new进行比较:二、开始比较总结概要公司存在多

本地私有化部署DeepSeek模型的详细教程

《本地私有化部署DeepSeek模型的详细教程》DeepSeek模型是一种强大的语言模型,本地私有化部署可以让用户在自己的环境中安全、高效地使用该模型,避免数据传输到外部带来的安全风险,同时也能根据自... 目录一、引言二、环境准备(一)硬件要求(二)软件要求(三)创建虚拟环境三、安装依赖库四、获取 Dee