一. 题目介绍
二. 题目分析
首先
题目让我们以先序遍历的方式用字符串建立一个二叉树
输入是一个字符串
输出是是以中序遍历二叉树打印
我们先来看最简单的输入
这里只要建立一个字符数组 然后等测试用例输入就好了
// 接受输入值 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 <stdio.h> #include <stdlib.h> 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; }
