二叉树非递归遍历代码（用J**A语言实现二叉树的层次遍历的非递归算法及查找算法）

本文目录

• 用J**A语言实现二叉树的层次遍历的非递归算法及查找算法
• 二叉树中序遍历非递归算法(c语言实现）
• 求C语言非递归建立二叉树和非递归非递归先序遍历的完整代码
• 二叉树先序非递归遍历C语言算法
• 如何编程实现二叉树的非递归遍历
• 二叉树后序遍历非递归算法
• 二叉树的后序非递归遍历
• 求一个关于二叉树非递归遍历的程序
• 大家看看这个非递归中序遍历二叉树代码什么问题，其他都没问题
• 二叉树的非递归遍历

用J**A语言实现二叉树的层次遍历的非递归算法及查找算法

分块查找
typedef struct
{ int key;
int link;
}SD;
typedef struct
{ int key;
float info;
}JD;
int blocksrch(JD r,int b,int k,int n)
{ int i=1,j;
while((k》nd.key)&&(i《=b) i++;
if(i》b) { printf("\nNot found");
return(0);
}
j=nd.link;
while((j《n)&&(k!=r.key))
j++;
if(k!=r.key) { j=0; printf("\nNot found"); }
return(j);
}
哈希查找算法实现
#define M 100
int h(int k)
{ return(k%97);
}
int slbxxcz(int t,int k)
{ int i,j=0;
i=h(k);
while((j《M)&&(t!=0))
j++;
i=(i+j)%M;
if(t==k) return(i);
else return(-1);
}
int slbxxcr(int t,int k)
{ int i,j=0;
i=h(k);
while((j《M)&&(t》0))
j++;
if(j==M) return(0);
i=(i+j)%M;
if(t《=0)
{ t=k; return(1); }
if(t==k) return(1);
}
int slbxxsc(int t,int k)
{ int i,j=0;
i=h(k);
while((j《M)&&(t!=0))
j++;
i=(i+j)%M;
if(t==k)
{ t=-1; return(1); }
return(0);
}
顺序查找
#define M 500
typedef struct
{ int key;
float info;
}JD;
int seqsrch(JD r,int n,int k)
{ int i=n;
r.key=k;
while(r.key!=k)
i--;
return(i);
}
折半查找
int binsrch(JD r,int n,int k)
{ int low,high,mid,found;
low=1; high=n; found=0;
while((low《=high)&&(found==0))
{ mid=(low+high)/2;
if(k》r.key) low=mid+1;
else if(k==r.key) found=1;
else high=mid-1;
}
if(found==1)
return(mid);
else
return(0);
}
虽然都是C++写的，万变不离其中，J**A我现在 刚学习，就不献丑了

二叉树中序遍历非递归算法(c语言实现）

#include "stdio.h"
#include "stdlib.h"
#include "string.h"
#define null 0
struct node
{
char data;
struct node *lchild;
struct node *rchild;
};
//先序，中序 建树
struct node *create(char *pre,char *ord,int n)
{
struct node * head;
int ordsit;
head=null;
if(n《=0)
{
return null;
}
else
{
head=(struct node *)malloc(sizeof(struct node));
head-》data=*pre;
head-》lchild=head-》rchild=null;
ordsit=0;
while(ord!=*pre)
{
ordsit++;
}
head-》lchild=create(pre+1,ord,ordsit);
head-》rchild=create (pre+ordsit+1,ord+ordsit+1,n-ordsit-1);
return head;
}
}
//中序递归遍历
void inorder(struct node *head)
{
if(!head)
return;
else
{
inorder(head-》lchild );
printf("%c",head-》data );
inorder(head-》rchild );
}
}
//中序非递归遍历
void inorder1(struct node *head)
{
struct node *p;
struct node *stack;
int top=0;

p=head;
while(p||top!=0)
{
while (p)
{
stack=p;
p=p-》lchild ;
}
p=stack;
printf("%c ",p-》data );
p=p-》rchild ;
}
}
//主函数
int main()
{
struct node * head;
char pre;
int n;
gets(pre);
gets(ord);
n=strlen(pre);
head=create(pre,ord,n);
inorder(head);
printf("\n");
inorder1(head);
printf("\n");
}
//测试事例；
/*
-+a*b%cd/ef
a+b*c%d-e/f
*/
几个月前自己编写，原版
vc++ 6.0实验通过
怎么样，老板，第一次上百度知道，好激动
给点面子
给分！给分啊

求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语言算法

#include "stdio.h"
#include "stdlib.h"
#define STACK_INIT_SIZE 10 //栈的初始长度
#define STACKINCREMENT 5 //栈的追加长度
typedef struct bitree{
char data;
struct bitree *lchild,*rchild;
}bitree; //二叉树结点定义
typedef struct {
bitree **base;
bitree **top;
int stacksize;
}sqstack; // 链栈结点定义top栈顶 base栈底 且栈元素是指向二叉树结点的二级指针
//建立一个空栈
int initstack(sqstack *s)
{s-》base=(bitree *)malloc(STACK_INIT_SIZE*sizeof(bitree)); //栈底指向开辟空间
if(!s-》base) exit(1); //抛出异常
s-》top=s-》base; //栈顶=栈尾 表示栈空
s-》stacksize=STACK_INIT_SIZE; //栈长度为开辟空间大小
return 1;
}
//进栈
int push(sqstack *s,bitree *e)
{if(s-》top-s-》base》=s-》stacksize) //如果栈满 追加开辟空间
{s-》base=(bitree *)realloc (s-》base,(s-》stacksize+STACKINCREMENT)* sizeof(bitree));
if(!s-》base) exit(1); //抛出异常
s-》top=s-》base+s-》stacksize; //感觉这一句没用
s-》stacksize+=STACKINCREMENT;}
*(s-》top)=e;s-》top++; //进栈 栈顶后移
return 1;
}
//出栈
int pop(sqstack *s,bitree **e)
{if(s-》top==s-》base) return 0; //栈空 返回0
--s-》top;*e=*(s-》top); //栈顶前移 取出栈顶元素给e
return 1;}
//取栈顶
int gettop(sqstack *s,bitree **e) //去栈顶元素 注意top指向的是栈顶的后一个
{if(s-》top==s-》base) return 0; //所以 s-》top-1
*e=*(s-》top-1);
return 1;
}
/*------------------------非递归-----先序建立二叉树----------------------------------*/
bitree *createprebitree()
{char ch;bitree *ht,*p,*q;
sqstack *s;
s=malloc(sizeof(bitree)); //加上这一句为s 初始化开辟空间
ch=getchar();
if(ch!=’#’&&ch!=’\n’) /* 输入二叉树先序顺序 是以完全二叉树的先序顺序
不是完全二叉树的把没有的结点以#表示 */
{ht=(bitree *)malloc(sizeof(bitree));
ht-》data=ch;
ht-》lchild=ht-》rchild=NULL;
p=ht;
initstack(s);
push(s,ht); //根节点进栈
while((ch=getchar())!=’\n’) // 算
{if(ch!=’#’) {q=(bitree *)malloc(sizeof(bitree)); // 法
q-》data=ch; //
if(p==*(s-》top-1)) p-》lchild=q; // 核
else p-》rchild=q; //
push(s,q);p=q; // 心
} //
else {if(p==*(s-》top-1)) p-》lchild=NULL; // 的
else p-》rchild=NULL; //
pop(s,&p);} // 步
//
} // 骤
return ht;
}
else return NULL;
}
/*--------------------------递归---------先序建立二叉树-------------------------------*/
void CreateBiTree(bitree **T) {
//按先序次序输入二叉树中的结点的值（一个字符），空格字符表示空树，
//构造二叉链表表示二叉树
char ch;
scanf("%c",&ch);
if(ch==’#’) *T=NULL;
else{
*T=(bitree * )malloc(sizeof(bitree));
if(!*T) exit(1);
(*T)-》data=ch; //生成根结点
CreateBiTree(&(*T)-》lchild); //构造左子树
CreateBiTree(&(*T)-》rchild); //构造右子树
}
}
/*--------------------------非递归-------中序建立二叉树-------------------------------*/
/*--------------------------递归---------中序建立二叉树-------------------------------*/
/*--------------------------非递归-------后序建立二叉树-------------------------------*/
/*--------------------------递归---------后序建立二叉树-------------------------------*/
/*-----------------------非递归------先序输出二叉树------------------------------*/
void preordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);printf("%c",h-》data);h=h-》lchild;}
else{pop(&m,&h);
h=h-》rchild;}
}
}
/*------------------------非递归-----中序输出二叉树----------------------------*/
void inordertraverse(bitree *h)
{sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {push(&m,h);h=h-》lchild;}
else {
pop(&m,&h);
printf("%c",h-》data);
h=h-》rchild;
}
}
}
/*---------------------非递归----后序遍历二叉树----------------------------------*/
void postordertraverse(bitree *h)
{
sqstack m;
initstack(&m);
while(h||m.base!=m.top)
{if(h) {
push(&m,h);
h=h-》lchild;}
else {
bitree *r; //使用r结点表示访问了右子树 代替标志域
gettop(&m,&h);
if(h-》rchild&&h-》rchild!=r)
{h=h-》rchild;
push(&m,h);
h=h-》lchild;}
else{pop(&m,&h);
printf("%c",h-》data);
r=h;h=NULL;}
}
}
}
//层次遍历二叉树 用队列 哈哈以后做
/*-------------------------------主过程-------------------------------*/
int main()
{bitree *ht;
printf("先序非递归建立一个二叉树:");
if((ht=createprebitree())!=NULL) //非递归建立
//CreateBiTree(&ht);
//if(ht!=NULL) //递归建立
{
printf("先序遍历输出二叉树:");
preordertraverse(ht);
putchar(’\n’);
printf("中序遍历输出二叉树:");
inordertraverse(ht);
putchar(’\n’);
printf("后序遍历输出二叉树:");
postordertraverse(ht);
putchar(’\n’);
}
else printf("空二叉树\n");
}

