文档章节

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

郭蓉蓉
 郭蓉蓉
发布于 2017/01/12 15:49
字数 882
阅读 2
收藏 0

有两种方法,我用自己的理解写出来:

第一种:

(1)首先从根节点开始,如果存在左孩子则进栈

(2)如果不存在左孩子并且不存在右孩子则出栈(有右孩子并且是第一次应该出但这时候并不出,标记为           1),将它的右孩子进栈

总结:没有左孩子则出,但是要看是否有右孩子,如果有右孩子并且是第一次出,此时并不出栈,先把右孩子进栈

第二种:

(1)将根入栈

(2)将左右孩子都进栈,依次向下,直到左右子树都为空的时候出栈

(3)如果不为空,看之前出栈的成员是否是当前结点的子结点,如果是则出栈,不是的话则不出。

总结:之前出栈的结点是否是当前结点的左右子树或者当前结点左右子树是否为空,只有符合这两种情况才可以将栈顶的成员出栈

         在这里附上第两种思想的代码:

// 非递归算法.cpp : 定义控制台应用程序的入口点。
//
#include<stdio.h>
#include<stdlib.h>
#define N 20
typedef struct TNode
{
	char data;
	struct TNode *LChild,*RChild;
}TNode,*Tree;

typedef struct Stack
{
	Tree data[N];
	int top;
}Stack,*PStack;

//创建二叉树
void CreateTree(Tree *T)
{
	char ch;
	scanf("%c",&ch);
	if(ch == '#')
	{
		*T = NULL;
	}
	else
	{
		*T = (TNode*)malloc(sizeof(TNode));    /*结构体指针需要分配内存一定不能忘记*/
		(*T)->data = ch;
		CreateTree(&(*T)->LChild);
		CreateTree(&(*T)->RChild);
	}
}

void PrintTree(Tree T)
{
	if(T != NULL)
	{
		printf("%c	",T->data);
		PrintTree(T->LChild);
		PrintTree(T->RChild);
	}
}
//初始化
PStack initStack(PStack *S)
{
	*S = (Stack *)malloc(sizeof(Stack));
	(*S)->top = -1;
	return *S;
}
//判空
bool IsEmpty(Stack *S)
{
	return S->top == -1;
}
//判满
bool IsFull(Stack *S)
{
	return S->top > N;
}
//压栈
void push(Stack *S,Tree T)
{
	if(!IsFull(S))
	{
	    S->data[++S->top] = T;
    }
	else
		printf("栈已满!");
}
//出栈
Tree pop(Stack *S)
{
	if(!IsEmpty(S))
		return S->data[S->top--];		
}

//取顶
Tree Gettop(Stack *S)
{
	if(!IsEmpty(S))
		return S->data[S->top];	
}

//非递归中序遍历
void InOrder(Tree T)
{
	PStack S;
	S = initStack(&S);
	Tree p = T;
	while(p != NULL || !IsEmpty(S))
	{
		if(p != NULL)
		{
			push(S,p);
			p = p->LChild;
		}
		else
		{
			p = pop(S);
			printf("%c	",p->data);
			p = p->RChild;
		}
	}
}

//非递归后序遍历
//非递归后序遍历
void postOrder(Tree T)
{
	PStack S;
	S = initStack(&S);
	Tree p = T;
	int Tag[20];///栈,用于标记从左(0)或右(1)返回
	while(p != NULL || !IsEmpty(S))
	{
		while(p != NULL)
		{
			push(S,p);
			Tag[S->top] = 0;
			p = p->LChild;
		}
		while(!IsEmpty(S) && Tag[S->top] == 1)
		{
			p = pop(S);
			printf("%c	",p->data);
		}
		if(!IsEmpty(S))
		{
			Tag[S->top] = 1;//设置右子树以及访问
			p = Gettop(S);
			p = p->RChild;
		}
		else
			break;
	}
}
//判断刚访问过的结点是不是当前栈顶结点的孩子
void postOrder2(Tree T)
{
	TNode *p,*q;
	Tree s[N];
	int top = 0;
	q = NULL;
	p = T;
	//只要当前结点存在或者栈不为空
	while(p != NULL || top != 0)
	{
		//从当前结点除非,进栈并走左子树,直到左子树为空
		while(p != NULL)
		{
			top++;
			if(top > N)
			{
				printf("栈满!\n");   //要判断栈是否已满
			}
			s[top] = p;
			p = p->LChild;
		}
		//栈不为空
		if(top > 0)
		{
			p = s[top];
			/*除了下面两种情况外均不应访问根
			1.没有右孩子此时访问根
			2.p的右孩子是刚被访问过的结点q,此时也应该访问根结点
			*/
			if((p->RChild == NULL) || (p->RChild == q))
			{
				printf("%c	",p->data);
				q = p;
				top--;
				p = NULL;
			}
			else
				p = p->RChild;//
		}
	}
}


