devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构——二叉树先序、中序、后序及层次四种遍历_先序 中序 后序

作者：繁依Fanyi0 | 2024-05-26 07:44:02

赞

踩

先序 中序 后序

数据结构——二叉树先序、中序、后序三种遍历

一、图示展示：

（1）先序遍历

先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果

先序遍历结果为：A B D H I E J C F K G

在这里插入图片描述
动画演示：

记住小人沿着外围跑一圈（直到跑回根节点），多看几次动图便能理解

在这里插入图片描述
在这里插入图片描述

（2）中序遍历

中序遍历可以看成，二叉树每个节点，垂直方向投影下来（可以理解为每个节点从最左边开始垂直掉到地上），然后从左往右数，得出的结果便是中序遍历的结果

中遍历结果为：H D I B E J A F K C G
在这里插入图片描述

动画展示：

记住，中序遍历就是从最左边开始，把每个节点垂直投影到同一直线上，然后从左往右读值就可以了，多看几遍动图就理解了

在这里插入图片描述

（3）后序遍历

后序遍历就像是剪葡萄，我们要把一串葡萄剪成一颗一颗的。

还记得我上面提到先序遍历绕圈的路线么？（不记得翻上面理解）

就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样），就把它剪下来，组成的就是后序遍历了。

后序遍历中，根节点默认最后面

后序遍历结果：H I D J E B K F G C A
在这里插入图片描述
动画展示：
在这里插入图片描述

（4）层次遍历

层次遍历很好理解，就是从根节点开始，一层一层，从上到下，每层从左到右，依次写值就可以了

层次遍历结果：A B C D E F G H I J K

在这里插入图片描述

解释外圈跑的意思：

绕着外围跑一整圈的真正含义是：遍历所有结点时，都先往左孩子走，再往右孩子走。

（5）口诀

先序遍历： 先根 再左 再右

中序遍历： 先左 再根 再右

后序遍历： 先左 再右 再根

这里的根，指的是每个分叉子树（左右子树的根节点）根节点，并不只是最开始头顶的根节点，需要灵活思考理解，建议画图理解！！

二、代码展示：

#include<stdio.h>
#include<stdlib.h>

  • 1
  • 2

typedef struct Tree{

int data; // 存放数据域
struct Tree lchild; // 遍历左子树指针
struct Tree rchild; // 遍历右子树指针

}Tree,*BitTree;

BitTree CreateLink()
{
int data;
int temp;
BitTree T;

<span class="token function">scanf</span><span class="token punctuation">(</span><span class="token string">"%d"</span><span class="token punctuation">,</span><span class="token operator">&amp;</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>		<span class="token comment">//	输入数据</span>
temp<span class="token operator">=</span><span class="token function">getchar</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>			<span class="token comment">//	吸收空格</span>

<span class="token keyword">if</span><span class="token punctuation">(</span>data <span class="token operator">==</span> <span class="token operator">-</span><span class="token number">1</span><span class="token punctuation">)</span><span class="token punctuation">{<!-- --></span>			<span class="token comment">//	输入-1 代表此节点下子树不存数据，也就是不继续递归创建</span>
	
	<span class="token keyword">return</span> <span class="token constant">NULL</span><span class="token punctuation">;</span>

<span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{<!-- --></span>
	T <span class="token operator">=</span> <span class="token punctuation">(</span>BitTree<span class="token punctuation">)</span><span class="token function">malloc</span><span class="token punctuation">(</span><span class="token keyword">sizeof</span><span class="token punctuation">(</span>Tree<span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>			<span class="token comment">//		分配内存空间</span>
	T<span class="token operator">-&gt;</span>data <span class="token operator">=</span> data<span class="token punctuation">;</span>								<span class="token comment">//		把当前输入的数据存入当前节点指针的数据域中</span>
	
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"请输入%d的左子树: "</span><span class="token punctuation">,</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>		
	T<span class="token operator">-&gt;</span>lchild <span class="token operator">=</span> <span class="token function">CreateLink</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>					<span class="token comment">//		开始递归创建左子树</span>
	<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"请输入%d的右子树: "</span><span class="token punctuation">,</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>			
	T<span class="token operator">-&gt;</span>rchild <span class="token operator">=</span> <span class="token function">CreateLink</span><span class="token punctuation">(</span><span class="token punctuation">)</span><span class="token punctuation">;</span>					<span class="token comment">//		开始到上一级节点的右边递归创建左右子树</span>
	<span class="token keyword">return</span> T<span class="token punctuation">;</span>							<span class="token comment">//		返回根节点</span>
<span class="token punctuation">}</span>	

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

}
// 先序遍历
void ShowXianXu(BitTree T) // 先序遍历二叉树
{
if(TNULL) // 递归中遇到NULL，返回上一层节点
{
return;
}
printf("%d ",T->data);
ShowXianXu(T->lchild); // 递归遍历左子树
ShowXianXu(T->rchild); // 递归遍历右子树
}
// 中序遍历
void ShowZhongXu(BitTree T) // 先序遍历二叉树
{
if(TNULL) // 递归中遇到NULL，返回上一层节点
{
return;
}

<span class="token function">ShowZhongXu</span><span class="token punctuation">(</span>T<span class="token operator">-&gt;</span>lchild<span class="token punctuation">)</span><span class="token punctuation">;</span>			<span class="token comment">//	递归遍历左子树</span>
<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d "</span><span class="token punctuation">,</span>T<span class="token operator">-&gt;</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">ShowZhongXu</span><span class="token punctuation">(</span>T<span class="token operator">-&gt;</span>rchild<span class="token punctuation">)</span><span class="token punctuation">;</span>			<span class="token comment">//	递归遍历右子树</span>

  • 1
  • 2
  • 3

}
// 后序遍历
void ShowHouXu(BitTree T) // 后序遍历二叉树
{
if(T==NULL) // 递归中遇到NULL，返回上一层节点
{
return;
}

<span class="token function">ShowHouXu</span><span class="token punctuation">(</span>T<span class="token operator">-&gt;</span>lchild<span class="token punctuation">)</span><span class="token punctuation">;</span>			<span class="token comment">//	递归遍历左子树</span>
<span class="token function">ShowHouXu</span><span class="token punctuation">(</span>T<span class="token operator">-&gt;</span>rchild<span class="token punctuation">)</span><span class="token punctuation">;</span>			<span class="token comment">//	递归遍历右子树</span>
<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"%d "</span><span class="token punctuation">,</span>T<span class="token operator">-&gt;</span>data<span class="token punctuation">)</span><span class="token punctuation">;</span>

  • 1
  • 2
  • 3

}

int main()
{
BitTree S;
printf(“请输入第一个节点的数据:\n”);
S = CreateLink(); // 接受创建二叉树完成的根节点
printf(“先序遍历结果: \n”);
ShowXianXu(S); // 先序遍历二叉树

<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"\n中序遍历结果: \n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">ShowZhongXu</span><span class="token punctuation">(</span>S<span class="token punctuation">)</span><span class="token punctuation">;</span>				<span class="token comment">//		中序遍历二叉树</span>

<span class="token function">printf</span><span class="token punctuation">(</span><span class="token string">"\n后序遍历结果: \n"</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
<span class="token function">ShowHouXu</span><span class="token punctuation">(</span>S<span class="token punctuation">)</span><span class="token punctuation">;</span>				<span class="token comment">//		后序遍历二叉树</span>

<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>	

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
转载： https://blog.csdn.net/chinesekobe/article/details/110874773
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/625805
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号