题解 | 二叉树遍历

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
    char c;
    struct node* left;
    struct node* right;
} BinaryTreeNode;

BinaryTreeNode* createTree(char* s);
void inOrder(BinaryTreeNode* r);

int main() {
    char s[101];
    while (scanf("%s", s) != EOF) {
        BinaryTreeNode*root=createTree(s);
        inOrder(root),printf("\n");
    }
    return 0;
}

BinaryTreeNode* createTree(char* s) {
    BinaryTreeNode* root, *prev, *current;
    root = prev = current = NULL;
    BinaryTreeNode* stack[100];
    int i = 0, top = -1;
    while (s[i] != '\0') {
        if (s[i] != '#') {
            current = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
            current->c = s[i];
            current->left = current->right = NULL;
            stack[++top] = current;
            if (!root) root = current;
            else prev->left = current;
            prev = current;
        } else {
            while (s[i] == '#'&&top!=-1) {
                prev = stack[top--];
                i++;
            }
            if(s[i]!='\0'&&s[i]!='#'){
                current = (BinaryTreeNode*)malloc(sizeof(BinaryTreeNode));
                current->c = s[i];
                current->left = current->right = NULL;
                prev->right=current;
                stack[++top] = current;
                prev=current;
                }
        }
        i++;
    }
    return root;
}

// void inOrder(BinaryTreeNode* r) {
//     if(!r) return;
//     if(r->left)inOrder(r->left);
//     printf("%c ",r->c);
//     if(r->right)inOrder(r->right);
// }

void inOrder(BinaryTreeNode*r){
    BinaryTreeNode*stack[100];
    int top=-1;
    BinaryTreeNode*current=r;
    while(current||top>=0){
        if(current){
            stack[++top]=current;
            current=current->left;
        }else{
            current=stack[top--];
            printf("%c ",current->c);
            current=current->right;
        }
    }
}