本贴给出二叉树先序、中序、后序三种遍历的非递归算法,此三个算法可视为标准算法。
1.先序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void PreOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
visite(p->data);
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s)) //通过下一次循环中的内嵌while实现右子树遍历
{
p=pop(s);
p=p->rchild;
}//endif
}//endwhile
}//PreOrderUnrec
2.中序遍历非递归算法
#define maxsize 100
typedef struct
{
Bitree Elem[maxsize];
int top;
}SqStack;
void InOrderUnrec(Bitree t)
{
SqStack s;
StackInit(s);
p=t;
while (p!=null || !StackEmpty(s))
{
while (p!=null) //遍历左子树
{
push(s,p);
p=p->lchild;
}//endwhile
if (!StackEmpty(s))
{
p=pop(s);
visite(p->data); //访问根结点
p=p->rchild; //通过下一次循环实现右子树遍历
}//endif
}//endwhile
}//InOrderUnrec
3.后序遍历非递归算法
#define maxsize 100
typedef enum{L,R} tagtype;
typedef struct
{
Bitree ptr;
tagtype tag;
}stacknode;
typedef struct
{
stacknode Elem[maxsize];
int top;
}SqStack;
void PostOrderUnrec(Bitree t)
{
SqStack s;
stacknode x;
StackInit(s);
p=t;
do
{
while (p!=null) //遍历左子树
{
x.ptr = p;
x.tag = L; //标记为左子树
push(s,x);
p=p->lchild;
}
while (!StackEmpty(s) && s.Elem[s.top].tag==R)
{
x = pop(s);
p = x.ptr;
visite(p->data); //tag为R,表示右子树访问完毕,故访问根结点
}
if (!StackEmpty(s))
{
s.Elem[s.top].tag =R; //遍历右子树
p=s.Elem[s.top].ptr->rchild;
}
}while (!StackEmpty(s));
}//PostOrderUnrec
- 浏览: 4544820 次
- 性别:
- 来自: 济南
最新评论
-
wahahachuang8:
GoEasy 实时推送支持IE6-IE11及大多数主流浏览器的 ...
服务器推送技术 -
pdztop:
inffas32.asm(594) inffas32.asm( ...
zlib 在 Visual Studio 2005 下编译失败的解决办法 -
myangle89:
这个方法有效果,但还是绕了一大圈。另外:如果每次这样使用,会造 ...
利用 Spring 与 Log4J 巧妙地进行动态日志配置切换并立即生效 -
lsw521314:
亲,请把用到的包贴出来好么?这版本问题搞得我头大······· ...
lucene MMAnalyzer 实现中文分词 -
guji528:
多命令执行:cmd /k reg delete "H ...
REG Command in Windows XP - Windows XP REG命令的作用和用法
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
二叉树先序、中序、后序遍历(递归、非递归算法) 其中自己已经开发了栈!
数据结构中关于二叉树的遍历,非递归算法数上未给出
二叉树前序、中序、后序三种遍历的非递归算法(C语言)
数据结构二叉树链式结构的前序遍历,中序遍历,后序遍历用递归的方法,层级遍历采用队列结构
二叉树先序中序后序三种遍历的非递归算法.doc
二叉树先序、中序、后序三种遍历的非递归算法_此三个算法可视为标准 二叉树先序、中序、后序三种遍历的非递归算法_此三个算法可视为标准 二叉树先序、中序、后序三种遍历的非递归算法_此三个算法可视为标准
基于C语言的关于二叉树的先序扩展创建,先序、中序、后序遍历的递归、非递归算法,求树的深度
采用二叉链表存储先序建立二叉树,非递归中序遍历二叉树算法实现
建立二叉树,以括号表示法输出二叉树,求二叉树的先序遍历,中序遍历,后序遍历输出~~~
自己编写的实验二叉树的后序遍历非递归算法 包括以递归中序遍历建立二叉树 前序,中序,后序递归以及非递归实现二叉树的遍历 经vc6.0编译通过 自己实验,不足之处应该很多,望指出
(1)输入字符序列,建立二叉链表 (2)中序遍历二叉树:递归 (3)中序遍历二叉树:非递归 (3)二叉树高度
数据结构中二叉树的先序遍历,中序遍历,后续遍历的递归和非递归的算法
本程序采用非递归方法实现对二叉树的先序、中序、后序遍历.自定义栈和树的结构。
[问题描述] 建立二叉树,并输出二叉树的先序,中序和后序遍历序列,以及二叉树的叶子数。 [基本要求] 要求根据读取的元素建立二叉树,能输出各种遍历。 [实现提示] 可通过输入带空格的前序序列建立二叉链表。