题解 | 二叉树遍历

难点建树的核心：所给出的先序遍历序列刚好和建树的递归调用顺序一样，采用递归建树，注意字符串的索引和字符类型要定义在main外面。

#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;

//定义树结点
typedef struct Node {
    char data;
    struct Node* rchild, * lchild;
} BiTNode, *BiTree;

//递归建树
int i = 0;
char arr[100];
BiTree CreatTree() {
    if (arr[i] == '#') {
        i++;
        return NULL;//空节点
    }
    BiTNode* root = new BiTNode();
    root->data = arr[i++];//根
    root->lchild = CreatTree();//左
    root->rchild = CreatTree();//右
    return root;

}

//递归中序遍历
void InOrder(BiTree T) {
    if (T == NULL)return;
    InOrder(T->lchild);
    printf("%c ", T->data);
    InOrder(T->rchild);

}

int main() {
    while (scanf("%s", arr) != EOF) {
        BiTNode* root = CreatTree();
        InOrder(root);
        printf("\n");
    }
    return 0;

}