C语言堆栈实现二叉树前序遍历
时间: 2023-05-30 11:01:54 浏览: 92
```
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
typedef struct TreeNode {
char data;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct Stack {
TreeNode *data[MAXSIZE];
int top;
} Stack;
void init(Stack *stack) {
stack->top = -1;
}
int isEmpty(Stack *stack) {
return stack->top == -1;
}
int isFull(Stack *stack) {
return stack->top == MAXSIZE - 1;
}
void push(Stack *stack, TreeNode *node) {
if (isFull(stack)) {
printf("Stack is full.\n");
return;
}
stack->data[++(stack->top)] = node;
}
TreeNode *pop(Stack *stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return NULL;
}
return stack->data[(stack->top)--];
}
void preOrder(TreeNode *root) {
if (root == NULL) {
return;
}
Stack stack;
init(&stack);
push(&stack, root);
while (!isEmpty(&stack)) {
TreeNode *node = pop(&stack);
printf("%c ", node->data);
if (node->right != NULL) {
push(&stack, node->right);
}
if (node->left != NULL) {
push(&stack, node->left);
}
}
}
int main() {
TreeNode *root = (TreeNode *) malloc(sizeof(TreeNode));
root->data = 'A';
root->left = (TreeNode *) malloc(sizeof(TreeNode));
root->left->data = 'B';
root->left->left = NULL;
root->left->right = NULL;
root->right = (TreeNode *) malloc(sizeof(TreeNode));
root->right->data = 'C';
root->right->left = (TreeNode *) malloc(sizeof(TreeNode));
root->right->left->data = 'D';
root->right->left->left = NULL;
root->right->left->right = NULL;
root->right->right = (TreeNode *) malloc(sizeof(TreeNode));
root->right->right->data = 'E';
root->right->right->left = NULL;
root->right->right->right = NULL;
printf("Preorder traversal: ");
preOrder(root);
printf("\n");
return 0;
}
```
阅读全文