二叉搜索树迭代器C语言

### 实现二叉搜索树迭代器

为了实现在 C 语言中的二叉搜索树（BST）迭代器，可以采用栈来模拟递归调用的过程。该方法能够有效地按照中序遍历的方式访问每一个节点。

#### 定义数据结构
定义 `TreeNode` 和 `BSTIterator` 结构体用于表示二叉搜索树的结点以及迭代器对象：

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

// Definition for a binary tree node.
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// Stack element structure to hold nodes during traversal
typedef struct StackElement {
    TreeNode *node;
    struct StackElement *next;
} StackElement;

// Iterator object that will be returned by the constructor function
typedef struct BSTIterator {
    StackElement *top;
} BSTIterator;

#### 初始化函数
创建一个新的迭代器实例并初始化指向最左边路径上的所有节点:

void pushLeftBranch(BSTIterator* obj, TreeNode* root){
    while (root != NULL) {
        StackElement *newElem = malloc(sizeof(StackElement));
        newElem->node = root;
        newElem->next = obj->top;
        obj->top = newElem;
        root = root->left;
    }
}

BSTIterator* bstIteratorCreate(TreeNode* root) {
    BSTIterator* iterator = malloc(sizeof(BSTIterator));
    iterator->top = NULL;
    pushLeftBranch(iterator, root);
    return iterator;
}

#### 获取下一个最小值
当调用 `next()` 方法时返回当前最小元素，并更新状态以便下次能获取到次小者:

int bstIteratorNext(BSTIterator* obj) {
    if (!obj || !obj->top) exit(-1);

    // Pop top item from stack which is smallest unvisited value so far
    StackElement *toPop = obj->top;
    int result = toPop->node->val;
    
    // Move on to process right subtree of popped node now
    obj->top = toPop->next;
    free(toPop);

    // If there was any right child then add its entire left branch into our processing queue too
    if (obj->top && obj->top->node->right)
        pushLeftBranch(obj, obj->top->node->right);

    return result;
}

#### 判断是否有更多元素可读取
通过检查内部维护的数据结构是否为空来决定能否继续前进:

bool bstIteratorHasNext(BSTIterator* obj) {
    return obj->top != NULL;
}

#### 销毁资源释放内存
最后提供一个销毁操作以清理分配给此特定迭代器的所有动态分配的空间:

void bstIteratorFree(BSTIterator* obj) {
    while (obj->top) {
        StackElement *temp = obj->top;
        obj->top = temp->next;
        free(temp);
    }
    free(obj);
}

上述代码展示了如何利用显式的堆栈机制，在不需要额外辅助变量的情况下完成对一棵二叉搜索树按升序序列化访问的任务[^3]。