二叉树的创建和遍历

之前我们在学习二叉树的遍历的时候都是先手动创建出一个二叉树，然后再前中后序的遍历，
但实际中，是给你一个数组里面存的数，然后把他以（前中后）的遍历储存创建为一个二叉树

思路：
想要创建二叉树，首先就要有树节点的结构体：

typedef char DataType; 
typedef struct TreeNode
{
    struct TreeNode* left;
    struct TreeNode* right;
    DataType val;
}TNode;
1
2
3
4
5
6
7

然后遍历字符数组，只要不是#，就要创建一个树节点把数据存进去，然后递归，先递归左，直到返回NULL.说明左树已经遍历到底，然后递归遍历右树，这样就实现了把字符串中的数组按前序遍历的数组储存到树中，也就建立了一二叉树

TNode* FrontTree(char* tre,int* pi)//创建二叉树
{
    if(tre[*pi]=='#')
    {
        (*pi)++;
        return NULL;
    }
    TNode* node=(TNode*)malloc(sizeof(TNode));
    node->val=tre[*pi];
    (*pi)++;
    node->left=FrontTree(tre,pi);
    node->right=FrontTree(tre,pi);

    return node;
}
void IntoTree(TNode* root)//中序打印
{
    if(root==NULL)
    {
        return; 
    }
    IntoTree(root->left);
    printf("%c ",root->val);
    IntoTree(root->right);
}
int main() {
    char tre[100];
    scanf("%s",tre);
    int i=0;
    TNode* tree=FrontTree(tre,&i);
    IntoTree(tree);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33