106.【C语言】数据结构之二叉树的三种递归遍历方式

已于 2025-02-08 10:37:12 修改
阅读量1.7k 收藏 22
点赞数 42
分类专栏： C语言 数据结构 文章标签： c语言 数据结构 开发语言 算法 笔记 二叉树
于 2024-11-27 20:08:08 首次发布
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/2401_85828611/article/details/144091922
版权

目录

1.知识回顾

2.分析二叉树的三种遍历方式

1.总览

2.前序遍历(也称先序遍历)

3.中序遍历

4.后序遍历

5.前序中序后序遍历速写方法

6.层序遍历

3.代码实现

1.准备工作

2.前序遍历函数PreOrder

测试结果

3.中序遍历函数InOrder

测试结果

4.后序遍历函数PostOrder

测试结果

4.底层分析

附一张PreOrder的调用图

附一张InOrder的调用图

1.知识回顾

在99.【C语言】数据结构之二叉树的基本知识文章中提到:任何一棵树都由两部分构成:根和子树,子树又由根和子树构成

因此看见二叉树要本能地做出反应:拆成三部分:根,左子树和右子树,直到遇到空树(叶节点)则停止拆分

 7447cca743864287a76ebeab89df1c1c.png

2.分析二叉树的三种遍历方式

1.总览

前序遍历

中序遍历

后序遍历

层序遍历(要借助队列,本文暂时不讲其代码实现)

e7d5951f3821482fa7550385986249c9.png

下面三种遍历方式都基于上面这张图分析

2.前序遍历(也称先序遍历)

定义:按根-->左子树-->右子树的顺序遍历

遍历顺序:

1(根)-->2(根)-->3(根)-->NULL(3的左子树)-->NULL(3的右子树)-->NULL(2的右子树)-->4(根)-->5(根)-->NULL(5的左子树)-->NULL(5的右子树)-->6(根)-->NULL(6的左子树)-->NULL(6的右子树)

bd1f91734a014b38b19d7b5d86c7676d.png

备注:图中每个方框都代表一棵子树

3.中序遍历

定义:按左子树-->根-->右子树的顺序遍历

这里有一个易错点也是关键点:中序遍历中第一个访问的一定为空!!!!

虽然1的左节点为2,但不能访问2(即不可访问root->data),按中序遍历的定义,要先访问2的左子树;虽然2的左节点为3,但不能访问3,按中序遍历的定义,先访问3左子树;3的左子树为NULL,其没有子树,因此开始访问根(即3),再访问根的右子树NULL,再回归......

左子树访问完才能访问根

遍历顺序:NULL(3的左子树)-->3-->NULL(3的右子树)-->2(根)-->NULL(2的右子树)-->1(根)-->NULL(5的左子树)-->5(根)-->NULL(5的右子树)-->4(根)-->NULL(6的左子树)-->6(根)-->NULL(6的右子树)

dd6d7b25fa2e4f61b4164b0ffe7214d8.png

备注:图中每个方框都代表一棵子树  

4.后序遍历

定义:按左子树-->右子树-->根的顺序遍历

和中序遍历一样,也有一个易错点也是关键点:和中序遍历一样,先访问左子树,因此后序遍历中第一个访问的也一定为空!!!!

遍历顺序:NULL(3的左子树)-->NULL(3的右子树)-->3(根)-->NULL(2的右子树)-->2(根)-->NULL(5的左子树)-->NULL(5的右子树)-->5(根)-->NULL(6的左子树)-->NULL(6的右子树)-->6(根)-->4(根)-->1(根)

3c55dfd99ac743d0801bd39f6d065fec.png

备注:图中每个方框都代表一棵子树   

5.前序中序后序遍历速写方法

仍然拿这棵树为例子

e7d5951f3821482fa7550385986249c9.png

方法:按遍历顺序排好依次往下罗列(如果不看NULL)

前序遍历:按前序遍历排好依次往下罗列 

 1->2->3->4->5->6

中序遍历:按中序遍历排好依次往下罗列

后序遍历:按后序遍历排好依次往下罗列 

6.层序遍历

定义:按层的方式遍历(,设n为树的深度,h==1-->h==2-->h==3-->...-->h==n)

遍历顺序:1-->2-->4-->3-->5-->6

