关于c语言实现后序非递归遍历,前序遍历非递归实现

本文目录一览：

• 1、C语言中二叉树的非递归遍历，请教下这个程序怎么修改啊，万分感谢。。。
• 2、二叉树后序非递归遍历 c语言
• 3、求二叉树的非递归后序遍历的c语言代码？
• 4、用C语言代码如何实现非递归遍历的C？
• 5、求二叉树后序遍历非递归算法c语言版
• 6、c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

C语言中二叉树的非递归遍历，请教下这个程序怎么修改啊，万分感谢。。。

# include stdio.h

# include malloc.h

struct BTNode

{

int data;

struct BTNode * pLchild;//p是指针，L是左，child是孩子

struct BTNode * pRchild;

};

//函数声明

struct BTNode * CreateBTree(void);//创建树

void PreTraverseBTree(struct BTNode * pT);//先序遍历

void InTraverseBTree(struct BTNode * pT);//中序遍历

void PostTraverseBTree(struct BTNode * pT);//后续遍历

int main(void)

{

struct BTNode * pT = CreateBTree();

PreTraverseBTree(pT);

printf(“\n”);

InTraverseBTree(pT);

printf(“\n”);

PostTraverseBTree(pT);

return 0;

}

//创建树

struct BTNode * CreateBTree(void)

{

struct BTNode * pA = (struct BTNode * )malloc(sizeof(BTNode));

struct BTNode * pB = (struct BTNode * )malloc(sizeof(BTNode));

struct BTNode * pC = (struct BTNode * )malloc(sizeof(BTNode));

struct BTNode * pD = (struct BTNode * )malloc(sizeof(BTNode));

struct BTNode * pE = (struct BTNode * )malloc(sizeof(BTNode));

pA-data = ‘A’;

pB-data = ‘B’;

pC-data = ‘C’;

pD-data = ‘D’;

pE-data = ‘E’;

pA-pLchild = pB;

pA-pRchild = pC;

pB-pLchild = NULL;

pB-pRchild = NULL;

pC-pLchild = pD;

pC-pRchild = NULL;

pD-pLchild = NULL;

pD-pRchild = pE;

pE-pLchild = NULL;

pE-pRchild = NULL;

return pA;

}

//先序遍历

void PreTraverseBTree(struct BTNode * pT)

{ //先访问根节点，再先序访问左子树，最后先序访问右子树

if ( pT != NULL)

{

printf(“%c\n”,pT-data);//访问根节点

//pT-pLchild可以代表整个左子树

PreTraverseBTree(pT-pLchild);

PreTraverseBTree(pT-pRchild);

}

return;

}

//中序遍历

void InTraverseBTree(struct BTNode * pT)

{

if(pT != NULL )

{

if (NULL != pT-pLchild)

{

InTraverseBTree(pT-pLchild);

}

printf(“%c\n”,pT-data);

if (NULL != pT-pRchild)

{

InTraverseBTree(pT-pRchild);

}

}

return;

}

//后续遍历

void PostTraverseBTree(struct BTNode * pT)

{

if(pT != NULL )

{

if (NULL != pT-pLchild)

{

PostTraverseBTree(pT-pLchild);

}

if (NULL != pT-pRchild)

{

PostTraverseBTree(pT-pRchild);

}

printf(“%c\n”,pT-data);

}

return;

}

二叉树后序非递归遍历 c语言

楼主，后序遍历树为了看结果，需要先建立一个树，

由于非递归，所以要用到栈，

你程序中少了不少东西。

这里给你写全，是可以运行的。程序如下：

#include stdio.h

#include stdlib.h

struct tree

{

char data;

struct tree *lchild;

struct tree *rchild;

};

typedef struct tree * treptr;

treptr build(treptr t)//先序建树

