一个C语言程序非递归中序遍历二叉树

#include

#include

typedef

struct

bitnode

{

char

data

struct

bitnode

*lchild,*rchild

}bitnode,*bitree

bitree

create_tree()

//先序创建

{

char

abitree

root

scanf("%c",&a)

fflush(stdin)

if(a=='#')return

NULL

else

{

root=(bitnode

*)malloc(sizeof(bitnode))

root->data=a

root->lchild=create_tree()

root->rchild=create_tree()

}

return

root

}

void

inorder(bitree

root)//中根遍历

{

bitree

s[100]

int

top=0

while(root||top)

{

while(root)

{

s[++top]=rootroot=root->lchild

}

if(top)

{

putchar(s[top]->data)

root=s[top--]->rchild

}

}

}

void

main()

{

bitree

root=NULL

root=create_tree()//输入序列为先序遍历序列，＃代表空

inorder(root)

printf("\n")

}

//例如输入a(回车）b（回车）#（回车）#(回车）c(回车）#（回车）#(回车）输出bac

#include<iostream.h>

struct tree

{ int data

tree *lchild

tree *rchild

}

int creat(tree *&t)

{ int ch

cin>>ch

if(ch==0 )

{ t=NULL}

else

{ t=new tree

t->data=ch

creat(t->lchild)

creat(t->rchild)

}

return 1

}

void inorder(tree *t)

{ if(t!=NULL)

{ cout<<t->data

inorder(t->lchild)

cout<<t->data

inorder(t->rchild)

}

}

void main()

{ tree *t

creat(t)

cout<<"创建完成"<<endl

cout<<"中序遍历为："

inorder(t)

}

if(T){

if(InOrderTraverse(T->l,Visit))

if(Visit(T->data))

if(InOrderTraverse(T->r,Visit)) return OK

return ERROR

}else return OK

以上就是中序遍历二叉树

这段程序我全有，具体如下：

#include <alloc.h>

#define ERROR 0

#define FALSE 0

#define TRUE 1

#define OK 1

typedef int ElemType

typedef int Status

typedef int KeyType

#define EQ(a,b) ((a)==(b))

#define LT(a,b) ((a)<(b))

#define LQ(a,b) ((a)<=(b))

typedef struct BinaryTree //定义二叉树

{

ElemType data

struct BinaryTree *l

struct BinaryTree *r

}*BiTree,BiNode//

BiNode * new()//为新结点开辟空间

{

return( (BiNode *)malloc(sizeof(BiNode)) )

}

CreateSubTree(BiTree *T,ElemType *all,int i)//创建新有子树

{

if ((all[i]==0)||i>16)

{

*T=NULL

return OK

}

*T=new()

if(*T==NULL) return ERROR

(*T)->data=all[i]

CreateSubTree(&((*T)->l),all,2*i)

CreateSubTree(&((*T)->r),all,2*i+1)

}

CreateBiTree(BiTree *T)//创建新结点

{

ElemType all[16]={0,1,2,3,0,0,4,5,0,0,0,0,6,0,0,0,}

CreateSubTree(T,all,1)

}

printelem(ElemType d)//输出

{

printf("%d\n",d)

}

PreOrderTraverse(BiTree T,int (*Visit)(ElemType d))//前序遍历

{

if(T){

if(Visit(T->data))

if(PreOrderTraverse(T->l,Visit))

if(PreOrderTraverse(T->r,Visit)) return OK

return ERROR

} else return OK

}

InOrderTraverse(BiTree T,int (*Visit)(ElemType d))//中序遍历

{

if(T){

if(InOrderTraverse(T->l,Visit))

if(Visit(T->data))

if(InOrderTraverse(T->r,Visit)) return OK

return ERROR

}else return OK

}

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree *p){

if(!T) {*p=freturn FALSE}

else if EQ(key,T->data){ *p=Treturn TRUE}

else if LT(key,T->data) SearchBST(T->l,key,T,p)

else SearchBST(T->r,key,T,p)

}

Status InsertBST(BiTree *T,ElemType e){

BiTree p

BiTree s

if(!SearchBST(*T,e,NULL,&p)){

s=(BiTree)malloc(sizeof(BiNode))

s->data=es->l=s->r=NULL

if(!p) *T=s

else if (LT(e,p->data)) p->l=s

else p->r=s

return TRUE

}

else return FALSE

}

void Delete(BiTree *p){

BiTree q,s

if(!(*p)->r){

q=(*p)

(*p)=(*p)->l

free(q)

}

else if(!(*p)->l){

q=(*p)

(*p)=(*p)->r

free(q)

}

else {

/*q=(*p)

s=(*p)->l

while(s->r) {q=ss=s->r}

(*p)->data=s->data

if(q!=(*p) ) q->r=s->l

else q->l=s->l

free(s)

*/

q=s=(*p)->l

while(s->r) s=s->r

s->r=(*p)->r

free(*p)

(*p)=q

}

}

Status DeleteBST(BiTree *T,KeyType key){

if (!(*T) )

{return FALSE}

else{

if ( EQ(key,(*T)->data)) Delete(T)

else if ( LT(key,(*T)->data)) DeleteBST( &((*T)->l), key)

else DeleteBST( &((*T)->r),key)

return TRUE

}

}

main()

{

BiTree root

BiTree sroot=NULL

int i

int a[10]={45,23,12,3,33, 27,56,90,120,62}

system("cls")

CreateBiTree(&root)

printf("PreOrderTraverse:\n")

PreOrderTraverse(root,printelem)

printf("InOrderTraverse:\n")

InOrderTraverse(root,printelem)

for(i=0i<10i++)

InsertBST(&sroot,a[i])

printf("InOrderTraverse:\n")

InOrderTraverse(sroot,printelem)

for(i=0i<3i++)

DeleteBST(&sroot,a[i])

printf("Now sroot has nodes:\n")

InOrderTraverse(sroot,printelem)

}

---