C语言实现二叉搜索树逐次返回升序节点功能的方法

你已经实现的minValue和inOrderSuccessor两个函数已经覆盖了核心逻辑，只需要补充状态维护部分即可实现要求的可重复调用函数。

实现逻辑 #

BST的中序遍历序列天然是升序排列的，迭代调用的规则完全匹配中序遍历的后继查找逻辑：

• 第一次调用时，直接通过minValue拿到整棵树的最小节点返回
• 后续每次调用，基于上一次返回的节点，通过inOrderSuccessor拿到下一个升序节点返回
• 遍历完所有节点后返回NULL作为结束标识

只需要额外维护一个变量记录上一次返回的节点位置即可，这里用函数内静态变量实现单树的迭代需求即可。

完整可运行代码 #

#include <stdio.h>
#include <stdlib.h>
 
/* 二叉树节点结构：存储节点值、左右孩子指针、父节点指针 */
struct node {
    int data;
    struct node *left;
    struct node *right;
    struct node *parent;
};
 
struct node *minValue(struct node *node);
struct node *inOrderSuccessor(struct node *root, struct node *n);
struct node *newNode(int data);
struct node *insert(struct node *node, int data);
struct node* getNextBstNode(struct node* root);

struct node *inOrderSuccessor(struct node *root, struct node *n)
{
    // 当前节点有右子树，后继是右子树的最小值
    if (n->right != NULL)
        return minValue(n->right);
   
    // 没有右子树，向上找第一个把当前节点所在子树作为左子树的祖先
    struct node *p = n->parent;
    while (p != NULL && n == p->right) {
        n = p;
        p = p->parent;
    }
    return p;
}
 
struct node *minValue(struct node *node)
{
    struct node *current = node;
    // 一路向左找最左节点，就是子树最小值
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}
 
struct node *newNode(int data)
{
    struct node *node = (struct node *)malloc(sizeof(struct node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->parent = NULL;
    return node;
}
 
struct node *insert(struct node *node, int data)
{
    if (node == NULL)
        return newNode(data);
    else {
        struct node *temp;
        // 小于等于当前节点值插左子树，支持重复值
        if (data <= node->data) {
            temp = insert(node->left, data);
            node->left = temp;
            temp->parent = node;
        } else {
            temp = insert(node->right, data);
            node->right = temp;
            temp->parent = node;
        }
        return node;
    }
}

/* 要求实现的可重复调用函数，每次返回升序下一个节点 */
struct node* getNextBstNode(struct node* root) {
    // 静态变量记录当前遍历位置，首次调用时初始化为NULL
    static struct node* curr = NULL;
    if (curr == NULL) {
        curr = minValue(root);
        return curr;
    }
    curr = inOrderSuccessor(root, curr);
    return curr;
}

// 测试示例
int main() {
    struct node* root = NULL;
    // 插入测试数据
    root = insert(root, 20);
    root = insert(root, 8);
    root = insert(root, 22);
    root = insert(root, 4);
    root = insert(root, 12);
    root = insert(root, 10);
    root = insert(root, 14);

    struct node* next;
    printf("BST升序遍历结果：\n");
    while((next = getNextBstNode(root)) != NULL) {
        printf("%d ", next->data);
    }
    return 0;
}

补充说明 #

• 如果需要同时操作多棵BST做迭代，不要用静态变量存储状态，可以单独定义迭代器结构体，分别保存每棵树的根节点和当前遍历节点指针即可
• 当遍历到最大节点后，函数会返回NULL，可以直接作为遍历终止的判断条件
• 原有插入逻辑对重复值做了左子树插入的兼容，完全支持存储重复元素的BST遍历需求

内容的提问来源于stack exchange，提问作者beanbean89