题解 | #二叉树遍历#

#include <bits/stdc++.h>

using namespace std;

//树节点的定义
typedef struct TreeNode {
    char data;
    TreeNode* left;
    TreeNode* right;
}* Tree;

//前序遍历的栈
typedef struct preOrder {
    TreeNode* pos;
    bool leftVisited;
    bool rightVisited;
};

stack<preOrder> preOrderStack;
char str[110] = {0};
int i = 0;

//前序遍历建树
void CreatTree(Tree& t) {
    char data = str[i++];
    if (data != '#') {
        // 申请一个新节点。
        TreeNode* newNode = (TreeNode*) malloc(sizeof(TreeNode));
        t = newNode;
        t->right = NULL;
        t->left = NULL;
        t->data = data;
        //递归插入左子树
        CreatTree(t->left);
        //递归插入右子树
        CreatTree(t->right);
    } else {
        return;
    }
}

void PostVisit(Tree& t) {
    if (t == NULL) {
        return;
    } else {
        PostVisit(t->left);
        printf("%c ", t->data);
        PostVisit(t->right);
    }
}

int main() {
    Tree t = NULL;
    scanf("%s", &str);
    CreatTree(t);
    PostVisit(t);
}