{

char c;

c=getchar();

if(c==’#’)

{

t=NULL;

}

else

{

t=(treptr)malloc(sizeof(struct tree));

t-data=c;

t-lchild=build(t-lchild);

t-rchild=build(t-rchild);

}

return t;

}

void postdorder(treptr root)//这是递归实现

{

if (root!=NULL)

{

postdorder(root-lchild);

postdorder(root-rchild);

printf(“%c”,root-data);

}

}

struct stack

{

treptr *top,*base;

};

typedef struct stack *stackptr;

void init (stackptr s)//初始化栈

{

s-base=(treptr*)malloc(sizeof(treptr)*100);

s-top=s-base;

}

void push(stackptr s,treptr t)//入栈

{

*(s-top++)=t;

}

treptr pop(stackptr s)//弹出栈顶元素

{

treptr t;

t=*(–(s-top));

return t;

}

treptr gettop(stackptr s)//取栈顶元素

{

treptr *l=s-top-1;

return *(l);

}

void postorder(treptr t)//这是非递归后序实现

{

stackptr s=(stackptr)malloc(sizeof(struct stack));

treptr temp=t;

treptr p;

treptr lastvist=NULL;

init(s);

p=t;

while(p||s-top!=s-base)

{

while(p)

{

push(s,p);

p=p-lchild;

}

temp=gettop(s);

if(temp-rchild==NULL||temp-rchild==lastvist)

{

putchar(temp-data);

lastvist=pop(s);

}

else

p=temp-rchild;

}

}

int main()

{

treptr t=NULL;

t=build(t);

postdorder(t);

printf(“非递归后序遍历\n”);

postorder(t);

printf(“\n”);

return 0;

}

程序如上，可以运行。

我空间中有中序遍历的非递归实现。

不过给你写的是后序遍历的递归实现和非递归实现，它两个输出的结果是一致的。

输入

234##5#6##7##回车

就可以看到结果。

中序遍历及其对应树可以参考我空间中的文章

求二叉树的非递归后序遍历的c语言代码？

#includeiostream

#includestdio.h

#define N 10

using namespace std;

char *a;

typedef struct NODE{

char data;

struct NODE *lch, *rch,*parent;

} *BINTREE,Node;

void visit(char data){

printf(“%5c”,data);

}

void preorder(BINTREE T){ // 先根序周游

BINTREE stack[50];

BINTREE p;

p=T;

int s=0;

if(p==NULL)return;

while(1)

{ visit(p-data);

while(p-lch!=NULL) {

stack[++s]=p;

p=p-lch;

visit(p-data); }

// cout” “s;

while(1)

{ if((p=p-rch)!=NULL)

break;

if(s==0)

return;

p=stack[s–];

}

}

}

void inorder(BINTREE T)//中根序周游

{

Node *stack[100];

int top=0;

stack[0]=T;

while(top0 ||stack[top]!=NULL)

{

while(stack[top]!=NULL)

{

stack[++top]=stack[top]-lch ;

}

if(top0)

{

printf(“%5c”,stack[–top]-data );

stack[top]=stack[top]-rch ;

}

}

}

void posorder1(BINTREE T)//后根序周游

{

Node *stack[100];

int top=0;

int tag[100];

tag[0]=0;

stack[0]=T;

do

{

while(stack[top]!=NULL)

{

stack[++top]=stack[top]-lch ;

tag[top]=0;

}

while(tag[top-1]==1)

printf(“%5c”,stack[–top]-data );

if(top0)

{

stack[top]=stack[top-1]-rch ;

tag[top-1]=1;

tag[top]=0;

}

} while(top!=0);

}

BINTREE Create(){//先根序树的建立

BINTREE T;

char ch;

cinch;

cout” ch=”chendl;

if(ch==’#’)

T=NULL;

else{

if(!(T=(BINTREE )malloc(sizeof(Node))))

printf(“Error!”);

T-data=ch;

T-lch=Create();

T-rch=Create();

}

return T;

}

void main(){

freopen(“D:\\input.txt”,”r”,stdin);

BINTREE T;

T=Create();

cout”先根序遍历 “;

preorder(T);

coutendl;

cout”中根序遍历 “;

inorder(T);

coutendl;

cout”后根序遍历 “;

posorder1(T);

coutendl;

coutendl;

}

在D盘建立一个input.txt的文件，输入数的内容，输入顺序为先序根遍历的顺序，叶子节点的left和right用#代替即可。

用C语言代码如何实现非递归遍历的C？

给你编了个，先序递归建树的。

#include stdio.h

#include stdlib.h

#define STACK_INIT_SIZE 100

#define STACKINCREMENT 10

typedef struct BiTNode

{

char data;

struct BiTNode *lchild,*rchild;

} BiTNode,*BiTree;//树类型

typedef struct SqStack

{

BiTNode *base;

BiTNode *top;

int stacksize;

} SqStack;//栈类型

void InitStack(SqStack *S)//创建

{

S-base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));

S-top=S-base;

S-stacksize=STACK_INIT_SIZE;

}