如何编程实现二叉树的非递归遍历

前序遍历按照“根结点-左孩子-右孩子”的顺序进行访问。
1.递归实现
void preOrder1(BinTree *root) //递归前序遍历
{
if(root!=NULL)
{
cout《《root-》data《《" ";
preOrder1(root-》lchild);
preOrder1(root-》rchild);
}
}
2.非递归实现
根据前序遍历访问的顺序，优先访问根结点，然后再分别访问左孩子和右孩子。即对于任一结点，其可看做是根结点，因此可以直接访问，访问完之后，若其左孩子不为空，按相同规则访问它的左子树；当访问其左子树时，再访问它的右子树。因此其处理过程如下：
对于任一结点P：
1)访问结点P，并将结点P入栈;
2)判断结点P的左孩子是否为空，若为空，则取栈顶结点并进行出栈操作，并将栈顶结点的右孩子置为当前的结点P，循环至1);若不为空，则将P的左孩子置为当前的结点P;
3)直到P为NULL并且栈为空，则遍历结束。
void preOrder2(BinTree *root) //非递归前序遍历
{
stack《BinTree*》 s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
cout《《p-》data《《" ";
s.push(p);
p=p-》lchild;
}
if(!s.empty())
{
p=s.top();
s.pop();
p=p-》rchild;
}
}
}
二.中序遍历
中序遍历按照“左孩子-根结点-右孩子”的顺序进行访问。
1.递归实现
void inOrder1(BinTree *root) //递归中序遍历
{
if(root!=NULL)
{
inOrder1(root-》lchild);
cout《《root-》data《《" ";
inOrder1(root-》rchild);
}
}
2.非递归实现
根据中序遍历的顺序，对于任一结点，优先访问其左孩子，而左孩子结点又可以看做一根结点，然后继续访问其左孩子结点，直到遇到左孩子结点为空的结点才进行访问，然后按相同的规则访问其右子树。因此其处理过程如下：
对于任一结点P，
1)若其左孩子不为空，则将P入栈并将P的左孩子置为当前的P，然后对当前结点P再进行相同的处理；
2)若其左孩子为空，则取栈顶元素并进行出栈操作，访问该栈顶结点，然后将当前的P置为栈顶结点的右孩子；
3)直到P为NULL并且栈为空则遍历结束
void inOrder2(BinTree *root) //非递归中序遍历
{
stack《BinTree*》 s;
BinTree *p=root;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p=p-》lchild;
}
if(!s.empty())
{
p=s.top();
cout《《p-》data《《" ";
s.pop();
p=p-》rchild;
}
}
}

