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

这篇具有很好参考价值的文章主要介绍了【数据结构】二叉树的遍历。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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

  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;
}

中序遍历

          中序遍历递归图解:

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

        代码解析:文章来源地址https://www.toymoban.com/news/detail-422385.html

        

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);
}

到了这里,关于【数据结构】二叉树的遍历的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构与算法-二叉树的遍历

    🌞 “少年没有乌托邦,心向远方自明朗!” 二叉树的遍历是按照一定次序访问二叉树中的所有结点,且每个结点仅被访问一次的过程。遍历线性结构是容易解决的,而二叉树的结构是非线性结构,需要寻找规律,使二叉树的结点排列在一个线性队列上,便于遍历。 由二叉树

    2024年02月08日
    浏览(46)
  • 数据结构——二叉树的遍历与应用

    目录 一.前言 二. 二叉树链式结构的实现 2.1 前置说明 2.2 二叉树的遍历 2.2.1 前序、中序以及后序遍历 前序遍历: 中序遍历递归图: 后序遍历: 2.3节点个数 2.4叶子节点个数 2.5第K层的节点个数 2.6 二叉树查找值为x的节点 2.7 二叉树的销毁 三.结语   大家好久不见,放寒假了咱

    2024年01月19日
    浏览(47)
  • 【数据结构】二叉树的层序遍历

    当我们面对一个树结构时,常常需要对其进行遍历以获取其中的节点信息。其中一种常用的遍历方式是层序遍历,也称为广度优先搜索(BFS)。本篇博客将详细介绍层序遍历的原理和实现方法。 层序遍历以树的根节点开始,按照从上到下、从左到右的顺序逐层遍历树中的节点

    2024年02月03日
    浏览(45)
  • 数据结构——二叉树的创建与遍历(链式存储结构)

    二叉树(binary tree)是指树中节点的度不大于2的有序树,它是一种最简单且最重要的树。二叉树的递归定义为:二叉树是一棵空树,或者是一棵由一个根节点和两棵互不相交的,分别称作根的左子树和右子树组成的非空树;左子树和右子树又同样都是二叉树。以下是对链式存

    2024年02月05日
    浏览(51)
  • 【C语言 数据结构】二叉树的遍历

    所谓先序遍历二叉树,指的是从根结点出发,按照以下步骤访问二叉树的每个结点: 访问当前结点; 进入当前结点的左子树,以同样的步骤遍历左子树中的结点; 遍历完当前结点的左子树后,再进入它的右子树,以同样的步骤遍历右子树中的结点; 先序遍历这棵二叉树的过

    2024年02月04日
    浏览(45)
  • 【数据结构】二叉树的遍历递归算法详解

    我们来写一个函数 BuyNode(x)函数 用于创建二叉树结点。 用动态开辟函数 malloc 函数进行动态开辟,并强制转换为 BTNode 型,用变量 node 来去管理开辟的空间。 我们初始化结点,其 val 即为传入的参数x,左右指针 left 和 right 都设为NULL。 我们在主函数中创建上面这样一颗二叉树

    2024年01月20日
    浏览(45)
  • 【数据结构】二叉树的链式实现及遍历

    后文所有代码中的二叉树结点: 前,中,后序遍历都可以采用分治递归的思想解决,将根节点和它的孩子结点分别处理。 此处仅利用递归展开图分析前序遍历,中序和后序也是相同的思想: 层序遍历需要利用队列来进行,如果二叉树跟结点不为空,则让 指向它的一个指针入

    2024年02月07日
    浏览(50)
  • 数据结构——二叉树的遍历【前序、中序、后序】

    hello hello~ ,这里是大耳朵土土垚~💖💖 ,欢迎大家点赞🥳🥳关注💥💥收藏🌹🌹🌹 💥 个人主页:大耳朵土土垚的博客 💥 所属专栏:数据结构学习笔记 、C语言系列函数实现 💥对于数据结构顺序表、链表、堆有疑问的都可以在上面数据结构的专栏进行学习哦~ 有问题可

    2024年03月15日
    浏览(54)
  • 【数据结构】二叉树的层序遍历(四)

     目录 一,层序遍历概念 二,层序遍历的实现         1,层序遍历的实现思路         2,创建队列         Queue.h         Queue.c         3,创建二叉树         BTree.h         BTree.c         4,层序遍历的实现 层序遍历:除了先序遍历、中序遍历、

    2024年02月07日
    浏览(47)
  • 【数据结构】二叉树的前序遍历(七)

    题目详情: 给你二叉树的根节点 root ,返回它节点值的  前序   遍历; 我们先来看几个示例: 输入:root = [ 1,null,2,3 ] 输出:[ 1,2,3 ]  示例2: 输入:root = [ 1,2 ] 输出:[ 1,2 ] 示例三: 输入:root = [  ] 输出:[  ] 提示: 树中结点数目在范围【0,100】内 -100 = Nod

    2024年02月07日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包