c语言用堆栈实现二叉树的前序遍历

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

#define MAX_SIZE 100

typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;

typedef struct Stack {
TreeNode *data[MAX_SIZE];
int top;
} Stack;

void initStack(Stack *stack) {
stack->top = -1;
}

int isStackEmpty(Stack *stack) {
return stack->top == -1;
}

int isStackFull(Stack *stack) {
return stack->top == MAX_SIZE - 1;
}

void push(Stack *stack, TreeNode *node) {
if (isStackFull(stack)) {
printf("Stack is full!\n");
return;
}
stack->top++;
stack->data[stack->top] = node;
}

TreeNode *pop(Stack *stack) {
if (isStackEmpty(stack)) {
printf("Stack is empty!\n");
return NULL;
}
TreeNode *node = stack->data[stack->top];
stack->top--;
return node;
}

TreeNode *createTreeNode(char data) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}

TreeNode *createBinaryTree() {
char data;
scanf("%c", &data);
if (data == '#') {
return NULL;
}
TreeNode *node = createTreeNode(data);
node->left = createBinaryTree();
node->right = createBinaryTree();
return node;
}

void preorderTraversal(TreeNode *root) {
if (root == NULL) {
return;
}
Stack stack;
initStack(&stack);
push(&stack, root);
while (!isStackEmpty(&stack)) {
TreeNode *node = pop(&stack);
printf("%c ", node->data);
if (node->right) {
push(&stack, node->right);
}
if (node->left) {
push(&stack, node->left);
}
}
}

int main() {
TreeNode *root = createBinaryTree();
printf("Preorder traversal:");
preorderTraversal(root);
printf("\n");
return 0;
}