二叉树后序遍历非递归算法

#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("非递归后序遍历\
");
postorder(t);
printf("\
");
return
0;
}
程序如上，可以运行。
我空间中有中序遍历的非递归实现。
不过给你写的是后序遍历的递归实现和非递归实现，它两个输出的结果是一致的。
输入
234##5#6##7##回车
就可以看到结果。
中序遍历及其对应树可以参考我空间中的文章
***隐藏网址***

二叉树的后序非递归遍历

struct StackNode
{
BinTreeNode *pTreeNode ;
TAG tag ;
StackNode(BinTreeNode *pnode = NULL):pTreeNode(pnode), tag(LEFT){}
} ;
void NonRecursivePostorder(BinTreeNode *t)
{
stack《StackNode》 s ;
StackNode stackNode ;
BinTreeNode *p = t ;
do
{
while(p != NULL)
{
stackNode.pTreeNode = p ;
stackNode.tag = LEFT ;
s.push(stackNode) ;
p = p-》left ;
}
bool continueFlag = true ;
while(!s.empty() && continueFlag)
{
stackNode = s.top() ;
s.pop() ;
p = stackNode.pTreeNode ;
switch(stackNode.tag)
{
case LEFT:
stackNode.tag = RIGHT ;
s.push(stackNode) ;
continueFlag = false ;
p = p-》right ;
break ;
case RIGHT:
cout 《《 p-》data ;
break ;
}
}
}while(!s.empty()) ;
}

