C语言非递归后序遍历二叉树
作者:数星星的咚咚咚 发布时间:2023-12-13 18:05:45
标签:C语言,非递归,二叉树
本文实例为大家分享了C语言非递归后序遍历二叉树的具体代码,供大家参考,具体内容如下
法一:实现思路:一个栈 先按 根->右子树->左子树的顺序访问二叉树。访问时不输出。另一个栈存入前一个栈只进栈的结点。
最后输出后一个栈的结点数据。
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode{
char element;
struct TreeNode *left,*right;
}Tree,*BTree;
typedef struct StackNode{
BTree data;
struct StackNode *next;
}Stack,*PStack;
typedef struct{
PStack top;
}LinkStack,*PLinkStack;
//初始化空栈
PLinkStack Init_Stack(void){
PLinkStack S;
S=(PLinkStack)malloc(sizeof(LinkStack));
if(S){
S->top=NULL;
}
return S;
}
//压栈
void Push_Stack(PLinkStack S,BTree T){
PStack p;
p=(PStack)malloc(sizeof(Stack));
p->data=T;
p->next=S->top;
S->top=p;
}
//判空
int empty_Stack(PLinkStack S){
if(S->top){
return 0;
}else{
return 1;
}
}
//出栈
PStack Pop_Stack(PLinkStack S){
PStack q;
if(empty_Stack(S)){
return S->top;
}else{
q=S->top;
S->top=S->top->next;
}
return q;
}
//销毁栈
void DestroyStack(PLinkStack S){
PStack del;
while(S->top!=NULL){
del=S->top;
S->top=S->top->next;
free(del);
}
free(S);
}
BTree BuildTree(void){
char ch;
BTree node;
ch=getchar();
if(ch=='#'){
node=NULL;
}else{
node=(BTree)malloc(sizeof(Tree));
node->element=ch;
node->left=BuildTree();
node->right=BuildTree();
}
return node;
}
void NotRecursionPostOrder(BTree T){
PLinkStack S,CS;
S=Init_Stack();
CS=Init_Stack();
while(T || !empty_Stack(S)){
if(T){
Push_Stack(S,T);
Push_Stack(CS,T);
T=T->right;
}else{
T=Pop_Stack(S)->data;
T=T->left;
}
}
while(CS->top!=NULL){
printf("%c",CS->top->data->element);
CS->top=CS->top->next;
}
DestroyStack(CS);
}
int main(void){
BTree T;
T=BuildTree();
NotRecursionPostOrder(T);
return 0;
}
法二:实现思路。按先序遍历访问每一个结点。存入栈中,当为空时,就出立即栈(第一次出栈)。出栈后应该立即进栈,去访问进栈结点的右结点,这样可以保证先输出左、右结点,再输出根结点。二次进栈利用flag标记。
#include<stdio.h>
#include<stdlib.h>
typedef struct TreeNode {
char element;
int flag;
struct TreeNode *left, *right;
}Tree, *BTree;
typedef struct StackNode {
BTree data;
struct StackNode *next;
}Stack, *PStack;
typedef struct {
PStack top;
}LinkStack, *PLinkStack;
//初始化空栈
PLinkStack Init_Stack(void) {
PLinkStack S = (PLinkStack)malloc(sizeof(LinkStack));
if (S) {
S->top = NULL;
}
return S;
}
//压栈
void Push_Stack(PLinkStack S, BTree T) {
PStack p;
p = (PStack)malloc(sizeof(Stack));
p->data = T;
p->next = S->top;
S->top = p;
}
//判空
int empty_Stack(PLinkStack S) {
if (S->top) {
return 0;
}
else {
return 1;
}
}
//出栈
PStack Pop_Stack(PLinkStack S) {
PStack q = S->top;
S->top = S->top->next;
return q;
}
BTree BuildTree(void) {
BTree t;
char ch;
ch = getchar();
if (ch == '#') {
t = NULL;
}
else {
t = (BTree)malloc(sizeof(Tree));
t->element = ch;
t->left = BuildTree();
t->right = BuildTree();
}
return t;
}
void DestroyStack(PLinkStack S){
PStack p;
while(S->top){
p=S->top;
free(p);
S->top=S->top->next;
}
}
void NotRecursionPostOrder(BTree T) {
PLinkStack S;
S = Init_Stack();
while (T || !empty_Stack(S)) {
if (T) {
T->flag = 0;
Push_Stack(S, T);
T = T->left;
}
else {
T = Pop_Stack(S)->data;
if (T->flag == 0) {
T->flag = 1;
Push_Stack(S, T);
T = T->right;
}
else {
if (T->flag == 1) {
printf("%c", T->element);
T = NULL;
}
}
}
}
DestroyStack(S);//销毁栈
}
int main(void) {
BTree T;
T = BuildTree();
NotRecursionPostOrder(T);
return 0;
}
来源:http://blog.csdn.net/chendongqaq/article/details/70832303
0
投稿
猜你喜欢
- 本文实例讲述了Android编程之交互对话框。分享给大家供大家参考,具体如下:1. 在Android SDK中,虽然有许多的窗口,有些类似M
- Kotlin简介Kotlin是一种针对Java 平台的新编程语言。Kotlin简洁、安全、务实,并且专注于与Java代码的互操作性。它几乎可
- 配置文件概述:应用程序配置文件是标准的 XML 文件,XML 标记和属性是区分大小写的。它是可以按需要更改的,开发人员可以使用配置文件来更改
- 结构体概念在C#中,结构体是值类型,一般适用于表示类似Point、Rectangle、Color的对象值类型能够降低对堆的管理、使用。降低垃
- Java实现简单的类似QQ聊天工具,供大家参考,具体内容如下所使用到的知识点:java socket编程之TCP协议java Swing简单
- SpringSecurity 框架简介Spring 是非常流行和成功的 Java 应用开发框架,Spring Security 正是 Spr
- ServletContext 基础知识获取 ServletContext对象有两种方式可以获取:使用 servletconfig 对象获取使
- producer是生产者的意思:指生产数据的线程,consumer是消费者的意思:指的是使用数据的线程public class Produc
- 1. 并行和并发有什么区别?并行:多个处理器或多核处理器同时处理多个任务。并发:多个任务在同一个 CPU 核上,按细分的时间片轮流(交替)执
- 本文实例为大家分享了C#实现简单文本编辑器的具体代码,供大家参考,具体内容如下建立一个窗体文件,实现对文件的编辑保存和对txt文件的打开界面
- 控制json序列化/反序列化1. @JsonIgnoreProperties的用法@JsonIgnoreProperties(value =
- 我就废话不多说了,大家还是直接看代码吧~using UnityEngine;using UnityEngine.EventSystems;
- 这将会是一篇比较 * 的文章,当你想在某个人的生活中制造悲剧时你可能会去google搜索它。在Java的世界里,内存溢出仅仅只是你
- java 归并排序的实例详解归并排序 归并排序,指的是将两个已经排序
- /// 构造随机数 种子static int GetRandomSeed(){ byte[] byt
- 如果在类路径上添加了Spring Boot Security依赖项,则Spring Boot应用程序会自动为所有HTTP端点提供基本身份验证
- 数据库事务是后端开发中不可缺少的一块知识点。Spring为了更好的支撑我们进行数据库操作,在框架中支持了两种事务管理的方式: 编程式事务声明
- 前言:在 Java 语言中,并发编程都是依靠线程池完成的,而线程池的创建方式又有很多,但从大的分类来说,线程池的创建总共分为两大类:手动方式
- 那么Http协议中的Multipart是个什么东东?下面是摘抄http协议1.1的一段话:
- 简单使用redis-zset实现排行榜此方法实现一个根据某字段的查询次数进行排行,查询的次数越多排行越前(从大到小排序),适用于初学者1.添