题解 | #二叉树遍历#

#include <stdio.h>
/*
读取用户输入，保存在数组中，这个字符串的内容刚好是二叉树的前序遍历

我们根据这个前序遍历的结果来创建二叉树

再对二叉树进行中序遍历，输出中序遍历的结果
*/
/*
abc##de#g##f###
对于这个字符串，c是b的左子树，b是a的左子树
*/


/*
若遍历中没有给出NULL节点的情况，是不能根据某一个遍历来创建二叉树的


*/
typedef struct BinaryTreeNode//定义二叉树节点结构类型
{
    char data;
    struct BinaryTreeNode*left;
    struct BinaryTreeNode*right;

}BTNode;

BTNode*buyNode(char x)//创建节点
{
    BTNode*newnode=(BTNode*)malloc(sizeof(BTNode));
    newnode->data=x;
    newnode->left=newnode->right=NULL;

    return newnode;
}

BTNode*createTree(char*arr,int*pi)//创建二叉树，返回根节点,第一个参数是字符串，第二个参数是下标
{
    if(arr[*pi]=='#')
    {
        (*pi)++;//不要忘了往后面接着走
        return NULL;
    }
    BTNode*root=buyNode(arr[(*pi)++]);//将数组中的数据存储在二叉树中，将数组中的数据传到二叉树节点内
    root->left=createTree(arr,pi); //然后进行二叉树左节点的创建
    root->right=createTree(arr,pi); //二叉树右节点的创建

    return root;//返回根节点
}
void InOeder(BTNode*root)
{
    if(root==NULL)
    {
        return;
    }
    InOeder(root->left);//递归左子树
    printf("%c ",root->data);//打印根节点
    InOeder(root->right);//递归右子树

}
int main()
{
    //读取用户输入的字符串保存在字符数组中
    char arr[100];
    scanf("%s",arr);

    //根据字符串（前序遍历）创建二叉树
    int i=0;
    BTNode*root=createTree(arr,&i);
//这里的root是创建的二叉树的根节点
    //输出二叉树的中序遍历
    InOeder(root);
    return 0;
}
/*
当pi=0时，我们创建了根节点a，然后创建a的左子树
然后pi指向b，然后创建了根节点b，然后pi++,pi指向c，
创建了根节点c,然后pi++,pi指向了#，为空，那么我们就return 了
然后创建c的右子树
那么pi++指向了#，那么就是空
那么就返回，回到了b这颗树，那么b的左子树就创建完成，那么就进行b的右子树的创建了
pi++指向了d,那么我们创建根节点d,然后pi++指向e，然后我们创建b的左节点e
pi++,指向#，所以为空，那么我们就返回了，进行e的右节点的创建
pi++指向了g，创建了根节点g pi++,指向了# 所以我们在创建g的左节点的时候返回了
那么我们就创建g的右节点
pi++指向了#，所以为空，那么我们就返回了。返回到d,d的左子树已经创建好了
那么我们就创建d的右子树
pi++指向了f
我们创建根节点f
然后pi++,指向#，创建f的左节点，因为为空，所以我们返回，然后创建f的右节点，，Pi++,指向了#，为空，那么我们就返回了
那么d的左右子树都已经创建完成了
那么我们就返回到a了
在a这棵树里面，a的左子树b已经创建好了
那么我们就进行a的右子树的创建了
pi++,指向了#，那么为空，我们就返回
到这里，a这颗二叉树就创建好了


*/