求一个关于二叉树非递归遍历的程序

#include 《stdio.h》
#include 《stdlib.h》
#include 《malloc.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-》lchild);
T-》rchild=CreateBiTree(T-》rchild);
}
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 PostOrder(BiTree T)//后序
{
SqStack S;
BiTNode p, *l, *r;
InitStack(&S);
Push(&S, *T);
while(!StackEmpty(&S))
{
p = Pop(&S);
l = p.lchild;
r = p.rchild;
if (l == NULL && r == NULL)
{
printf("%c", p.data);
}
else
{
p.lchild = NULL;
p.rchild = NULL;
Push(&S, p);
if (r != NULL) Push(&S, *r);
if (l != NULL) Push(&S, *l);
}
}
}
void main()
{
BiTree Ta;int a;
printf("请创建树");
Ta=CreateBiTree();
printf("请选择：\n");
scanf("%d",&a);
if(a==1)
{
printf("先序遍历:");
printf("\n");
PreOrder(Ta);
}
if(a==2)
{
printf("中序遍历:");
printf("\n");
InOrder(Ta);
}
if(a==3)
{
printf("后序遍历:");
printf("\n");
PostOrder(Ta);
}
}

大家看看这个非递归中序遍历二叉树代码什么问题，其他都没问题

测试结果: AB#D##C##(递归法)先序遍历序列: A B D C(递归法)中序遍历序列: B D A C(递归法)后序遍历序列: D B C A你好0B D A C你好1 二叉树示意图: A / \ B C \ D 二叉树(带扩展序列)示意图: A / \ B C / \ / \# D # # / \ # # 注:输入的字符串 AB#D##C## 是先序扩展序列,#表示空结点. #include《stdio.h》#include《stdlib.h》typedef struct tree{ char data; struct tree *lc,*rc;} tree,*T0;typedef struct list{ //原代码tree dat; tree *dat; //改用指针 struct list *next;}list,*l;typedef struct zhan{ list *top; int count;}zhan; //创建二叉树: 先序扩展序列+递归法void create_tree(T0 *T){ char ch=getchar(); if(ch==’#’) *T=NULL; else { *T=(tree*)malloc(sizeof(tree)); (*T)-》data=ch; create_tree(&((*T)-》lc)); create_tree(&((*T)-》rc)); }}//原代码/*void creat_tree (T0 T){ char ch=getchar(); if(ch==’#’) T=NULL; else { T=(tree*)malloc(sizeof(tree)); T-》data=ch; creat_tree(T-》lc); creat_tree(T-》rc); }}*/ //原代码void push(zhan *s, tree p)//入栈,输入参数改用指针tree *pvoid push(zhan *s, tree *p){ list *v=(list*)malloc(sizeof(list)); v-》dat=p; v-》next=s-》top; s-》top=v; s-》count++;}//原代码int pop(zhan *s,tree *e)//出栈,去掉输入参数,改用返回值tree *tree *pop(zhan *s){ tree *e; list *p=s-》top; ////////测试 if(s-》top==NULL) { return NULL; } //////// s-》top=s-》top-》next; e=p-》dat; s-》count--; ****(p); return e;}//中序遍历(非递归)void msearch_tree(T0 T){ T0 p=T; zhan *s=(zhan*)malloc(sizeof(list)); s-》top=NULL; s-》count=0; while(p!=NULL || s-》count!=0) { while(p!=NULL) { push(s,p); p=p-》lc; } if(s-》count!=0) { p=pop(s); printf("%c ",p-》data); p=p-》rc; } } if(s!=NULL) { ****(s); } //原代码 /* while(p||!(s-》count==0)) if(p-》lc) { push(s,*p); p=p-》lc; } else { printf("%c",p-》data); p=p-》rc; while(!p||!(s-》count==0)) { pop(s,p); printf("%c",p-》data); p=p-》rc; } } */} void preOrder(T0 T) //先序遍历(递归法){ if(T != NULL) { printf("%c ",T-》data); preOrder(T-》lc); preOrder(T-》rc); }}void inOrder(T0 T) //中序遍历(递归法){ if(T != NULL) { inOrder(T-》lc); printf("%c ",T-》data); inOrder(T-》rc); }}void postOrder(T0 T) //后序遍历(递归法){ if(T != NULL) { postOrder(T-》lc); postOrder(T-》rc); printf("%c ",T-》data); }} int main(){ //原代码T0 t=(T0)malloc(sizeof(tree)); //原代码creat_tree(t); T0 t; create_tree(&t); printf("(递归法)先序遍历序列: "); preOrder(t); printf("\n"); printf("(递归法)中序遍历序列: "); inOrder(t); printf("\n"); printf("(递归法)后序遍历序列: "); postOrder(t); printf("\n"); printf("你好0\n"); msearch_tree(t); printf("\n你好1\n"); system("pause"); return 0;}

