非递归先序遍历二叉树 给出c代码示例

以下是非递归先序遍历二叉树的 C 代码示例：

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 100

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

void preorderTraversal(struct TreeNode* root) {
    if (root == NULL) {
        return;
    }
    struct TreeNode* stack[MAXSIZE]; // 定义栈
    int top = -1; // 栈顶指针初始化为-1
    stack[++top] = root; // 根节点入栈
    while (top >= 0) {
        struct TreeNode* node = stack[top--]; // 弹出栈顶元素
        printf("%d ", node->val); // 访问当前节点
        if (node->right != NULL) { // 右子树先入栈
            stack[++top] = node->right;
        }
        if (node->left != NULL) { // 左子树后入栈
            stack[++top] = node->left;
        }
    }
}

int main() {
    // 创建二叉树
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    struct TreeNode* node1 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    struct TreeNode* node2 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    struct TreeNode* node3 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    struct TreeNode* node4 = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = 1;
    node1->val = 2;
    node2->val = 3;
    node3->val = 4;
    node4->val = 5;
    root->left = node1;
    root->right = node2;
    node1->left = node3;
    node1->right = node4;
    node2->left = NULL;
    node2->right = NULL;
    node3->left = NULL;
    node3->right = NULL;
    node4->left = NULL;
    node4->right = NULL;
    // 非递归先序遍历二叉树
    printf("Non-recursive preorder traversal: ");
    preorderTraversal(root);
    printf("\n");
    return 0;
}

该代码中，首先定义了一个结构体 `TreeNode` 表示二叉树节点，包含 `val` 表示节点的值，以及 `left` 和 `right` 分别表示左子树和右子树。然后，定义栈 `stack` 存储节点。`top` 变量表示栈顶指针，初始值为 -1。程序从根节点开始，将其入栈。每次弹出栈顶元素 `node`，访问该节点的值，并将其右子树入栈，左子树入栈（因为先序遍历是先遍历左子树再遍历右子树）。直到栈为空，遍历结束。最后，我们使用 `main` 函数创建了一个二叉树，并进行非递归先序遍历。