void Push(SqStack *S,BiTNode e)//进栈

{

if(S-top-S-base=S-stacksize)

{

S-base=(BiTNode*)realloc(S-base,

(S-stacksize+STACKINCREMENT)*sizeof(BiTNode));

S-top=S-base+S-stacksize;

S-stacksize+=STACKINCREMENT;

}

*(S-top)=e;

S-top++;

}

BiTNode Pop(SqStack *S)//出栈

{

S-top –;

return *S-top;

}

int StackEmpty(SqStack *S)//判断栈是否非空

{

if(S-top == S-base )

return 1;

else

return 0;

}

BiTree CreateBiTree()//创建树（先序递归）

{

char p;BiTree T;

scanf(“%c”,p);

if(p==’ ‘)

T=NULL;

else

{

T=(BiTNode *)malloc(sizeof(BiTNode));

T-data=p;

T-lchild=CreateBiTree();

T-rchild=CreateBiTree();

}

return (T);

}

void PreOrder(BiTree T)//先序

{

SqStack S;

BiTree p=T;

InitStack(S);

if(p)

Push(S,*p);

while(!StackEmpty(S))

{

p=(BiTNode *)malloc(sizeof(BiTNode));

*p=Pop(S);

printf(“%c”,p-data);

if(p-rchild)

Push(S,*p-rchild);

if(p-lchild)

Push(S,*p-lchild);

}

}

void InOrder(BiTree T)//中序

{

SqStack S;

BiTree p=T;

InitStack(S);

while(p||!StackEmpty(S))

{

if(p)

{

Push(S,*p);

p=p-lchild;

}

else

{

p=(BiTNode *)malloc(sizeof(BiTNode));

*p=Pop(S);

printf(“%c”,p-data);

p=p-rchild;

}

}

}

void main()

{

BiTree Ta;

printf(“请创建树”);

Ta=CreateBiTree();

printf(“先序遍历:”);

printf(“\n”);

PreOrder(Ta);

printf(“\n”);

printf(“中序遍历:”);

printf(“\n”);

InOrder(Ta);

}

求二叉树后序遍历非递归算法c语言版

#includestdio.h

#includeiostream.h

#includestdlib.h

#define Maxsize 100

typedef int datatype;

typedef struct node

{

datatype data;

struct node* lchild;

struct node* rchild;

}BTNode;

void CreatBTNode(BTNode *b,char * str)

{

BTNode *p,*st[Maxsize];

int top=-1;

p=NULL;

b=NULL;

int j=0,k;

char ch=str[j];

while(ch!=’\0′)

{

switch(ch)

{

case ‘(‘:top++;st[top]=p;k=1;break;

case ‘)’:top–;break;

case ‘,’:k=2;break;

default:p=(BTNode *)malloc(sizeof(BTNode));

p-data=ch;p-lchild=p-rchild=NULL;

if(b==NULL)

{

b=p;

}

else

{

switch(k)

{

case 1:st[top]-lchild=p;break;

case 2:st[top]-rchild=p;break;

}

}

}

j++;ch=str[j];

}

}

void DispBTNode(BTNode *b)

{

if(b!=NULL)

{

printf(“%c”,b-data);

if(b-lchild!=NULL||b-rchild!=NULL)

{

printf(“(“);

DispBTNode(b-lchild);

if(b-rchild!=NULL)

printf(“,”);

DispBTNode(b-rchild);

printf(“)”);

}

}

}

BTNode *FindNode(BTNode *b,char x)

{

BTNode *p=NULL;

if(b==NULL)

{

return NULL;

}

else if(b-data==x)

{

return b;

}

else

{

p=FindNode(b-lchild,x);

if(p!=NULL)

{

return p;

}

else

{

return FindNode(b-rchild,x);

}

}

}

void PostOrderl(BTNode *b)

{

BTNode *st[Maxsize],*p;

int flag,top=-1;

if(b!=NULL)

{

do

{

while(b!=NULL)

{

top++;

st[top]=b;

b=b-lchild;

}

p=NULL;

flag=1;

while(top!=-1flag)

{

b=st[top];

if(b-rchild==p)

{

printf(“%c”,b-data);

top–;

p=b;

}

else

{

b=b-rchild;

flag=0;

}

}

}while(top!=-1);

printf(“\n”);

}

}

