本文目录一览：
- 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
}
