always-SYY.
2021-05-18 09:38
采纳率: 100%
浏览 70

数据结构二叉树C语言

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

  • 好问题 提建议
  • 收藏

2条回答 默认 最新

  • CSDN专家-张老师 2021-05-18 09:41
    已采纳
    
    #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 ;
    }
    
    
    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • CSDN专家-张老师 2021-05-18 09:44
    #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 ;
    }
    

    中序序列和后序 序列构造

    评论
    解决 1 无用
    打赏 举报

相关推荐 更多相似问题