一. 题目介绍

二. 题目分析

首先

题目让我们以先序遍历的方式用字符串建立一个二叉树

输入是一个字符串

输出是是以中序遍历二叉树打印

我们先来看最简单的输入

这里只要建立一个字符数组 然后等测试用例输入就好了

    // 接受输入值char arr[100]={0};scanf("%s",arr);

代码表示如上

之后我们再开始创建二叉树

我们可以看到 它是先序遍历

所以说我们要用先序遍历的方式来创建二叉树

我们先来创建二叉树的结构体

代码表示如下

typedef struct BinaryTree
{struct BinaryTree* left;struct BinaryTree* right;char val;
}BT;

之后我们开始写创建二叉树的代码（前序）

BT* BinaryTreeCreate(char* arr , int i)
{//如果是#返回空if(arr[i]=='#'){i++;return NULL;}// 否则就创建一个新的节点 BT* newnode = (BT*)malloc(sizeof(struct BinaryTree));newnode->val= arr[i];i++;newnode->left = BinaryTreeCreate(arr, i);newnode->right = BinaryTreeCreate(arr, i); return newnode;}

但是我们这样子的代码对吗？

显然是不对的

因为这个时候我们使用的i是传值传递的

所以说这里一定会存在问题

我们这个时候需要使用指针来接受i的值

BT* BinaryTreeCreate(char* arr , int* pi)
{//如果是#返回空if(arr[*pi]=='#'){(*pi)++;return NULL;}// 否则就创建一个新的节点 BT* newnode = (BT*)malloc(sizeof(struct BinaryTree));newnode->val= arr[*pi];(*pi)++;newnode->left = BinaryTreeCreate(arr, pi);newnode->right = BinaryTreeCreate(arr, pi); return newnode;
}

这样子就可以了

之后我们开始中序遍历打印

void Inorder(BT* root)
{// 首先考虑极限情况if(root==NULL){return;}// 之后开始中序遍历 Inorder(root->left);printf("%c ",root->val);Inorder(root->right);
}

三. 所有代码

#include 
#include typedef struct BinaryTree
{struct BinaryTree* left;struct BinaryTree* right;char val;
}BT;void Inorder(BT* root)
{// 首先考虑极限情况if(root==NULL){return;}// 之后开始中序遍历 Inorder(root->left);printf("%c ",root->val);Inorder(root->right);
}BT* BinaryTreeCreate(char* arr , int* pi)
{//如果是#返回空if(arr[*pi]=='#'){(*pi)++;return NULL;}// 否则就创建一个新的节点 BT* newnode = (BT*)malloc(sizeof(struct BinaryTree));newnode->val= arr[(*pi)++];newnode->left = BinaryTreeCreate(arr, pi);newnode->right = BinaryTreeCreate(arr, pi); return newnode;
}int main()
{// 接受输入值char arr[100]={0};scanf("%s",arr);// 建立二叉树int i = 0;BT* root = BinaryTreeCreate(arr, &i); // 中序遍历打印二叉树Inorder(root);return 0;
}