int main()
{
	Tree T;
	//T = NULL;
	printf("请输入二叉树的值!\n");
	CreateTree(&T);
	PrintTree(T);
	printf("\n");

	printf("非递归中序遍历!\n");
	InOrder(T);
	printf("\n");

	printf("非递归后序遍历1!\n");
	postOrder(T);
	printf("\n");

	printf("非递归后序遍历2!\n");
	postOrder2(T);
	printf("\n");
	system("pause");
	return 0;
}

 

© 著作权归作者所有

郭蓉蓉
粉丝 1
博文 14
码字总数 4589
作品 0
西安
私信 提问
二叉树的遍历,深度优先遍历和广度优先遍历

原文:http://www.cnblogs.com/joyang/p/4860441.html 二叉树的遍历: D:访问根结点,L:遍历根结点的左子树,R:遍历根结点的右子树。 给定一棵二叉树的前序遍历序列和中序遍历序列可以惟一...

not_in_mountain
2017/09/29
0
0
面试算法知识梳理(13) - 二叉树算法第三部分

面试算法代码知识梳理系列 面试算法知识梳理(1) - 排序算法 插入排序 希尔排序 选择排序 冒泡排序 计数排序 基数排序 归并排序 快速排序 双向扫描的快速排序 堆排序 面试算法知识梳理(2) - 字...

泽毛
2017/12/22
0
0
二叉树的递归,非递归遍历,深度优先遍历,广度优先遍历

结果: 二叉树的递归先序遍历 A B D E H I C F J G P 二叉树的非递归先序遍历 A B D E H I C F J G P 二叉树的递归中序遍历 D B H E I A F J C P G 二叉树的非递归中序遍历 D B H E I A F J ...

tsmyk0715
2016/07/04
387
0
二叉树递归和非递归遍历

二叉树的非递归遍历 二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就 是递归定义,因...

种地瓜
2016/08/03
61
0
[算法总结] 20 道题搞定 BAT 面试——二叉树

本文首发于我的个人博客:尾尾部落 0. 几个概念 完全二叉树:若二叉树的高度是h,除第h层之外,其他(1h-1)层的节点数都达到了最大个数,并且第h层的节点都连续的集中在最左边。想到点什么没...

繁著
2018/09/04
0
0

没有更多内容

加载失败,请刷新页面

加载更多

代理模式之JDK动态代理 — “JDK Dynamic Proxy“

动态代理的原理是什么? 所谓的动态代理,他是一个代理机制,代理机制可以看作是对调用目标的一个包装,这样我们对目标代码的调用不是直接发生的,而是通过代理完成,通过代理可以有效的让调...

code-ortaerc
今天
5
0
学习记录(day05-标签操作、属性绑定、语句控制、数据绑定、事件绑定、案例用户登录)

[TOC] 1.1.1标签操作v-text&v-html v-text:会把data中绑定的数据值原样输出。 v-html:会把data中值输出,且会自动解析html代码 <!--可以将指定的内容显示到标签体中--><标签 v-text=""></......

庭前云落
今天
8
0
VMware vSphere的两种RDM磁盘

在VMware vSphere vCenter中创建虚拟机时,可以添加一种叫RDM的磁盘。 RDM - Raw Device Mapping,原始设备映射,那么,RDM磁盘是不是就可以称作为“原始设备映射磁盘”呢?这也是一种可以热...

大别阿郎
今天
12
0
【AngularJS学习笔记】02 小杂烩及学习总结

本文转载于:专业的前端网站☞【AngularJS学习笔记】02 小杂烩及学习总结 表格示例 <div ng-app="myApp" ng-controller="customersCtrl"> <table> <tr ng-repeat="x in names | orderBy ......

前端老手
昨天
16
0
Linux 内核的五大创新

在科技行业,创新这个词几乎和革命一样到处泛滥,所以很难将那些夸张的东西与真正令人振奋的东西区分开来。Linux内核被称为创新,但它又被称为现代计算中最大的奇迹,一个微观世界中的庞然大...

阮鹏
昨天
20
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部