非递归后序遍历二叉树

标签: 数据结构  数据结构  二叉树  算法

本文主要分为两个部分:包括二叉树的构造和非递归后序遍历,都比较有参考价值,这里将思路整理出来。
第一个部分主要是通过先序和中序构造二叉树,参考文章为https://blog.csdn.net/qq_35733751/article/details/80970664我觉得他的构造方式比较通用而且简洁,其实还有通过递归构造的方式我觉得比较麻烦,就没有采用。下为原理图:
原理图
主要思想:1.找到pre数组中先序序列中的根节点并创建树的根节点;2.通过匹配in数组中中序序列中的根节点,找到先序和中序中分割点位置;3.分别递归构建左子树和右子树。

bitnode *createbt1(char*pre,char*in,int n){
	if(n<=0){
		return NULL;
	}
	if(pre==NULL||in==NULL){
		return NULL;
	}
	
	int k;
	bitnode *s=NULL;
	char*p=NULL;
	
	s=(bitnode*)malloc(sizeof(bitnode));
	s->data=*pre;
	
	for(p=in;p<in+n;p++)
	  if(*p==*pre)
	   break;
	k=p-in;
	
	s->lchild = createbt1(pre+1,in,k);
    s->rchild = createbt1(pre+k+1,p+1,n-k-1);
    return s;
}

第二部分为非递归遍历二叉树,访问序列为左-右-中,主要思想:1.将左孩子节点全部入栈;2.如果栈不为空且右孩子节点未被访问,出栈并访问该节点;3.找到栈顶元素遍历其右子树;4.循环上述过程直到栈为空;这里需要设置flag标记以访问过的变量,左孩子若被访问过标记0,右孩子若被访问过标记1。这里参考了:https://www.cnblogs.com/hicjiajia/archive/2010/08/27/1810055.html有兴趣可以进去看看。

void postorder(bitree T){
    bitree p;
	p=T;   
	stack s;
	inistack(s);
	int flag[50];
	while(p||!isempty(s)){
		while(p){
			push(s,p);
			flag[s.top]=0;
			p=p->lchild; 
		}
		while(!isempty(s)&&flag[s.top]==1){
		    pop(s,p);
			visit(p);
		}
        if(!isempty(s)){
        	flag[s.top]=1;
        	p=gettop(s);
        	p=p->rchild;
		}
		else break;
	}
}

以下附上完整代码,通过了Dev c++调试了:

#include <stdio.h>
#include <stdlib.h>
#define elemtype int 
typedef struct BiTNode{
	elemtype data;
	struct BiTNode *lchild,*rchild; 
}bitnode,*bitree;
//*********************创建二叉树************************
bitnode *createbt1(char*pre,char*in,int n){
	if(n<=0){
		return NULL;
	}
	if(pre==NULL||in==NULL){
		return NULL;
	}
	
	int k;
	bitnode *s=NULL;
	char*p=NULL;
	
	s=(bitnode*)malloc(sizeof(bitnode));
	s->data=*pre;
	
	for(p=in;p<in+n;p++)
	  if(*p==*pre)
	   break;
	k=p-in;
	
	s->lchild = createbt1(pre+1,in,k);
    s->rchild = createbt1(pre+k+1,p+1,n-k-1);
    return s;
}

//*********************非递归后序遍历二叉树************************

typedef struct {
	bitree data[50];
	int top;
}stack;

void inistack(stack &s){
	s.top=-1;
}

void push(stack &s,bitree p){
    if(s.top==49) return;
	s.data[++s.top]=p;
}

void pop(stack &s,bitree &p){
	if(s.top==-1) return;
	p=s.data[s.top--];
} 

void visit(bitree p){
	printf("%c\n",p->data);
}

bool isempty(stack s){
	if(s.top==-1){
		return 1;
	}else
	    return 0;
}

bitree gettop(stack s){
   if(s.top==-1)
     return false;
   bitree p;  
   p=s.data[s.top];
   return p;	
}

void postorder(bitree T){
    bitree p;
	p=T;   
	stack s;
	inistack(s);
	int flag[50];
	while(p||!isempty(s)){
		while(p){
			push(s,p);
			flag[s.top]=0;
			p=p->lchild; 
		}
		while(!isempty(s)&&flag[s.top]==1){
		    pop(s,p);
			visit(p);
		}
        if(!isempty(s)){
        	flag[s.top]=1;
        	p=gettop(s);
        	p=p->rchild;
		}
		else break;
	}
}

int main(){
  char pre[]={'a','b','d','g','c','e','f'};
  char in[]={'d','g','b','a','e','c','f'};
  bitree s=createbt1(pre,in,7);
  postorder(s);
}