h==1为第一层,只有1;h==2为第二层,有2和4;h==3为第三层,有3,5和6;

具体参见109.【C语言】数据结构之二叉树层序遍历

3.代码实现

1.准备工作

用结构体去定义一个二叉树,其成员变量有:数值域data,结构体指针变量left和right,分别指向其对应的左子树和右子树(写入Tree.h)

typedef int BTDataType;
typedef struct BinaryTreeNode
{
	BTDataType data;
	struct BinaryTreeNode* left;
	struct BinaryTreeNode* right;
}BTNode;

定义完二叉树后还要开辟空间函数BuyNode和建立树的函数(写入Tree.c)

BTNode* BuyNode(BTDataType x)
{
	BTNode* node = (BTNode*)malloc(sizeof(BTNode));
	if (node == NULL)
	{
		perror("malloc");
		return NULL;
	}
	node->data = x;
	node->left = NULL;
	node->right = NULL;
	return node;
}

建立指定的二叉树,见下图

 e7d5951f3821482fa7550385986249c9.png

BTNode* CreateTree()
{
	//写入各个节点的数据域
	BTNode* node1 = BuyNode(1);
	BTNode* node2 = BuyNode(2);
	BTNode* node3 = BuyNode(3);
	BTNode* node4 = BuyNode(4);
	BTNode* node5 = BuyNode(5);
	BTNode* node6 = BuyNode(6);

	//设置left和right指针
	node1->left = node2;
	node1->right = node4;
	node2->left = node3;
	node4->left = node5;
	node4->right = node6;

	//返回根节点的指针
	return node1;
}

递归返回的条件:遇到空树(NULL)

2.前序遍历函数PreOrder

按根-->左子树-->右子树的顺序遍历,

即printf("%d ",root->data);-->PreOrder(root->left);-->PreOrder(root->right);

void PreOrder(BTNode* root)
{
	//先判断是否为空树(叶节点的左节点和右节点均为空树)
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//按根-->左子树-->右子树的顺序遍历
	printf("%d ",root->data);
	PreOrder(root->left);
	PreOrder(root->right);
}

注意:一定要先判断是否为空树(叶节点的左节点和右节点均为空树)

测试结果

mainc.c写入以下代码

#include "Tree.h"
int main()
{
	BTNode* root = CreateTree();
	PreOrder(root);
	return 0;
}

4281ea4b0863424e94e65923f055cf78.png

bd1f91734a014b38b19d7b5d86c7676d.png

和前面的图完全符合

3.中序遍历函数InOrder

:按左子树-->根-->右子树的顺序遍历,

即InOrder(root->left);-->printf("%d ", root->data);-->InOrder(root->right);

void InOrder(BTNode* root)
{
	//先判断是否为空树(叶节点的左节点和右节点均为空树)
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//按左子树-->根-->右子树的顺序遍历
	InOrder(root->left);
	printf("%d ", root->data);
	InOrder(root->right);
}

注意:一定要先判断是否为空树(叶节点的左节点和右节点均为空树) 

测试结果

mainc.c写入以下代码

#include "Tree.h"
int main()
{
	BTNode* root = CreateTree();
	InOrder(root);
	return 0;
}

 f61598a6904e4cbda6aed0047cf9623a.png

dd6d7b25fa2e4f61b4164b0ffe7214d8.png 和前面的图完全符合

4.后序遍历函数PostOrder

按左子树-->右子树-->根的顺序遍历,

即PostOrder(root->left);-->PostOrder(root->right);-->printf("%d ", root->data);

void PostOrder(BTNode* root)
{
	//先判断是否为空树(叶节点的左节点和右节点均为空树)
	if (root == NULL)
	{
		printf("NULL ");
		return;
	}

	//按左子树-->右子树-->根的顺序遍历
	PostOrder(root->left);
	PostOrder(root->right);
	printf("%d ", root->data);
}

注意:一定要先判断是否为空树(叶节点的左节点和右节点均为空树) 

测试结果

mainc.c写入以下代码

#include "Tree.h"
int main()
{
	BTNode* root = CreateTree();
	PostOrder(root);
	return 0;
}

ce1b1e00233142dd8d34a81c9d87d242.png

3c55dfd99ac743d0801bd39f6d065fec.png

和前面的图完全符合

4.底层分析

