利用栈实现二叉树的前序遍历的全代码C++

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

#define MAXSIZE 100 // 栈的最大容量

typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;

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

// 初始化栈
void initStack(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--];
}

// 获取栈顶元素
TreeNode* getTop(Stack* stack) {
if (isEmpty(stack)) {
printf("Stack is empty.\n");
return NULL;
}
return stack->data[stack->top];
}

// 前序遍历二叉树（非递归）
void preOrderTraversal(TreeNode* root) {
if (root == NULL) {
return;
}
Stack stack;
initStack(&stack);
push(&stack, root);
while (!isEmpty(&stack)) {
TreeNode* node = pop(&stack);
printf("%d ", node->val);
if (node->right != NULL) {
push(&stack, node->right);
}
if (node->left != NULL) {
push(&stack, node->left);
}
}
}

// 创建二叉树
TreeNode* createTree() {
int val;
scanf("%d", &val);
if (val == -1) {
return NULL;
}
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = val;
root->left = createTree();
root->right = createTree();
return root;
}

// 销毁二叉树
void destroyTree(TreeNode* root) {
if (root == NULL) {
return;
}
destroyTree(root->left);
destroyTree(root->right);
free(root);
}

int main() {
TreeNode* root = createTree();
printf("Preorder Traversal: ");
preOrderTraversal(root);
printf("\n");
destroyTree(root);
return 0;
}