void main()

{

BTNode *b,*q;

char str[100];

printf(“您输入的二叉树为\n”);

scanf(“%s”,str);

CreatBTNode(b,str);

DispBTNode(b);

q=FindNode(b,’A’);

printf(“\n”);

printf(“*********************************\n”);

printf(“%c\n”,q-data);

printf(“它的后序序列为：\n”);

PostOrderl(b);

}

c语言实现二叉树的先序,中序,后序的递归和非递归算法和层次遍历算法

#includemalloc.h // malloc()等

#includestdio.h // 标准输入输出头文件，包括EOF(=^Z或F6)，NULL等

#includestdlib.h // atoi()，exit()

#includemath.h // 数学函数头文件，包括floor()，ceil()，abs()等

#define ClearBiTree DestroyBiTree // 清空二叉树和销毁二叉树的操作一样

typedef struct BiTNode

{

int data; // 结点的值

BiTNode *lchild,*rchild; // 左右孩子指针

}BiTNode,*BiTree;

int Nil=0; // 设整型以0为空

void visit(int e)

{ printf(“%d “,e); // 以整型格式输出

}

void InitBiTree(BiTree T)

{ // 操作结果：构造空二叉树T

T=NULL;

}

void CreateBiTree(BiTree T)

{ // 算法6.4：按先序次序输入二叉树中结点的值(可为字符型或整型，在主程中定义)，

// 构造二叉链表表示的二叉树T。变量Nil表示空(子)树。修改

int number;

scanf(“%d”,number); // 输入结点的值

if(number==Nil) // 结点的值为空

T=NULL;

else // 结点的值不为空

{ T=(BiTree)malloc(sizeof(BiTNode)); // 生成根结点

if(!T)

exit(OVERFLOW);

T-data=number; // 将值赋给T所指结点

CreateBiTree(T-lchild); // 递归构造左子树

CreateBiTree(T-rchild); // 递归构造右子树

}

}

void DestroyBiTree(BiTree T)

{ // 初始条件：二叉树T存在。操作结果：销毁二叉树T

if(T) // 非空树

{ DestroyBiTree(T-lchild); // 递归销毁左子树，如无左子树，则不执行任何操作

DestroyBiTree(T-rchild); // 递归销毁右子树，如无右子树，则不执行任何操作

free(T); // 释放根结点

T=NULL; // 空指针赋0

}

}

void PreOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数。修改算法6.1

// 操作结果：先序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ Visit(T-data); // 先访问根结点

PreOrderTraverse(T-lchild,Visit); // 再先序遍历左子树

PreOrderTraverse(T-rchild,Visit); // 最后先序遍历右子树

}

}

void InOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数

// 操作结果：中序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T)

{ InOrderTraverse(T-lchild,Visit); // 先中序遍历左子树

Visit(T-data); // 再访问根结点

InOrderTraverse(T-rchild,Visit); // 最后中序遍历右子树

}

}

void PostOrderTraverse(BiTree T,void(*Visit)(int))

{ // 初始条件：二叉树T存在，Visit是对结点操作的应用函数

// 操作结果：后序递归遍历T，对每个结点调用函数Visit一次且仅一次

if(T) // T不空

{ PostOrderTraverse(T-lchild,Visit); // 先后序遍历左子树

PostOrderTraverse(T-rchild,Visit); // 再后序遍历右子树

Visit(T-data); // 最后访问根结点

}

}

void main()

{

BiTree T;

InitBiTree(T); // 初始化二叉树T

printf(“按先序次序输入二叉树中结点的值,输入0表示节点为空，输入范例：1 2 0 0 3 0 0\n”);

CreateBiTree(T); // 建立二叉树T

printf(“先序递归遍历二叉树：\n”);

PreOrderTraverse(T,visit); // 先序递归遍历二叉树T

printf(“\n中序递归遍历二叉树：\n”);

InOrderTraverse(T,visit); // 中序递归遍历二叉树T

printf(“\n后序递归遍历二叉树：\n”);

PostOrderTraverse(T,visit); // 后序递归遍历二叉树T

}