C语言二叉树非递归遍历问题

问题描述

C语言二叉树非递归遍历问题

#include"stdio.h"
#include"stdlib.h"

#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef int Status;
typedef struct LNode{
BiTree data;
struct LNode *next;
}LNode;
typedef struct{
LNode *top;
}LStack;

int main(){
Status CreateBiTree(BiTree &T);
Status Pop(LStack &S);
Status Init_Stack(LStack &S);
Status Push(LStack &S,BiTree T);
Status StackEmpty(LStack S);
Status PreOrderTraverse(BiTree T);
void visit(TElemType data);

BiTree T;
printf("创建树中...");
if(CreateBiTree(T))
    printf("创建成功
");
PreOrderTraverse(T);
return 0;

}

Status CreateBiTree(BiTree &T){
TElemType ch;
scanf("%c",&ch);
if(ch==' ')
T=NULL;
else{
T=(BiTNode *)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}

Status Init_Stack(LStack &S){
LNode *p;
p=(LNode *)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
p->next=NULL;
S.top=p;
return OK;
}

Status Push(LStack &S,BiTree T){
LNode *p;
p=(LNode *)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
S.top->data = T;
p->next = S.top;
S.top = p;
return OK;
}

Status StackEmpty(LStack S){
if(S.top==NULL)
return 1;
else
return 0;
}

void visit(TElemType data){
printf("%c
",data);
}

BiTree Pop(LStack &S){
BiTree tran;
LNode *t;
tran=S.top->data;
t=S.top;
S.top=S.top->next;
free(t);
return tran;
}

Status PreOrderTraverse(BiTree T){
LStack S;
Init_Stack(S);
BiTree p;
p=T;
while(p||!(StackEmpty(S))){
if(p){
Push(S,p);
p=p->lchild;
}
else{
p=Pop(S);
visit(p->data);
p=p->rchild;
}
}
return OK;
}

//源代码如上，程序运行，我输入ABC DE G F

建立二叉树那一段可以运行，到了二叉树遍历的时候程序无法运行自动关闭，麻烦各位了！

解决方案

#include"stdio.h"
#include"stdlib.h"
#include"string.h"

#define OK 1
#define ERROR 0
#define OVERFLOW -1
typedef char TElemType;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

typedef int Status;
typedef struct LNode{
BiTree data;
struct LNode *next;
}LNode;
typedef struct{
LNode *top;
}LStack;

int main(){
Status CreateBiTree(BiTree &T);
Status Pop(LStack &S);
Status Init_Stack(LStack &S);
Status Push(LStack &S,BiTree T);
Status StackEmpty(LStack S);
Status PreOrderTraverse(BiTree T);
void visit(TElemType data);

BiTree T;
printf("创建树中...");
if(CreateBiTree(T))
    printf("创建成功
");
PreOrderTraverse(T);
return 0;

}

Status CreateBiTree(BiTree &T){
TElemType ch;
if((ch=getchar())=='
')
T=NULL;
else{
T=(BiTNode *)malloc(sizeof(BiTNode));
if(!T)
exit(OVERFLOW);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return OK;
}

Status Init_Stack(LStack &S){
LNode *p;
p=(LNode *)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
p->next=NULL;
S.top=p;
return OK;
}

Status Push(LStack &S,BiTree T){
LNode *p;
p=(LNode *)malloc(sizeof(LNode));
if(!p)
exit(OVERFLOW);
S.top->data = T;
p->next = NULL;
S.top = p;
return OK;
}

Status StackEmpty(LStack S){
if(S.top->next==NULL)
return 1;
else
return 0;
}

void visit(TElemType data){
printf("%c
",data);
}

BiTree Pop(LStack &S){
BiTree tran;
LNode *t;
tran=S.top->data;
t=S.top;
S.top=S.top->next;
free(t);
return tran;
}

Status PreOrderTraverse(BiTree T){
LStack S;
Init_Stack(S);
BiTree p;
p=T;
while(p||!(StackEmpty(S))){
if(p){
Push(S,p);
visit(p->data);
p=p->lchild;
}
else{
p=Pop(S);
p=p->rchild;
}
}
return OK;
}


每次都只能输出ABC，求教。。

解决方案二：

二叉树的非递归遍历C语言实现
二叉树非递归遍历C语言实现
二叉树遍历的c语言非递归实现

时间： 2024-10-18 15:54:01

C语言二叉树非递归遍历问题的相关文章

求大神看看，C语言二叉树非递归遍历问题 ，最后输出正确，然后在程序崩溃

问题描述 求大神看看,C语言二叉树非递归遍历问题 ,最后输出正确,然后在程序崩溃 #include #include #include typedef struct TNode { char date; struct TNode *lchild,*rchild; }TNode,*BiTree; typedef struct { BiTree top; BiTree *base; int stacksize; }Stack; int createBiTree(BiTree &S){ char ch

C++实现二叉树非递归遍历方法实例总结_C 语言

一般来说,二叉树的遍历是C++程序员在面试中经常考察的,其实前中后三种顺序的遍历都大同小异,自己模拟两个栈用笔画画是不难写出代码的.现举一个非递归遍历的方法如下,供大家参考. 具体代码如下: class Solution { public: vector<int> preorderTraversal(TreeNode *root) { vector<int> out; stack<TreeNode*> s; s.push(root); while(!s.empty()

采用栈数据结构的二叉树非递归遍历

[前言]树的遍历,根据访问自身和其子节点之间的顺序关系,分为前序,后序遍历.对于二叉树,每个节点至多有两个子节点(特别的称为左,右子节点),又有中序遍历.由于树自身具有的递归性,这些遍历函数使用递归函数很容易实现,代码也非常简洁.借助于数据结构中的栈,可以把树遍历的递归函数改写为非递归函数.   在这里我思考的问题是,很显然,循环可以改写为递归函数.递归函数是否借助栈这种数据结构改写为循环呢.因为函数调用中,call procedure stack 中存储了流程的 context,调用和返回相当

C语言二叉树的非递归遍历实例分析_C 语言

本文以实例形式讲述了C语言实现二叉树的非递归遍历方法.是数据结构与算法设计中常用的技巧.分享给大家供大家参考.具体方法如下: 先序遍历: void preOrder(Node *p) //非递归 { if(!p) return; stack<Node*> s; Node *t; s.push(p); while(!s.empty()) { t=s.top(); printf("%d\n",t->data); s.pop(); if(t->right) s.pus

二叉树递归和非递归遍历

二叉树是一种非常重要的数据结构,很多其他数据机构都是基于二叉树的基础演变过来的.二叉树有前.中.后三种遍历方式,因为树的本身就是用递归定义的,因此采用递归的方法实现三种遍历,不仅代码简洁且容易理解,但其开销也比较大,而若采用非递归方法实现三种遍历,则要用栈来模拟实现(递归也是用栈实现的).下面先简要介绍三种遍历方式的递归实现,再详细介绍三种遍历方式的非递归实现. 一.三种遍历方式的递归实现(比较简单,这里不详细讲解) 1.先序遍历--按照"根节点-左孩子-右孩子"的顺序进行访问. vo

有关后序非递归遍历二叉树的问题

问题描述 有关后序非递归遍历二叉树的问题 void show_LRD(tree LRD) { //后序非递归遍历二叉树 int otherstack[max];//辅助栈,用于检测出栈时是否已经遍历右子树 int *othertop,*otherbottom; tree temp; othertop=otherbottom=otherstack; while(LRD||!emptystack()) { while(LRD) { while(LRD) { inputstack(LRD); *oth

数据结构算法-菜鸟问，二叉树的非递归遍历问题

问题描述 菜鸟问,二叉树的非递归遍历问题 二叉树的非递归遍历跟着代码走一遍可以看懂是怎么实现的,想问一下利用栈非递归实现遍历是怎么想到的,代码是怎么来的呢 解决方案 我理解你的问题,意思是想问二叉树遍历是怎么出来这种算法的?,这是一个叫哈弗曼的人首先提出的二叉树概念,你要是想追溯本源就去了解他.. 我觉得学算法,_最主要就是要瞄准算法怎么解决问题,而不是去讨论起源,_ 就好比牛顿发现了行星轨道之间运转的规律--万有引力,,但是并不清楚为啥是遵循这样运动的.... 解决方案二: 我觉得你应该先把二

c语言-C语言版非递归马踏棋盘·死循环了·求大神解答·小弟新手求助

问题描述 C语言版非递归马踏棋盘·死循环了·求大神解答·小弟新手求助 这是出现死循环的代码bool solution(Move move, Pos &beginPos){ if(!move) { printf("solution Failed!"); return false; } int chessBoard[8][8] = {0}; push(move, beginPos); chessBoard[beginPos.mX][beginPos.mY] = 1; int ste

深入理解二叉树的非递归遍历_C 语言

二叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的.对于二叉树,有前序.中序以及后序三种遍历方法.因为树的定义本身就是递归定义,因此采用递归的方法去实现树的三种遍历不仅容易理解而且代码很简洁.而对于树的遍历若采用非递归的方法,就要采用栈去模拟实现.在三种遍历中,前序和中序遍历的非递归算法都很容易实现,非递归后序遍历实现起来相对来说要难一点.一.前序遍历前序遍历按照"根结点-左孩子-右孩子"的顺序进行访问.1.递归实现 复制代码 代码如下: void preO