中序递归遍历二叉树的算法？（数据结构）

#include
#include
#define maxsize 100
typedef char elemtype;
typedef struct Node
{
elemtype data;
struct Node *lchild;
struct Node *rchild;
}BitNode;
void CreatBiTree(BitNode *&b,char *str)
{BitNode *st[maxsize],*p=NULL;
int top=-1,k,j=0;
char ch;
b=NULL;
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=(BitNode *)malloc(sizeof(BitNode));
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];
}
}

BitNode *Find(BitNode *b,elemtype x)
{BitNode *p;
if(b==NULL)
return NULL;
else if(b->data==x)
return b;
else
{p=Find(b->lchild,x);
if(p!=NULL)
return p;
else
return Find(b->rchild,x);
}
}

BitNode *Lchild(BitNode *b)
{return b->lchild;}

BitNode *rchild(BitNode *b)
{return b->rchild;}

int BiTreeDepth(BitNode *b)
{ /* 初始条件: 二叉树T存在。操作结果: 返回T的深度 */
int i,j;
if(!b)
return 0;
if(b->lchild)
i=BiTreeDepth(b->lchild); //递归求左子树的深度
else
i=0;
if(b->rchild)
j=BiTreeDepth(b->rchild); //递归求右子树的深度
else
j=0;
return i>j?i+1:j+1; //取深度值大者加1作为该树的深度
}
void Visit(char ch)
{
printf("%c ",ch);
}

/*先序遍历二叉树*/
void PreOrder(BitNode *b)
{
if (b!=NULL)
{
Visit(b->data);
PreOrder(b->lchild);
PreOrder(b->rchild);
}
}

/*中序遍历二叉树*/
void InOrder(BitNode *b)
{
if (b!= NULL)
{
InOrder(b->lchild);
Visit(b->data);
InOrder(b->rchild);
}
}

/* 后序遍历二叉树*/
void PostOrder(BitNode *b)
{
if(b!= NULL)
{
PostOrder(b->lchild);
PostOrder(b->rchild);
Visit(b->data);
}
}

void main()
{
BitNode *b,*p,*lp,*rp;
printf("(1)用孩子链式储存结构创建二叉树");
CreatBiTree(b,"A(B(D,E(H(J,K(L,M(,N))))),C(F,G(,I)))");
printf("\n(2)输出'H'结点的左右孩子");
p=Find(b,'H');
if(p!=NULL)
{lp=Lchild(p);
if(lp!=NULL)
printf("左孩子为:%c",lp->data);
else
printf("无左孩子");
rp=rchild(p);
if(rp!=NULL)
printf("右孩子为:%c",rp->data);
else
printf("无右孩子");}
printf("\n");
printf("(3)二叉树b的深度为:%d\n",BiTreeDepth(b));
printf("(4)先序遍历序列为:");
PreOrder(b);
printf("\n(5)中序遍历序列为:");
InOrder(b);
printf("\n(6)后序遍历序列为:");
PostOrder(b);
printf("\n");
}

#include
using namespace std;
#include
#include
#include
#define maxsize 20 //最大结点个数
//#define N 14 //必须输入结点个数(包含虚结点)
#define M 10 //最大深度
typedef struct node{
char data;
int m; //结点的深度
struct node*lchild,*rchild;
}Bitree;
Bitree*Q[maxsize];
Bitree*creatree()
{
char ch;
int front,rear;
// int i=1;
Bitree *T,*s;
T=NULL;
front=1;
rear=0;
cout<<"请输入数据"< cin>>ch;
while(ch!='#')
{
// cin>>ch;
s=NULL;
if(ch!='@')
{
s=(Bitree*)malloc(sizeof(Bitree));
s->data =ch;
s->lchild =s->rchild =NULL;
}
rear++;
Q[rear]=s;
if(rear==1)
{
T=s;
T->m=1; //父结点深度为一
}
else{
if(s!=NULL&&Q[front]!=NULL)
if(rear%2==0)
{
Q[front]->lchild =s;
Q[front]->lchild ->m =Q[front]->m+1;
}
else
{
Q[front]->rchild =s;
Q[front]->rchild ->m =Q[front]->m+1;
}

if(rear%2==1)
front++;
}
//i++;
cin>>ch;
}
return T;
}
int countleaf(Bitree* T)
{
if(T==NULL)
return (0);
else if((T->lchild==NULL)&&(T->rchild==NULL))
return (1);
else
return (countleaf(T->lchild)+countleaf(T->rchild));
}
int treedepth(Bitree *T)
{
if(T==NULL)
return (0);
else
{
if(treedepth(T->lchild )>treedepth(T->rchild ))
return(treedepth(T->lchild )+1);
else
return (treedepth(T->rchild )+1);
}
}
void output(Bitree*T) //输出打印二叉数
{
int i;
if(T!=NULL)
{
output(T->rchild ); //右根左遍历二叉数，结果从上到下显示
for(i=1;i<=M;i++)
{
if(i!=T->m)
cout<<" ";
else
cout<data ;
}
cout< //cout<data ;
output(T->lchild );
}
}

int menu_select( )
{
int sn;
printf(" 打印二叉树问题\n");
printf("==================\n");
printf(" 1 二叉树的建立\n");
printf(" 2 打印二叉树\n");
printf(" 3 求二叉树叶子结点个数\n");
printf(" 4 求二叉树的深度\n");
printf(" 0 退出系统\n");
printf("==================\n");
printf(" 请 选 择0－4：\n");
for( ; ; )
{
scanf( "%d", &sn);
if( sn <0||sn>4)
printf("\n\t输入错误，重选0－4：\n");
else
break;
}
return sn;
}

int main( )
{
Bitree*T;
for(; ;)
{
switch(menu_select())
{
case 1: T=creatree();
printf("\n");
break;
case 2: cout<<"打印结果："< output(T);
printf("\n");
break;
case 3: int i;
i=countleaf(T);
cout<<"所求二叉树叶子结点为"< cout< break;
case 4: int j;
j=treedepth(T);
cout<<"所求二叉树深度为"< cout< break;
case 0:printf("再见");
exit(0);
break;
}
}
return 0;
}

/*void main()
{
Bitree*T;
T=creatree();
cout<<"打印结果："< output(T);
}*/

Seek( 某一节点)
{
if (这个节点不存在) return ;
Seek(左儿子节点)
处理。例如输入printf(节点.data);
Seek(右儿子节点)
}

void Inorder ( bitptr t )
{
if ( t ) {
Inorder (t->lchild);
visit ( t );
Inorder (t->rchild);
}
}