二叉树的非递归遍历

#include《stdio.h》
#include《stdlib.h》
#include《malloc.h》
#include《math.h》
typedef struct BiTNode
{
int data;
BiTNode *lchild,*rchild; // 左右孩子指针
}BiTNode,*BiTree;
void visit(int e)
{
printf("-》%d",e);
}
void InitBiTree(BiTree &T)// 操作结果：构造空二叉树T
{
T=NULL;
}
void CreateBiTree(BiTree &T)
//按先序次序输入二叉树中结点的值,构造二叉链表表示的二叉树T。变量Nil表示空(子)树。
{
int number;
scanf("%d",&number); // 输入结点的值
if(number==0) // 结点的值为空
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); // 递归销毁右子树，如无右子树，则不执行任何操作
****(T); // 释放根结点
T=NULL; // 空指针赋0
}
}
void PreOrderTraverse(BiTree T,void(*Visit)(int))
//二叉树T存在，Visit是对结点操作的应用函数,先序递归遍历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()
{
char m;
BiTree T;
InitBiTree(T); // 初始化二叉树T
do{
printf("\n");
printf("##################二叉树的基本操作###########################\n");
printf("×××××××××1.二叉树的创建××××××××××××××\n");
printf("×××××××××2.先序递归遍历二叉树×××××××××××\n");
printf("×××××××××3.中序递归遍历二叉树×××××××××××\n");
printf("×××××××××4.后序递归遍历二叉树×××××××××××\n");
printf("×××××××××5.退出程序××××××××××××××××\n");
printf("#############################################################\n");
printf("请输入你的选择:");
scanf("%c",&m);
switch(m) {
case ’1’:
printf("按先序次序输入二叉树中结点的值,输入0表示节点为空，如：（1 2 3 0 0 4 5 0 6 0 0 7 0 0 0）\n");
printf("\n请按先序次序输入二叉树中结点的值：");
CreateBiTree(T); // 建立二叉树T
break;
case ’2’:
printf("先序递归遍历二叉树： ");
PreOrderTraverse(T,visit); // 先序递归遍历二叉树T
break;
case ’3’:
printf("\n中序递归遍历二叉树： ");
InOrderTraverse(T,visit); // 中序递归遍历二叉树T
break;
case ’4’:
printf(" \n后序递归遍历二叉树：");
PostOrderTraverse(T,visit); // 后序递归遍历二叉树T
break;
case ’5’:break;
default:
printf("输入的字符不对，请重新输入!");
break;

}
getchar();
}while(m!=’5’);

}