每调用一次PreOrder或InOrder或PostOrder函数就压入栈区,返回时出栈

在E41.【C语言】练习:斐波那契函数的空间复杂度的计算及函数调用分析文章中讲过了函数调用的堆栈分析,这里不再赘述

附一张PreOrder的调用图

e355fba3c180434e980b6c08259c252d.jpeg

附一张InOrder的调用图

9f446891de6c4ce1895580ce6945bc38.jpeg

数据结构——二叉树先序、中序、后序及层次四种遍历（C语言版）
正弦定理的博客
12-09 36万+
数据结构——二叉树先序、中序、后序三种遍历二叉树先序、中序、后序三种遍历三、代码展示： 二叉树先序、中序、后序三种遍历 先序遍历：3 2 2 3 8 6 5 4 中序遍历：2 2 3 3 4 5 6 8 后序遍历: 2 3 2 4 5 6 8 3 三种遍历不同之处在，输出数据放在不同之处 三、代码展示： #include<stdio.h> #include<stdlib.h> typedef struct Tree{ int
二叉树的非递归遍历算法C语言实现（详细注释版）
qq_51751843的博客
04-21 6944
二叉树的非递归算法遍历分为：先序遍历，中序遍历，后序遍历。 此文章我会根据先、中、后的顺序为大家用C语言实现全部代码。 顾名思义先序遍历是先遍历根节点，随后是左孩子，右孩子 。 中序遍历与后序遍历可以通过类比改变根节点相对左右孩子的遍历顺序。 我不为大家讲解先、中、后遍历的实现思想了。 我为我所写的每一行代码都书写了详细的注释，为大家看懂代码的目的及功能提供便利。 所写注释可能会有少部分错别字，如果发现欢迎大家及时提出。 先为大家附上代码实现结果图： 马上为大家附上全部代码： #
c语言递归遍历二叉树
10-22
递归遍历二叉树、c语言以及数据结构均要用到，我还会上传非递归的··
递归遍历二叉树--C语言
lei2014lei的博客
12-22 873
  之前写了关于二叉树的非递归遍历算法的代码，今天把二叉树的递归遍历算法的代码补上，内容很简单！但是今天也算是写了一会儿代码了～姑且这么认为吧～ 代码： #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef struct BiTNode { char data;//二叉树节点数据 struct BiTNode *lc...
