二叉树的遍历及打印.cpp

在vc平台上

#include<stdio.h>
#include<stdlib.h>
#include<iostream.h>
/*#define TRUE 1
#define FALSE 0
#define Stack_Size 50
const NUM;
typedef struct
{ Stack ElementType elem[Stack_Size];
  int top;
}SeqStack;非递归方法实现*/
typedef struct Node
{char  data;
  struct Node *Lchild;
  struct Node *Rchild;
}BiTNode,*BiTree;
//建立二叉链表存储的树(按先序)
void CreateBiTree(BiTree *bt)
{
  char ch;
  ch=getchar();
  if(ch=='.')
	  *bt=NULL;
  else
  { *bt=(BiTree)malloc(sizeof(BiTNode));
    (*bt)->data=ch;
	CreateBiTree(&((*bt)->Lchild));
    CreateBiTree(&((*bt)->Rchild));
  }
}

//下面先用递归的方法实现
void PreOrder(BiTree root)
{ if(root!=NULL)
{//printf("%c",  root->data);
 PreOrder(root->Lchild);
 printf("%c",root->data);
 PreOrder(root->Rchild);
 //printf("%c",root->data);
}
}
void main()
{BiTree T=NULL;
 CreateBiTree(&T);
 PreOrder(T);
 printf("\n ");
}
 
/*//下面用非递归的方法来实现
void InitStack(SeqStack *S)
{ S->top=-1;
}
int IsEmpty(SeqStack *S)
{ return(S->top==-1?TRUE:FALSE);
}
int Push(SeqStack *S,StackElementType x)
{if(S->top==Stack_Size-1)
   return (FALSE); 
  S->top++;
  S->elem[S->top]=x;
  return(TRUE);
}
int Pop(SeqStack *S,StackElementType *x)
{ if(S->top==-1)
  return(FALSE);
  else
  { *x=S->elem[S->top];
    S->top--;
	return(TRUE);
}}
 
void PreOrder(BiTree root)//非递归先序
{
 BiTree p=root;
 SeqStack S;
 S.top=-1;
 while(p!=NULL||S.top!=-1)
 {if(p)
 { 
	 printf("%c",p->data);
	 Push(&S,p);
	 p=p->Lchild;
 }
 else
 {
	 Pop(&S,&p);
	 p=p->Rchild;
}}}

void PostOrder(BiTree root) //非递归后序
{BiTNode *p,*q;
 BiTNode **S;
 int top=0;
 q=NULL;
 p=root;
 S=(BiTNode**)malloc(sizeof(BiTNode*)*NUM);
 while(p!=NULL||top!=0)
 {while(p!=NULL)
 {top++;
 S[top]=p;
 p=p->Lchild;
 }
 if(top>0)
 {p=S[top];
  if(p->Rchild==NULL)||(p->Rchild==q))
  {printf(p->data);
  q=p;
  top--;
  p=NULL;
  }
  else
  p=p->Rchild;
 }
 }
 free(S);
}

void InOrder(BiTree root)//非递归中序
{InitStack(&S);
 p=root;
 while((p!=NULL)||!IsEmpty(S))
 {if(p!=NULL)
 {Push(&S,p);
  p=p->Lchild;
 }
 else
 { Pop(&S,&p);
   printf(p->data);
   p=p->Rchild;
 }
 }
}
void main()
{
	BiTree T=NULL;
	SeqStack s;
	InitStack(&S);
	IsEmpty(&S);
	Push(&S,x);
	Pop(&S,&x);
	PreOrder(T);
	PostOrder(T);
	InOrder(T);
	printf("\n ");
}*/