用C++写二叉树及其非递归遍历

以下是使用C语言实现二叉树的代码示例，包括二叉树的结构体定义、节点的创建和插入操作：

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

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

TreeNode* createNode(int val) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->val = val;
    node->left = NULL;
    node->right = NULL;
    return node;
}

void insert(TreeNode** root, int val) {
    if (*root == NULL) {
        *root = createNode(val);
        return;
    }
    if (val < (*root)->val) {
        insert(&(*root)->left, val);
    } else {
        insert(&(*root)->right, val);
    }
}

接下来是二叉树的非递归遍历代码，包括前序遍历、中序遍历和后序遍历：

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

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

typedef struct Stack {
    TreeNode** data;
    int top;
    int maxSize;
} Stack;

Stack* createStack(int maxSize) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->data = (TreeNode**)malloc(maxSize * sizeof(TreeNode*));
    stack->top = -1;
    stack->maxSize = maxSize;
    return stack;
}

void push(Stack* stack, TreeNode* node) {
    if (stack->top == stack->maxSize - 1) {
        return;
    }
    stack->data[++stack->top] = node;
}

TreeNode* pop(Stack* stack) {
    if (stack->top == -1) {
        return NULL;
    }
    return stack->data[stack->top--];
}

void preorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = createStack(1000);
    push(stack, root);
    while (stack->top != -1) {
        TreeNode* node = pop(stack);
        printf("%d ", node->val);
        if (node->right) {
            push(stack, node->right);
        }
        if (node->left) {
            push(stack, node->left);
        }
    }
    printf("\n");
}

void inorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack = createStack(1000);
    TreeNode* node = root;
    while (node || stack->top != -1) {
        while (node) {
            push(stack, node);
            node = node->left;
        }
        node = pop(stack);
        printf("%d ", node->val);
        node = node->right;
    }
    printf("\n");
}

void postorderTraversal(TreeNode* root) {
    if (root == NULL) {
        return;
    }
    Stack* stack1 = createStack(1000);
    Stack* stack2 = createStack(1000);
    push(stack1, root);
    while (stack1->top != -1) {
        TreeNode* node = pop(stack1);
        push(stack2, node);
        if (node->left) {
            push(stack1, node->left);
        }
        if (node->right) {
            push(stack1, node->right);
        }
    }
    while (stack2->top != -1) {
        TreeNode* node = pop(stack2);
        printf("%d ", node->val);
    }
    printf("\n");
}

以上代码实现了二叉树的创建、插入以及三种非递归遍历方法。其中，使用了栈来模拟递归的过程，从而实现了非递归遍历。