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


猜你喜欢
- ThreadGroup的作用及方法ThreadGroup线程组,java对这个类的描述呢就是“线程组表示一组线程。此外,线程组还可以包括其他
- Android 界面刷新 Android提供了Invalidate方法实现界面刷新,但是Invalidate不能直接在线程中调用,
- 运行结果:模拟器图库就三张 没办法~画质挺感人~一个隐式意图布局文件:<RelativeLayout xmlns:android=&q
- 关于链表链表是有序的列表链表是以节点的方式来存储每个节点包含data域,next域(指向下一个节点)分带头节点的链表和没有头节点的链表定义一
- 1. 前言什么是特殊矩阵?C++,一般使用二维数组存储矩阵数据。在实际存储时,会发现矩阵中有许多值相同的数据或有许多零数据,且分布呈现出一定
- 带搜索的ComboBox就是给ComboBox一个依赖属性的ItemSource,然后通过数据源中是否包含要查询的值,重新给ComboBox
- 这篇文章主要介绍了Spring Cloud Hystrix异常处理方法详解,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参
- 1.异步委托开启线程public class Program { public static void
- 前段时间接到一个Web应用自动生成Word的需求,现整理了下一些关键步骤拿来分享一下。思路:(注:这里只针对WORD2003版本,其它版本大
- 访问Controller返回400BadRequest问题SpringMVC使用自定义类型接收参数时, form提交会返回400 Bad R
- 第一节:服务端初始化首先看下在我们用户代码中netty的使用最简单的一个demo://创建boss和worker线程(1)EventLoop
- 前言:使用 interrupt 来通知线程停止运行,而不是强制停止!普通情况停止线程public class Right
- 在网上有非常多通过射线方式实现的人物行走控制脚本,可是假设仅仅是想通过键盘按键来控制的话。比方进行第三人称视角控制,事实上仅仅须要进行简单的
- •readonly和const都是用来标识常量的[1]。•const可用于修饰class的field或者一个局部变量(local varia
- 在平时的工作中,估计大多数都做过轮询调度的任务,比如定时轮询数据库同步,定时邮件通知等等。大家通过windows计划任务,windows服务
- 依赖SpringBoot版本:2.4.2 <dependencies> &
- Unicode有四种编码格式,UTF-8, UTF-16,UTF-32,UTF-7。字符编码类,ASCIIEncoding ,UTF7Enc
- 目录三大只读类型介绍使用 IReadOnlyList 替换 List使用 IEnumberable 接口集合 表示一组可用于获取和存储的对象
- 本文实例讲述了Android编程实现禁止系统锁屏与解锁亮屏的方法。分享给大家供大家参考,具体如下:需求:某个时刻任务执行完毕,关闭屏幕,某时
- 本文实例为大家分享了Java实现 * 系统的具体代码,供大家参考,具体内容如下父类Vehiclepublic abstract class