【数据结构】二叉树的遍历

news/2025/3/16 9:44:46/

  Yan-英杰的主页

悟已往之不谏 知来者之可追  

C++程序员,2024届电子信息研究生


目录

前序、中序以及后序遍历

前序遍历

中序遍历

后序遍历


前序、中序以及后序遍历

        

        学习二叉树结构,最简单的方式就是遍历。所谓二叉树遍历 (Traversal) 是按照某种特定的规则,依次对二叉树中的节点进行相应的操作,并且每个节点只操作一次 。访问结点所做的操作依赖于具体的应用问题。 遍历 是二叉树上最重要的运算之一,也是二叉树上进行其它运算的基础。

按照规则,二叉树的遍历有: 前序 / 中序 / 后序的递归结构遍历
         1. 前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点的操作发生在遍历其左右子树之前。
        2. 中序遍历(Inorder Traversal)——访问根结点的操作发生在遍历其左右子树之中(间)。
        3. 后序遍历(Postorder Traversal)——访问根结点的操作发生在遍历其左右子树之后

        由于被访问的结点必是某子树的根,所以 N(Node )、 L(Left subtree )和 R(Right subtree )又可解释为根、根的左子树和根的右子树 NLR LNR LRN 分别又称为先根遍历、中根遍历和后根遍历。

        

// 二叉树前序遍历
void PreOrder(BTNode* root);
// 二叉树中序遍历
void InOrder(BTNode* root);
// 二叉树后序遍历
void PostOrder(BTNode* root);

 下面主要分析前序递归遍历,中序与后序图解类似,同学们可自己动手绘制。

前序遍历

         前序遍历递归图解:

        

        代码解析:

                

#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<assert.h>
#include<stdlib.h>typedef int BTDataType;typedef struct BinaryTreeNode
{BTDataType data;struct BinaryTreeNode* left;struct BinaryTreeNode* right;
}BTNode;BTNode* BuyNode(BTDataType x)
{BTNode* node = (BTNode*)malloc(sizeof(BTNode));if (node == NULL){perror("malloc fail");return;}node->data = x;node->left = NULL;node->right = NULL;return node;
}BTNode* CreatTree()
{BTNode* node1 = BuyNode(1);BTNode* node2 = BuyNode(2);BTNode* node3 = BuyNode(3);BTNode* node4 = BuyNode(4);BTNode* node5 = BuyNode(5);BTNode* node6 = BuyNode(6);BTNode* node7 = BuyNode(7);node1->left = node2;node1->right = node4;node2->left = node3;node2->right = NULL;node4->left = node5;node4->right = node6;return node1;
}//前序排列
void PreOrder(BTNode* root)
{if (root==NULL){printf("NULL ");return;}printf("%d ",root->data);PreOrder(root->left);PreOrder(root->right);
}int main()
{BTNode* root = CreatTree();PreOrder(root);printf("\n");return 0;
}

中序遍历

          中序遍历递归图解:

        代码解析:

        

void InOrder(BTNode* root) {if (root == NULL) {printf("NULL ");return;}InOrder(root->left);printf("%d ", root->data);InOrder(root->right);
}

后序遍历

        后序遍历递归图解:

        代码解析:

void PostOrder(BTNode* root)
{if (root == NULL){printf("NULL ");return;}PostOrder(root->left);PostOrder(root->right);printf("%d ", root->data);
}


http://www.ppmy.cn/news/53426.html

相关文章

ThingsBoard教程(三六):规则节点解析 检查关系节点 check relation,实体类型节点 entity type

前言 本篇文章和大家一起来学习两个节点,检查关系节点 check relation和实体类型节点 entity type。 check relation 检查消息的发起者与其他实体之间是否存在关系。如果选择了“check relation to specific entity(检查与特定实体的关系)”,则必须指定相关实体。否则,…

微服务---分布式事务Seata(XA,AT,TCC,SAGA模式基本使用)

分布式事务 1.分布式事务问题 1.1.本地事务 本地事务&#xff0c;也就是传统的单机事务。在传统数据库事务中&#xff0c;必须要满足四个原则&#xff1a; 1.2.分布式事务 分布式事务&#xff0c;就是指不是在单个服务或单个数据库架构下&#xff0c;产生的事务&#xff0c…

SqlSugar操作MySQL数据库

SqlSugar操作MySQL数据库 C#操作DataTable排序 在C#中&#xff0c;我们可以使用DataTable类来表示内存中的数据表格。DataTable类提供了各种方法和属性来操作数据表格&#xff0c;包括排序。 要对DataTable进行排序&#xff0c;可以使用DataView类。DataView类是一个用于筛选…

收废品小程序开发中的常见问题及解决方法

常见问题 1. 用户界面设计 小程序的用户界面设计至关重要。设计师需要在用户界面中提供清晰的指示&#xff0c;以便用户可以轻松地找到他们需要的功能。同时&#xff0c;设计师还需要确保用户界面的整体风格与公司的品牌形象相符。 2. 功能开发 开发小程序的功能需要考虑到…

如何掌握PMO核心技能和知识?

想成为PMO大神&#xff0c;但不知道该从哪里入手&#xff1f;别慌&#xff01;按照步骤&#xff0c;一级级往上跳&#xff0c;学习项目管理的核心技能和知识。 一、项目管理流程 1、熟悉和理解项目管理的基本原则、流程和方法。 2、确保项目计划符合业务目标和价值。 3、确…

day6 socket套接字及TCP的实现框架

socket套接字 Berkeley UNIX 操作系统定义了一种API它又称为套接字接口&#xff08;socket interface); socket作用&#xff1a; socket常见API介绍 /*创建套接字*/ int socket(int domain, int type, int protocol); /*绑定通信结构体*/ int bind(int sockfd, const, struc…

pod-debug初始化容器

pod-debug初始化容器 上文&#xff0c;我们已经学习了如何配置初始化镜像&#xff0c;那么本文将带大家学习如何Debug初始化容器。 ps: 本文使用<pod-name> 来指代Pod的名称&#xff0c;使用<init-container-1> 和 <init-container-2> 来指代初始化容器的名…

改进YOLOv8/YOLOv5系列:创新必备,助力涨点。原创魔改注意力,动态通道注意力模块DyCAConv,带改进描述

动态通道注意力模块DyCAConv 1. 背景三、YOLOv5改进代码及加入方法1.YOLO5中添加:注意力代码四、YOLOv8改进代码及加入方法1.注册YOLOv8yaml文件四、测试涨点!1. 背景 在深度学习领域,尤其是计算机视觉任务中,神经网络需要捕捉图像中的多尺度特征以实现有效的特征表征。为…