二叉树——二叉树的遍历

由题目可知，这道题一共分为两个部分，一是根据所给的字符串以前序遍历的方式创建一个二叉树，而是根据创建的二叉树以中序遍历的方式输出。

首先来解决创建二叉树的问题，我们先创建一个数组，将字符串存储进去。根据我们之前做过的几道题目，我们将该数组以及该数组下标的指针传入函数CreatNode()。在该函数中，首先我们需要判断在数组中该下标所指的元素是否为#，若为#号，则返回空，并且将下标+1.若不是#号，那么我们需要创建一个大小为BTNode大小的节点，并将该下标指向的数组元素填入。然后根据递归的知识，以该节点为这棵子树的根节点，接着向下调用CreatNode()函数。

然后根据我们之前所学的中序遍历的知识将刚才创建的二叉树中的节点输出，这里就不过多赘述。

#include <stdio.h>

typedef struct BTNode
{
    char val;
    struct BTNode*left;
    struct BTNode*right;
}BTNode;

BTNode*CreatNode(char*a,int *pi)
{
    if(a[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    //非空则创建节点
    BTNode*root=(BTNode*)malloc(sizeof(BTNode));
    root->val=a[*pi];
    (*pi)++;
    root->left=CreatNode(a,pi);
    root->right=CreatNode(a,pi);
    return root;
}
void InOrder(BTNode*root)
{
    if(root==NULL)
    {
        return;
    }
    InOrder(root->left);
    printf("%c ",root->val);
    InOrder(root->right);
    
}

int main() 
{
    char a[100];
    scanf("%s",a);
    int i=0;
    BTNode*root=CreatNode(a,&i);
    InOrder(root);
    return 0;
}

大家感兴趣的可以自行尝试一下哦~

页面找不到了_牛客网

原文地址：https://blog.csdn.net/Cancan2004/article/details/143026335

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！