使用堆栈迭代地遍历C二进制搜索树的后序遍历

可以通过以下步骤实现：

创建一个空堆栈，并将根节点入栈。
创建一个空列表，用于存储后序遍历的结果。
当堆栈不为空时，执行以下操作：
- 将栈顶节点弹出，并将其值添加到列表中。
- 如果该节点有左子节点，则将左子节点入栈。
- 如果该节点有右子节点，则将右子节点入栈。

将列表反转，即可得到后序遍历的结果。

后序遍历的特点是先遍历左子树，再遍历右子树，最后访问根节点。通过使用堆栈迭代地进行后序遍历，可以避免使用递归的方法，提高效率。

以下是一个示例的C代码实现：

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

// 二叉树节点结构
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

// 创建新节点
struct TreeNode* createNode(int val) {
    struct TreeNode* newNode = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 后序遍历二叉树（堆栈迭代）
int* postorderTraversal(struct TreeNode* root, int* returnSize) {
    if (root == NULL) {
        *returnSize = 0;
        return NULL;
    }

    struct TreeNode** stack = (struct TreeNode**)malloc(sizeof(struct TreeNode*) * 1000);
    int top = -1;
    struct TreeNode* prev = NULL;
    struct TreeNode* curr = root;
    int* result = (int*)malloc(sizeof(int) * 1000);
    int count = 0;

    while (curr != NULL || top != -1) {
        while (curr != NULL) {
            stack[++top] = curr;
            curr = curr->left;
        }

        curr = stack[top];

        // 如果当前节点的右子节点为空或已经访问过，则可以访问当前节点
        if (curr->right == NULL || curr->right == prev) {
            result[count++] = curr->val;
            prev = curr;
            top--;
            curr = NULL;
        } else {
            curr = curr->right;
        }
    }

    free(stack);
    *returnSize = count;
    return result;
}

int main() {
    // 创建二叉搜索树
    struct TreeNode* root = createNode(4);
    root->left = createNode(2);
    root->right = createNode(6);
    root->left->left = createNode(1);
    root->left->right = createNode(3);
    root->right->left = createNode(5);
    root->right->right = createNode(7);

    int size;
    int* result = postorderTraversal(root, &size);

    printf("后序遍历结果：");
    for (int i = 0; i < size; i++) {
        printf("%d ", result[i]);
    }
    printf("\n");

    free(result);
    return 0;
}

该代码实现了使用堆栈迭代地遍历二叉搜索树的后序遍历，并输出结果。在实际应用中，可以根据具体需求进行相应的修改和扩展。

腾讯云相关产品和产品介绍链接地址：