關於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

}