当前位置:首页 » 操作系统 » 二叉树后序遍历的非递归算法

二叉树后序遍历的非递归算法

发布时间: 2023-09-09 17:35:06

⑴ 编写一个程序,实现二叉树的先序遍历,中序遍历,后序遍历的各种递归和非递归算法,以及层次遍历的算法

文件 main.cpp 代码如下:

#include<malloc.h> // malloc()等
#include<stdio.h> // 标准输入输出头文件,包括EOF(=^Z或F6),NULL等
#include<stdlib.h> // atoi(),exit()
#include<math.h> // 数学函数头文件,包括floor(),ceil(),abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode
{
int data; // 结点的值
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空
void visit(int e)
{ printf("%d ",e); // 以整型格式输出
}
void InitBiTree(BiTree &T)
{ // 操作结果:构造空二叉树T
T=NULL;
}

void CreateBiTree(BiTree &T)
{ // 算法6.4:按先序次序输入二叉树中结点的值(可为字符型或整型,在主程中定义),
// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改
int number;
scanf("%d",&number); // 输入结点的值
if(number==Nil) // 结点的值为空
T=NULL;
else // 结点的值不为空
{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点
if(!T)
exit(OVERFLOW);
T->data=number; // 将值赋给T所指结点
CreateBiTree(T->lchild); // 递归构造左子树
CreateBiTree(T->rchild); // 递归构造右子树
}
}

void DestroyBiTree(BiTree &T)
{ // 初始条件:二叉树T存在。操作结果:销毁二叉树T
if(T) // 非空树
{ DestroyBiTree(T->lchild); // 递归销毁左子树,如无左子树,则不执行任何操作
DestroyBiTree(T->rchild); // 递归销毁右子树,如无右子树,则不执行任何操作
free(T); // 释放根结点
T=NULL; // 空指针赋0
}
}

void PreOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数。修改算法6.1
// 操作结果:先序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ Visit(T->data); // 先访问根结点
PreOrderTraverse(T->lchild,Visit); // 再先序遍历左子树
PreOrderTraverse(T->rchild,Visit); // 最后先序遍历右子树
}
}

void InOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:中序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T)
{ InOrderTraverse(T->lchild,Visit); // 先中序遍历左子树
Visit(T->data); // 再访问根结点
InOrderTraverse(T->rchild,Visit); // 最后中序遍历右子树
}
}

void PostOrderTraverse(BiTree T,void(*Visit)(int))
{ // 初始条件:二叉树T存在,Visit是对结点操作的应用函数
// 操作结果:后序递归遍历T,对每个结点调用函数Visit一次且仅一次
if(T) // T不空
{ PostOrderTraverse(T->lchild,Visit); // 先后序遍历左子树
PostOrderTraverse(T->rchild,Visit); // 再后序遍历右子树
Visit(T->data); // 最后访问根结点
}
}

void main()
{
BiTree T;
InitBiTree(T); // 初始化二叉树T
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空,输入范例:1 2 0 0 3 0 0\n");
CreateBiTree(T); // 建立二叉树T
printf("先序递归遍历二叉树:\n");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
printf("\n中序递归遍历二叉树:\n");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
printf("\n后序递归遍历二叉树:\n");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
}
这样可以么?

⑵ 二叉树的遍历非递归算法中应注意哪些问题

先序非递归算法
【思路】
假设:T是要遍历树的根指针,若T != NULL
对于非递归算法,引入栈模拟递归工作栈,初始时栈为空。
问题:如何用栈来保存信息,使得在先序遍历过左子树后,能利用栈顶信息获取T的右子树的根指针?
方法1:访问T->data后,将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应扮谈弯为T,出栈,再先序遍历T的右子树。
方法2:访问T->data后,将T->rchild入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T->rchild,出栈,遍历以该指针为根的子树。
【算法1】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法一,流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S)){
while ( T != NULL ){
Visit(T->data) ;
Push(S,T);
T = T->lchild;
}

if( !StackEmpty(S) ){
Pop(S,T);
T = T->rchild;
}
}
}
【算法2】
void PreOrder(BiTree T, Status ( *Visit ) (ElemType e))

{ // 基于方法二,流程图如右,当型循环
InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Visit(T->data);
Push(S, T->rchild);
T = T->lchild;
}
if ( !StackEmpty(S) ){
Pop(S,T);
}
}
}
进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。
中序非递归算法
【思路】
T是要遍历树的根指针,中序遍历要求厅闷在遍历完左子树后,访问根,再遍历右子树。
问题:如何用栈来保存信息,使得在中序遍历过左子树后,能利用栈顶信息获取T指针?
方法:先将T入栈,遍历左子树;遍历完左子树返回时,栈顶元素应为T,出栈,访问T->data,再中序遍历T的右子树。

【算法】
void InOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右,当型循环
InitStack(S);

while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T);
T = T->lchild;
}
if( !StackEmpty(S) ){
Pop(S, T);
Visit(T->data);
T = T->rchild;
}
}
}
进一步考虑:对于处理流程中的循环体的直到型、当型+直到型的实现。
后序非递归算法
【思路】

T是要遍历树的根指针,后序遍历要求在遍历完左右子树后,再访问根。需要判断根结点的左右子树是否均遍历过。
可采用标记法侍升,结点入栈时,配一个标志tag一同入栈(0:遍历左子树前的现场保护,1:遍历右子树前的现场保护)。
首先将T和tag(为0)入栈,遍历左子树;返回后,修改栈顶tag为1,遍历右子树;最后访问根结点。
typedef struct stackElement{
Bitree data;
char tag;
}stackElemType;
【算法】
void PostOrder(BiTree T, Status ( *Visit ) (ElemType e))
{ // 流程图如右,当型循环
InitStack(S);
while ( T!=NULL || !StackEmpty(S) ){
while ( T != NULL ){
Push(S,T,0);
T = T->lchild;
}

while ( !StackEmpty(S) && GetTopTag(S)==1){
Pop(S, T);
Visit(T->data);
}
if ( !StackEmpty(S) ){
SetTopTag(S, 1); // 设置栈顶标记
T = GetTopPointer(S); // 取栈顶保存的指针
T = T->rchild;
}else break;
}
}

⑶ 二叉树中序遍历的非递归算法

推荐这篇文章,把二叉树的前序、中序和后续的递归和非递归算法都讲了。
http://www.cppblog.com/ngaut/archive/2006/01/01/2351.html

热点内容
oracle二进制存储 发布:2025-01-29 13:44:47 浏览:575
浙江常规存储设备特价 发布:2025-01-29 13:44:43 浏览:675
恩格尔算法 发布:2025-01-29 13:44:41 浏览:713
怎么查看我的车是什么配置 发布:2025-01-29 13:38:20 浏览:78
间片轮转算法 发布:2025-01-29 13:38:19 浏览:438
PID算法包 发布:2025-01-29 13:36:52 浏览:197
安卓加速器app哪个好 发布:2025-01-29 13:36:49 浏览:155
如何有专有的服务器 发布:2025-01-29 13:36:14 浏览:921
android前台activity 发布:2025-01-29 13:31:24 浏览:870
安卓怎么配置mitm 发布:2025-01-29 13:10:55 浏览:821