目录一题目二代码思路1前序遍历还原二叉树2代码逻辑三代码四 递归展开图一题目解释读取用户输入的二叉树前序遍历字符串构建中对应二叉树然后打印二叉树的中序遍历字符串即可(题目没有要求把中序遍历字符串存储在数组中再返回数组)此外前中后序遍历二叉树的递归逻辑在此篇博客详细有讲不再赘述递归实现 前/中/后序 遍历二叉树 的详细讲解-CSDN博客二代码思路1前序遍历还原二叉树前提根据前序遍历字符串构建二叉树示意图是最简单无脑的直接跟着字符串进行根左右的顺序构建节点即可遇到非空字符则创建节点存储该字符遇到空则返回并且空字符也给我们了就是#所以对于空的判断仅需判断字符是否为#例子2代码逻辑①接收到的前序遍历字符串创建一个字符串数组来保存②访问该数组根据前序遍历将其还原成二叉③所以我们要实现定义二叉树节点结构体④实现一个中序遍历的函数用来遍历二叉树进行中序遍历打印三代码#include stdio.h #include stdlib.h //单个二叉树节点的定义 typedef struct BinaryTreeNode { struct BinaryTreeNode* left; struct BinaryTreeNode* right; char val; }BTNode; //还原二叉树函数 BTNode* CreteTree(char* str, int* pi) { if(str[*pi]#) { (*pi); return NULL; } BTNode* root (BTNode*) malloc(sizeof(BTNode)); root-val str[*pi]; (*pi); root-left CreteTree(str, pi); root-right CreteTree(str, pi); return root; } //中序遍历函数 void InOrder(BTNode* root) { if(root NULL) return; InOrder(root-left); printf(%c ,root-val); InOrder(root-right); } int main() { //创建一个字符串数组来接受 前序遍历字符串 char str[100] ; scanf(%s,str); //创建一个i来控制下标 int i0; //将字符串和下标i传给 CreteTree 来还原成一个二叉树最后接收返回的二叉树的根节点 BTNode* root CreteTree(str,i); //中序遍历打印 InOrder(root); return 0; }解释①节点结构体二叉树的单个节点的结构体定义还原成二叉树前提肯定是需要二叉树节点的定义的。②根据前序遍历字符串构建二叉树和上文所述一致。根据前序遍历字符串构建二叉树示意图是最简单无脑的直接跟着字符串进行根左右的顺序构建节点即可遇到非空字符则创建节点存储该字符遇到空则返回并且空字符也给我们了就是#所以对于空的判断仅需判断字符是否为#③中序遍历函数递归实现 前/中/后序 遍历二叉树 的详细讲解-CSDN博客④主函数CreteTree构建二叉树函数是一个递归函数而该函数内部是要通过下标访问str数组的所以每个递归函数都应该共享并修改同一个下标变量i所以在main中创建ii传递给CreteTree();四 递归展开图下面是CreteTree函数的递归展开图在int*pi下面的是下标红色的线是递蓝色的线是归线旁边的是该线所处的第几步。不清晰从上到下分开发上中下 [ 作者 ] shylyly [ 首次发布 ] 2024.9.2❌ [ 最新修改 ] 2026.8.4 [ 声明 ] 由于笔者水平有限文中难免有疏漏或不妥之处还望读者不吝赐教
)
