表述形式
在这里我在非递归方面前序遍历和中序遍历都提供了两种不同的算法,一种是我自己根据性质和原理写的还有一种就是比较普遍的算法,代码也已经测试过啦,有什么问题可以留言或者私信我,在这里声明一下二叉树的输入的形式,不是顺序输入噢,是按照根左右的形式,空子树用’ ^ ‘代替,会这种表达的小伙伴可以直接跳转到代码方面
举例:
二叉树形态:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210125113227388.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1htdW11Xw==,size_16,color_FFFFFF,t_70)
(有点丑大家不要介意,嘿嘿)
根据根左右,并且空树就用‘^’符号代替的规则:
ABD^^^ CE^^ F^^^
说明:D后面三个’^‘,前面两个是说D既没有左子树,又没有右子树,所以有两个‘ ^ ’,而第三个’ ^ ‘就回到D前一个B,B没有右子树,所以就用一个’ ^ ',而后就到C啦,C是A的右子树嘛,所以就按规则办事喽,到后面就轮到E,E是叶子结点,那就和D一样啦,F也是。
这种方式在很多计算机系刚学习到数据结构应该都有涉及一点点吧,有问题欢迎私聊我哈![在这里插入图片描述](https://img-blog.csdnimg.cn/2021012511282336.png)
再举个小栗子:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210125120156663.png)
ABC ^^ DE ^^ FG ^^^^ (其中^表示空子树)
代码
二叉树非递归的三种遍历方法在这里是使用栈进行的,栈也是解决像类似这种非递归问题的常用方法之一。
需要完整代码的私聊我哈🍖🍖
部分代码如下:
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <limits.h>
#define maxsize 20
#define INFINITY 0x3f3f3f3f
#define OK 1;
#define ERROR -1;
#define Status int
typedef struct Node {
char data;
struct Node* LChild;
struct Node* RChild;
}BiTNode, * BiTree;
typedef BiTree StackElementType;
typedef BiTree QueueElementType;
typedef struct stack {
StackElementType elem[maxsize];
int top;
}Stack;
typedef struct qu {
QueueElementType ele[maxsize];
int front;
int rear;
}Queue;
测试结果
就用上面我们谈到的那棵树来做首个测验啦!
测试一:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210125114651689.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1htdW11Xw==,size_16,color_FFFFFF,t_70)
测试二:
![在这里插入图片描述](https://img-blog.csdnimg.cn/20210125114352819.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1htdW11Xw==,size_16,color_FFFFFF,t_70)
中序遍历我写了两个方法,但是上面的测试和代码只有一种,另一种目前好像有点问题,等我更正好了再回来修改,嘿嘿。
需要完整代码的私聊我~
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)