学步园

先以先序和中序恢复来说：

1.首先我们是使用递归的方式来完成

2.递归的最小单元是：给一个空树和这个书的中序与先序序列，那么先序序列的第一个元素就是该树的根节点，同样在恢复左右子树递归调用这个方法

3.递归的终止条件是，当这棵树的中序序列为空的时候就停止。

同理根据后序和中序序列也是一样的道理：

我们可以发现后续序列就是先序序列的倒置

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXNODE 100

#include <windows.h>
static void   gotoxy(int   x,   int   y)   {
  COORD   c;
  c.X   =   x   -   1;
  c.Y   =   y   -   1;
  SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c);
}

typedef struct Node{
	char data;
	struct Node* lchild;
	struct Node* rchild;
}*BinTree,binNodt;

//递归前序遍历二叉树
void PreOrder(BinTree T){
	if(T == NULL){
		return;
	}
	printf("%c",T->data);
	PreOrder(T->lchild);
	PreOrder(T->rchild);
}

//递归中序遍历二叉树
void InOrder(BinTree T){
	if(T == NULL){
		return;
	}
	InOrder(T->lchild);
	printf("%c",T->data);
	InOrder(T->rchild);
}

//递归后续遍历二叉树
void PostOrder(BinTree T){
	if(T == NULL){
		return;
	}
	PostOrder(T->lchild);
	PostOrder(T->rchild);
	printf("%c",T->data);
}

//图像输出
/*
	以满二叉树为考虑对象：
	为了确保父节点与子节点之间的有交错感觉所以：
	二叉树最左边的叶子到根节点的水平距离为：根节点左子数的节点个数.2^(k-2) k是层数 根的层数为1
*/
int xxx=0;
int yyy=6;
void print(BinTree T,int level,int offset){//T,1,0

   xxx++;
   if(T == NULL)
		return ;
    else
    {
		print(T->lchild,level+1,offset-1);
		gotoxy(xxx*2,(level*2)+yyy);
		//printf("%c(%d,%d) ",T->data,offset,level);
		printf("%c",T->data);
		if(T->lchild!=NULL){
			gotoxy(xxx*2-1,(level*2)+yyy+1);
			printf("/");
		}
		if(T->rchild!=NULL){
			gotoxy(xxx*2+1,(level*2)+yyy+1);
			printf("\\");
		}
		print(T->rchild,level+1,offset+1);
	}
}
//查找字符的位置
int getIndex(char * str,char x){
	int i;
	for(i=0;i<strlen(str);i++){
		if(str[i]==x){
			return i;
		}
	}
	return -1;
}
//将str字符串分割
void getFastEnd(char* str,char x,char result[2][100]){
	strcpy(result[0],"\0");
	strcpy(result[1],"\0");
	if(strlen(str)==0 || strlen(str)==1){
		return;
	}
	if(getIndex(str,x) == 0){
		strcpy(result[1],str+1);
	}else if(getIndex(str,x) == strlen(str)-1){
		strcpy(result[0],str);
		result[0][strlen(str)-1]='\0';
	}else{
		strcpy(result[0],strtok(str,&x));
		strcpy(result[1],strtok(NULL,&x));
	}
}

//依据前序和中续生成一颗二叉树
int fIndex=0;//标识前序进行了几个了
void getTreeForF_M(char* proOrder,char* inOrder,BinTree* T){
	BinTree temp = NULL;
	char result[2][100];//存储左右孩子的中序序列
	if(*inOrder==NULL){	//当中序序列为空时将指向该子树的指针设置为NULL
		*T = NULL;
	}else{
		temp = (BinTree)malloc(sizeof(binNodt));
		temp->data = proOrder[fIndex++];
		temp->lchild=NULL;
		temp->rchild=NULL;
		*T = temp;
		getFastEnd(inOrder,temp->data,result);	//将中序序列根据当前根的值分割成两段
		getTreeForF_M(proOrder,result[0],&(temp->lchild));//恢复左子树
		getTreeForF_M(proOrder,result[1],&(temp->rchild));//恢复右子树
	}
}

//依据 后序和中序生成一颗二叉树
int eIndex=1;
void getTreeForE_M(char* endOrder,char* inOrder,BinTree* T){
	BinTree temp=NULL;
	char result[2][100];
	if(*inOrder==NULL){
		*T=NULL;
	}else{
		temp = (BinTree)malloc(sizeof(binNodt));
		temp->data = endOrder[strlen(endOrder)-eIndex++];
		temp->lchild=NULL;
		temp->rchild=NULL;
		*T = temp;
		getFastEnd(inOrder,temp->data,result);	//将中序序列根据当前根的值分割成两段
		getTreeForE_M(endOrder,result[1],&(temp->rchild));//恢复右子树
		getTreeForE_M(endOrder,result[0],&(temp->lchild));//恢复左子树
	}
}
int main()
{
	char temp[2][100];
	char pro[100]="ABCDEFGHI";
	char in[100]="BCAEDGHFI";
	char en[100]="CBEHGIFDA";
	BinTree T=NULL;
	//getTreeForF_M(pro,in,&T);
	getTreeForE_M(en,in,&T);
	printf("\n");

	printf("前序遍历：");
	PreOrder(T);
	printf("\n中序遍历：");
	InOrder(T);
	printf("\n后序遍历：");
	PostOrder(T);

	printf("\n图像输出：");
	print(T,1,0);
	getchar();
    return 0;
}

在上面结构的基础上还可以获取某一层的数据，二叉树的深度，二叉树的层次遍历等方法：

//打印二叉树某一层的节点
void TransLevel(BinTree T,int level){
    if(T == NULL)
        return ;
    else
    {
        if(level == 1)
           printf("%c ",T->data);
        else
        {
            TransLevel(T->lchild,level-1);
            TransLevel(T->rchild,level-1);
        }
    }
}

//二叉树层次便利
void LevelOrder(BinTree T){
	BinTree Queue[MAXNODE];
	int f,r;
	if(T == NULL)
		return;
	f=-1;
	r=0;
	Queue[r]=T;//将头指针入队
	while(r!=f){//队列不为空就循环
		f++;//出队
		printf("%c",Queue[f]->data);
		if(Queue[f]->lchild!=NULL){
			r++;//入队
			Queue[r]=Queue[f]->lchild;
		}
		if(Queue[f]->rchild!=NULL){
			r++;//入队
			Queue[r]=Queue[f]->rchild;
		}
	}
}
//获取二叉树的深度
void LevelNum(BinTree T,int level){
	int temp = 1;
	if(T == NULL)
        return;
    else
    {
        if(level > num){//如果当前层大于num就交换
			num = level;
        }

            LevelNum(T->lchild,level+1);
            LevelNum(T->rchild,level+1);

    }
}

有那写的不妥当的我们一起来交流！

http://blog.csdn.net/manageer/article/details/24519987