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

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

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

相关文章

如何为Yarn配置国内源的详细教程

《如何为Yarn配置国内源的详细教程》在使用Yarn进行项目开发时,由于网络原因,直接使用官方源可能会导致下载速度慢或连接失败,配置国内源可以显著提高包的下载速度和稳定性,本文将详细介绍如何为Yarn... 目录一、查询当前使用的镜像源二、设置国内源1. 设置为淘宝镜像源2. 设置为其他国内源三、还原为官方

最详细安装 PostgreSQL方法及常见问题解决

《最详细安装PostgreSQL方法及常见问题解决》:本文主要介绍最详细安装PostgreSQL方法及常见问题解决,介绍了在Windows系统上安装PostgreSQL及Linux系统上安装Po... 目录一、在 Windows 系统上安装 PostgreSQL1. 下载 PostgreSQL 安装包2.

MySql match against工具详细用法

《MySqlmatchagainst工具详细用法》在MySQL中,MATCH……AGAINST是全文索引(Full-Textindex)的查询语法,它允许你对文本进行高效的全文搜素,支持自然语言搜... 目录一、全文索引的基本概念二、创建全文索引三、自然语言搜索四、布尔搜索五、相关性排序六、全文索引的限制七

python中各种常见文件的读写操作与类型转换详细指南

《python中各种常见文件的读写操作与类型转换详细指南》这篇文章主要为大家详细介绍了python中各种常见文件(txt,xls,csv,sql,二进制文件)的读写操作与类型转换,感兴趣的小伙伴可以跟... 目录1.文件txt读写标准用法1.1写入文件1.2读取文件2. 二进制文件读取3. 大文件读取3.1

Linux内核参数配置与验证详细指南

《Linux内核参数配置与验证详细指南》在Linux系统运维和性能优化中,内核参数(sysctl)的配置至关重要,本文主要来聊聊如何配置与验证这些Linux内核参数,希望对大家有一定的帮助... 目录1. 引言2. 内核参数的作用3. 如何设置内核参数3.1 临时设置(重启失效)3.2 永久设置(重启仍生效

如何在Mac上安装并配置JDK环境变量详细步骤

《如何在Mac上安装并配置JDK环境变量详细步骤》:本文主要介绍如何在Mac上安装并配置JDK环境变量详细步骤,包括下载JDK、安装JDK、配置环境变量、验证JDK配置以及可选地设置PowerSh... 目录步骤 1:下载JDK步骤 2:安装JDK步骤 3:配置环境变量1. 编辑~/.zshrc(对于zsh

使用Node.js制作图片上传服务的详细教程

《使用Node.js制作图片上传服务的详细教程》在现代Web应用开发中,图片上传是一项常见且重要的功能,借助Node.js强大的生态系统,我们可以轻松搭建高效的图片上传服务,本文将深入探讨如何使用No... 目录准备工作搭建 Express 服务器配置 multer 进行图片上传处理图片上传请求完整代码示例

C++ vector的常见用法超详细讲解

《C++vector的常见用法超详细讲解》:本文主要介绍C++vector的常见用法,包括C++中vector容器的定义、初始化方法、访问元素、常用函数及其时间复杂度,通过代码介绍的非常详细,... 目录1、vector的定义2、vector常用初始化方法1、使编程用花括号直接赋值2、使用圆括号赋值3、ve

python连接本地SQL server详细图文教程

《python连接本地SQLserver详细图文教程》在数据分析领域,经常需要从数据库中获取数据进行分析和处理,下面:本文主要介绍python连接本地SQLserver的相关资料,文中通过代码... 目录一.设置本地账号1.新建用户2.开启双重验证3,开启TCP/IP本地服务二js.python连接实例1.

Nginx中配置HTTP/2协议的详细指南

《Nginx中配置HTTP/2协议的详细指南》HTTP/2是HTTP协议的下一代版本,旨在提高性能、减少延迟并优化现代网络环境中的通信效率,本文将为大家介绍Nginx配置HTTP/2协议想详细步骤,需... 目录一、HTTP/2 协议概述1.HTTP/22. HTTP/2 的核心特性3. HTTP/2 的优