数据结构二叉树C语言

由先序序列和中序序列以及由中序序列和后序 序列构造一棵二叉树的功能(二叉树中的每个结点值为单个字符),要求以括号表示和凹入 表示法输出该二叉树,并用先序遍历序列“ABDEHJKLMNCFGI”和中序遍历序列 “DBJHLKMNEAFCGI”以及由中序遍历序列“DBJ HLKMNEAFCGI”和后序遍历序列 DJLNMKHEBFIGCA”进行验证

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
typedef char ElementType ;
 
typedef struct node
{
	ElementType data ;
	struct node * leftChild ;
	struct node * rightChild ;
}BTNode;
 
//pre：存放先序序列  in：存放中序序列
BTNode *createBT(char *pre , char *in ,int n)
{
	BTNode *b;
	char *p ;
	int k ;
	if(n<=0)
		return NULL;
	b=(BTNode *)malloc(sizeof(BTNode));
	b->data = *pre ;
	int j=0;
	for(p=in;p<in+n;p++)
	{
		if(*p == *pre)
			break;
	}
	k=p-in;           //确定根节点在中序序列(in)中的位置 编号为0,1,2,...,n-1 (类似于数组中的下标号，不是逻辑序号)
	b->leftChild = createBT(pre+1,in,k);   //递归构造左子数
	b->rightChild = createBT(pre+1+k,p+1,n-k-1);  //递归构造右子树
	return b ;
}
 
//先序遍历二叉树BinaryTree:先遍历根节点接着遍历左子树，最后遍历右子树
//(不是左孩子节点和右孩子节点，概念要分清哦(虽然节点也是一个树))
void showBTPreOrder(BTNode *b)
{
	if(b != NULL)
	{
		//遍历根节点
		printf("%c",b->data);
		//遍历左子树
		showBTPreOrder(b->leftChild);
		//遍历右子树
		showBTPreOrder(b->rightChild);
 
	}
}
 
//中序遍历二叉树BinaryTree:先遍历左子树，接着遍历根节点，左后遍历右子树
//(不是左孩子节点和右孩子节点，概念要分清哦(虽然节点也是一个树))
void showBTInOrder(BTNode *b)
{
	if(b!=NULL)
	{
		//遍历左子树
		showBTInOrder(b->leftChild);
		//遍历根节点
		printf("%c",b->data);
		//遍历右子树
		showBTInOrder(b->rightChild);
	}
}
 
int main()
{
	BTNode *b = NULL ;
	char pre[] = "ABDGCEF";
	char in[] = "DGBAECF" ;
	b=createBT(pre,in,7);
	//先序遍历遍历二叉树
	printf("先序遍历遍历二叉树:\n");
	showBTPreOrder(b);
	printf("\n");
	//中序遍历遍历二叉树
	printf("中序遍历遍历二叉树:\n");
	showBTInOrder(b);
	printf("\n");
	return 0 ;
}

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
 
typedef char ElementType ;
 
typedef struct node
{
	ElementType data ;
	struct node * leftChild ;
	struct node * rightChild ;
}BTNode;
 
//post:存放后序序列  in:存放中序序列
BTNode *createBT(char *post , char *in ,int n)
{
	BTNode *b;
	char *p ,root ;  //root:根节点值
	int k ;
	if(n<=0)
		return NULL;
	root=*(post+n-1) ;  //获取根节点的值
	b=(BTNode *)malloc(sizeof(BTNode));
	b->data = root ;
	for(p=in;p<in+n;p++)
	{
		if(*p == root)
			break;
	}
	k=p-in;           //确定根节点在中序序列(in)中的位置(下标号) 编号为0,1,2,...,n-1 (类似于数组中的下标号，不是逻辑序号)
	b->leftChild = createBT(post,in,k);   //递归构造左子数
	b->rightChild = createBT(post+k,p+1,n-k-1);  //递归构造右子树
	return b ;
}
 
 
//中序遍历二叉树BinaryTree:先遍历左子树，接着遍历根节点，左后遍历右子树
//(不是左孩子节点和右孩子节点，概念要分清哦(虽然节点也是一个树))
void showBTInOrder(BTNode *b)
{
	if(b!=NULL)
	{
		//遍历左子树
		showBTInOrder(b->leftChild);
		//遍历根节点
		printf("%c",b->data);
		//遍历右子树
		showBTInOrder(b->rightChild);
	}
}
 
//后序遍历二叉树BinaryTree:先遍历左子树，接着遍历右子树，左后遍历根节点
//(不是左孩子节点和右孩子节点，概念要分清哦(虽然节点也是一个树))
void showBTPostOrder(BTNode *b)
{
	if(b != NULL)
	{
		//遍历左子树
		showBTPostOrder(b->leftChild);
		//遍历右子树
		showBTPostOrder(b->rightChild);
		//遍历根节点
		printf("%c",b->data);
 
	}
}
 
int main()
{
	BTNode *b = NULL ;
	char in[] = "DGBAECF";
	char post[] = "GDBEFCA" ;
	b=createBT(post,in,7);
	//中序遍历遍历二叉树
	printf("中序遍历遍历二叉树:\n");
	showBTInOrder(b);
	printf("\n");
	//后序遍历遍历二叉树
	printf("后序遍历遍历二叉树:\n");
	showBTPostOrder(b);
	printf("\n");
	return 0 ;
}

中序序列和后序 序列构造