二叉树的遍历（递归）（c语言）
最新发布
2402_87796189的博客
04-11 120
【代码】二叉树的遍历（递归）（c语言）
二叉树的递归遍历（c语言）
qq_43633585的博客
04-16 516
#include<stdio.h> #include<stdlib.h> #define OK 1 #define ERROR 0 typedef char Elemtype; typedef struct node { Elemtype data; struct node *lchild,*rchild; }*BiTree,Tree; void createBiTr...
二叉树递归遍历（C语言实现）
m0_46544158的博客
10-28 2848
#include<stdio.h> #include<string.h> #include<stdlib.h> //二叉树节点 struct BinaryNode { char ch; //显示字母 struct BinaryNode* lChild; //左孩子 struct BinaryNode* rChild; //右孩子 }; //递归函数：先序遍历 void recursion(struct BinaryNode* root) { if (roo
数据结构 --- c语言递归法遍历二叉树
weixin_60569662的博客
02-24 1264
二叉树的单一个体 - - -> 一个节点、两个指针，结构体的定义和双向链表类似 二叉树可以存任何类型的数据：这里选择存char类型数据 二叉树的结构体描述 #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef struct Node { char data; //顶点数据 struct Node* LChild; //左子树的指针 struct No...
C语言数据结构之二叉树的非递归后序遍历算法
01-01
C语言数据结构之二叉树的非递归后序遍历算法 前言： 前序、中序、后序的非递归遍历中，要数后序最为麻烦，如果只在栈中保留指向结点的指针，那是不够的，必须有一些额外的信息存放在栈中。 方法有很多，这里只举一...
C语言二叉树的非递归遍历实例分析
09-04
在计算机科学中，二叉树是一种基础的数据结构，它由节点（或称为顶点）组成，每个节点最多有两个子节点，通常称为左子节点和右子节点。二叉树遍历是访问二叉树中所有节点的过程，通常分为三种基本方法：先序遍历、...
[C语言]二叉树的递归遍历
renboyu010214的博客
04-05 246
遍历方法：无论哪种遍历方式，对每个节点的查看方式一般都遵循先左后右 二叉树的遍历方式 （D：DATA，L：LEFT，R：RIGHT） 先序遍历：DLR 中序遍历：LDR 后序遍历：LRD 对上图二叉树进行遍历 #define _CRT_SECURE_NO_WARNINGS #include<stdio.h> #include<stdlib.h> //二叉树结点 ...
C语言实现二叉树的中序遍历（递归）
12-13
C语言实现二叉树的中序遍历（递归）。大家下载看看哦！有用的！
【算法】二叉树的递归遍历C语言实现
东东里个乖乖
02-07 9252
二叉树是一种极其重要的数据结构,以下是二叉树的结构定义 创建 和递归先序 中序 后序 遍历的代码. #include #include typedef char ElemType; /*二叉树节点数据结构*/ typedef struct node{ ElemType data; struct treenode *lChild; struct treenode *rCh
c语言实现二叉树的递归遍历
hou19975418的博客
01-17 1294
c语言实现二叉树递归遍历，首先用结构体给出结点类型，然后创建具体的结点变量，接着对结点进行连接。递归遍历的函数的内部主要是根节点的打印和左右子树的递归，前中后序的实现通过调整递归的顺序即可完成。
C语言 二叉树的遍历（递归和非递归）
weixin_30648963的博客
01-22 163
#include <iostream> #include <cstdio> #include "biTree.h" #include "cstdlib" #define OVERFLOW -1 #include <stack> using namespace std; Status CreateBiTree( BiTree &T ) {...
C语言二叉树的递归遍历综合
wwxy1995的博客
12-17 317
二叉树的前序，中序，后序遍历本质上是深度优先搜索DFS,可以用过递归方法实现，求二叉树的高度，求二叉树叶子的个数，拷贝二叉树和删除二叉树，都可以通过递归的方式实现 代码 #include &lt;stdio.h&gt; #include &lt;stdlib.h&gt; typedef struct BINARYNODE { char ch; struct BINARYNODE* lch...
二叉树遍历——递归链式（C语言实现）
qq_63580639的博客
10-27 2859
递归实现二叉树的前，中，后，层，序遍历
二叉树的建立与递归遍历C语言版
岳麓丹枫
06-22 1335
#include #include typedef struct BTNode { char data; struct BTNode *lchild; struct BTNode *rchild; }BTNode; void createTree(BTNode* *T) { char ch = getchar(); if(ch=='#')  { *T=
c语言数据结构二叉树的非递归遍历代码
05-21
二叉树的非递归遍历通常使用栈来实现。以下是三种非递归遍历方式的代码实现： 1. 非递归中序遍历： ``` void inorderTraversal(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; while (cur != nullptr || !st.empty()) { if (cur != nullptr) { st.push(cur); cur = cur->left; } else { cur = st.top(); st.pop(); cout << cur->val << " "; cur = cur->right; } } } ``` 2. 非递归先序遍历： ``` void preorderTraversal(TreeNode* root) { stack<TreeNode*> st; if (root != nullptr) { st.push(root); } while (!st.empty()) { TreeNode* cur = st.top(); st.pop(); cout << cur->val << " "; if (cur->right != nullptr) { st.push(cur->right); } if (cur->left != nullptr) { st.push(cur->left); } } } ``` 3. 非递归后序遍历： ``` void postorderTraversal(TreeNode* root) { stack<TreeNode*> st; TreeNode* prev = nullptr; if (root != nullptr) { st.push(root); } while (!st.empty()) { TreeNode* cur = st.top(); if ((cur->left == nullptr && cur->right == nullptr) || (prev != nullptr && (prev == cur->left || prev == cur->right))) { cout << cur->val << " "; st.pop(); prev = cur; } else { if (cur->right != nullptr) { st.push(cur->right); } if (cur->left != nullptr) { st.push(cur->left); } } } } ```
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包

打赏作者

zhangcoder

赠人玫瑰手有余香,感谢支持~

¥1 ¥2 ¥4 ¥6 ¥10 ¥20
扫码支付：¥1
获取中
扫码支付

您的余额不足，请更换扫码支付或充值

打赏作者

实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值