【前言】

今天是刷题打卡第42天！

早成者未必有成，晚达者未必不达，一切都还来得及，加油鸭。

原题：清华大学考研复试题：二叉树遍历

题目描述：

编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。 

输入描述：

输入包括1行字符串，长度不超过100。

输出描述：

可能有多组测试数据，对于每组数据， 输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。 每个输出结果占一行。 

题解：

如果只给出前序遍历肯定是不能构造一棵二叉树的，但是给出了空树部分就很简单啦。详情见代码哈。

代码执行：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      typedef struct TreeNode
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	char val;
     
    
   

    

     

    
    

     
	struct TreeNode* left;
     
    
   

    

     

    
    

     
	struct TreeNode* right;
     
    
   

    

     

    
    

     

      }TNode;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      TNode* CreateTree(char* a, int* pi)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (a[*pi] == '#')//空树不需要递归构建,但是需要i++
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		(*pi)++;
     
    
   

    

     

    
    

     
		return NULL;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	//不是空树就需要递归构建树
     
    
   

    

     

    
    

     

      	TNode* root = (TNode*)malloc(sizeof(TNode));
     
    
   

    

     

    
    

     
	if (root == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		printf("malloc fail\n");
     
    
   

    

     

    
    

     
		exit(-1);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	else
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     

      		root->val = a[*pi];//将当前数组中的值作为根节点值
     
    
   

    

     

    
    

     

      		(*pi)++;
     
    
   

    

     

    
    

     

      		root->left = CreateTree(a, pi);//递归构建左子树
     
    
   

    

     

    
    

     

      		root->right = CreateTree(a, pi);//递归构建右子树
     
    
   

    

     

    
    

     
		return root;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      void InOrder(TNode* root)//中序递归遍历
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	if (root == NULL)
     
    
   

    

     

    
    

     

      	{
     
    
   

    

     

    
    

     
		return;
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	InOrder(root->left);
     
    
   

    

     

    
    

     
	printf("%c ", root->val);
     
    
   

    

     

    
    

     
	InOrder(root->right);
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
	char arr[30] = { 0 };
     
    
   

    

     

    
    

     
	gets(arr);
     
    
   

    

     

    
    

     
	int i = 0;
     
    
   

    

     

    
    

     

      	TNode* root = CreateTree(arr, &i);
     
    
   

    

     

    
    

     
	InOrder(root);
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

结语

今天是刷题打卡第42天！

加油吧少年。

文章来源: bit-runout.blog.csdn.net，作者：安然无虞，版权归原作者所有，如需转载，请联系作者。

原文链接：bit-runout.blog.csdn.net/article/details/121717042