版权声明:本文为qq_27108973原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_27108973/article/details/104709263

智能推荐

模拟按键 —— 鼠标

背景 之前写自动化脚本的时候总是遇到一些很尴尬的问题: 跑脚本时模拟鼠标按键时,光标是真实的跑到了那个位置的,也就是说跑脚本的时候会很影响电脑的正常使用,导致不得不开一个虚拟机专门跑。 另外因为光标只有一个所以很难实现多线程去同时操作多个窗口,当线程1 模拟鼠标但还没有结束时,线程2 已经开始执行模拟操作,这就导致了线程1 的模拟操作被终止了,被迫之下只能开多个虚拟机(但实在太占用性能🙄) 解决...

Hibernate学习总结(一)

一、Hibernate简介 一个持久层的ORM框架。ORM:Object Relational Mapping(对象关系映射)。指的是将一个Java中的对象与关系型数据库中的表建立一种映射关系,从而操作对象就可以操作数据库中的表。 二、Hibernate入门 1、创建一个项目,引入jar包 hibernate用到的jar包 2、创建表 3、创建实体类 4、创建映射(*****) 映射需要通过XML...

Linux系统NFS

文章目录 1. nfs简介 1.1 nfs特点 1.2 使用nfs的好处 1.3 nfs的体系组成 1.4 nfs的应用场景 2. nfs工作机制 2.1 RPC 2.2 NIS 2.3 nfs工作机制 3. exports文件的格式 4. nfs管理 5. 作业 5.1手动搭建一个nfs服务器 5.1.1开放/nfs/shared目录,供所有用户查阅资料 5.1.2 开放/nfs/upload目...

关于java中String,StringBuffer,StringBuilder的区别以及StringBuffer,StringBuilder的安全性问题

这里的结果就是正确的然后我们来看他的append方法 它在前边加了一个synchronized来修饰,相当于同时只能有一个线程来访问他,这样就不会产生上边的问题但同时他的效率也就比StringBuilder低,...

Django连接现有mysql数据库

1、打开cmd后cd到项目位置 2、建立项目 django-admin startproject test2 3、编辑项目中的配置文件, mysite/settings.py ,告诉Django你的数据库连接参数和数据库名。具体的说,要提供 DATABASE_NAME , DATABASE_ENGINE , DATAB...

猜你喜欢

ShareSDK新浪微博登录时报错error:redirect_uri_mismatch

今天用 ShareSDK 做第三方登录的时候碰到个问题,明明在微博平台的应用审核已经通过了,但是调用登录接口的时候一直报错,错误如下: 出现这个错误是因为在微博开放平台上没有设置回调地址,或者设置的回调地址与本地XML中的地址不一致。 在sharesdk.xml文件当中对于微博的设置: 其中RedirectUrl为设置的回调地址,这里的地址必须要与微博开发平台设置的地址相同,否则就会出现上面的错误...

python解析网络封包方法

2019独角兽企业重金招聘Python工程师标准>>> 在使用Python解析网络数据包时,使用网络字节序解析,参见下表。 C语言的数据类型和Python的数据类型对照表请参见下表。 接下来对封包与解包进行举例说明。 version type id content unsigned short unsigned short unsigned int unsigned int 封包...

python3:时间方法,异常处理,系统文件相关模块(os)

文章目录 时间方法 time模块 时间表示方法: time模块的方法 datetime模块 异常处理 触发异常 创建mydiv.py脚本,要求如下: 创建myerror.py脚本,要求如下: os模块 实现ls -R(os.walk) os.path pickle模块 记账脚本 时间方法 time模块 时间表示方法: 时间戳:自1970-1-1 0:00:00到某一时间点之间的秒数 UTC时间:世...

负载均衡群集——LVS+DR模型

一、实验组成 调度器 192.168.100:41 web1 192.168.100:42 web2 192.168.100.43 NFS共享服务器 192.168.100.44 二、实验拓扑 三、实验配置 3.1在调度器配置:192.168.100.41 配置虚拟IP地址(VIP) 调整/proc响应参数 对于 DR 群集模式来说,由于 LVS 负载调度器和各节点需要共用 VIP 地址,应该关闭...

adb无线连接时appium找不到设备

问题描述 以前使用USB连接真机,运行appium时一直正常,连接参数如下: 最近为了方便,使用adb无线连接真机,adb版本为1.0.40,真机安卓版本10,连接后,通过adb devices能够查看到连接的设备: adb无线连接是正常的,但每次运行时appium都找不到无线连接的设备,陷入重启adb循环: 解决流程 1.因为是没找到设备,所以在appium连接参数中增加了"udid&...