有没有办法实现此二进制搜索树功能？

Question

我正在努力实现以下功能：

给定二进制搜索树，返回最小的节点，然后将指针移至树中下一个最小的节点。再调用函数后，它应该返回下一个最小的节点，依此类推。

任何帮助将不胜感激。

到目前为止，这是我的程序，其中有一些辅助功能及其定义：

#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data,
   the pointer to left child
   and a pointer to right child */
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)
{
    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;
}
 
/* Given a non-empty binary search tree,
    return the minimum data 
    value found in that tree. Note that
    the entire tree does not need
    to be searched. */
struct node *minValue(struct node *node)
{
    struct node *current = node;
 
    /* loop down to find the leftmost leaf */
    while (current->left != NULL) {
        current = current->left;
    }
    return current;
}
 
/* Helper function that allocates a new
    node with the given data and
    NULL left and right pointers. */
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);
}
 
/* Give a binary search tree and
   a number, inserts a new node with   
    the given number in the correct
    place in the tree. Returns the new
    root pointer which the caller should
    then use (the standard trick to
    avoid using reference parameters). */
struct node *insert(struct node *node,
                    int data)
{
    /* 1. If the tree is empty, return a new,
      single node */
    if (node == NULL)
        return (newNode(data));
    else {
        struct node *temp;
 
        /* 2. Otherwise, recur down the tree */
        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 the (unchanged) node pointer */
        return node;
    }
}

Answer 1

以下是有关您的代码的一些评论：

• 函数 minvalue 是正确的，它应该接受null参数（这是一个空的树）并为此返回null。

• 功能 new_node 应检查内存分配未能避免不确定的行为。

• 函数 inorderSuccessor 在返回到 root 节点时，应停止扫描，并返回 null 。还测试无效的父节点将避免不确定的行为。

• 您可以在插入中检查失败并返回空指针。

这是一个具有功能测试的修改版本：

#include <stdio.h>
#include <stdlib.h>
 
/* A binary tree node has data,
   the pointer to left child
   a pointer to right child
   and a pointer to parent node
 */
struct node {
    int data;
    struct node *left;
    struct node *right;
    struct node *parent;
};
 
/* Given a binary search tree,
    return the node with the minimum data. */
struct node *minValue(struct node *node) {
    if (node) {
        /* loop down to find the leftmost leaf */
        while (node->left != NULL) {
            node = node->left;
        }
    }
    return node;
}
 
struct node *inOrderSuccessor(struct node *root,
                              struct node *n)
{
    if (n == NULL)
        return minValue(root);

    if (n->right != NULL)
        return minValue(n->right);
   
    for (;;) {
        struct node *p = n->parent;
        /* sanity test */
        if (p == NULL)
            return NULL;
        /* coming back from the left child, return parent node */
        if (n != p->right)
            return p;
        /* coming back from the right child, stop at the root node */
        if (p == root)
            return NULL;
        n = p;
    }
}
 
/* Helper function that allocates a new
    node with the given data and
    NULL left and right pointers. */
struct node *newNode(int data) {
    struct node *node = malloc(sizeof(*node));
    if (node) {
        node->data = data;
        node->left = NULL;
        node->right = NULL;
        node->parent = NULL;
    }
    return node;
}
 
/* Give a binary search tree and
   a number, inserts a new node with   
    the given number in the correct
    place in the tree. Returns the new
    root pointer which the caller should
    then use (the standard trick to
    avoid using reference parameters).
    Return a null pointer on memory allocation failure */
struct node *insert(struct node *node,
                    int data)
{
    /* 1. If the tree is empty, return a new,
      single node */
    if (node == NULL) {
        return newNode(data);
    } else {
        struct node *temp;
 
        /* 2. Otherwise, recurse down the tree */
        if (data <= node->data) {
            temp = insert(node->left, data);
            if (temp == NULL)  /* return NULL on failure */
                return NULL;
            node->left = temp;
            temp->parent = node;
        } else {
            temp = insert(node->right, data);
            if (temp == NULL)  /* return NULL on failure */
                return NULL;
            node->right = temp;
            temp->parent = node;
        }
        /* return the (unchanged) node pointer */
        return node;
    }
}

void freeNode(struct node *node) {
    if (node) {
        freeNode(node->left);
        freeNode(node->right);
        free(node);
    }
}

int main() {
    struct node *tree = NULL;
    printf("inserting values:");
    for (int i = 0; i < 20; i++) {
        int data = rand() % 1000;
        tree = insert(tree, data);
        printf(" %d", data);
    }
    printf("\n");
    printf("enumerate values:");
    for (struct node *cur = NULL;;) {
        if ((cur = inOrderSuccessor(tree, cur)) == NULL)
            break;
        printf(" %d", cur->data);
    }
    printf("\n");
    freeNode(tree);
    return 0;
}

输出：

inserting values: 807 249 73 658 930 272 544 878 923 709 440 165 492 42 987 503 327 729 840 612
enumerate values: 42 73 165 249 272 327 440 492 503 544 612 658 709 729 807 840 878 923 930 987

Answer 2

给定二进制搜索树，返回最小的节点，然后将指针移至树中下一个最小的节点。再调用函数，它应该返回下一个最小的节点，依此类推。

struct node *next_smallest_node(struct node *root, struct node *min)
{
    if (!min)
        return min_node(root);
    
    if (min->right)
        return min_node(min->right);
   
    for (struct node *p = min->parent; p; p = min->parent) {
        // Coming from left: return parent
        if (min != p->right)
            return p;
        
        // Coming from right: stop at root
        if (p == root)
            return NULL;
        
        min = p;
    }
    
    return NULL;
}

min_node（）返回树中的最小节点：

struct node *min_node(struct node *root)
{
    struct node *min = NULL;
    for (struct node *i = root; i; i = i->left) 
        min = i;
    
    return min;
}

usage：

int main(void)
{
    struct node *tree = NULL;
    // Fill tree with data ...
    
    struct node *min = NULL;
    while (min = next_smallest_node(tree, min)) {
        printf("Next smallest = %d\n", min->data);
    }
}

---

ustage：

• next_smallest_node（）现在解析左子树（感谢 @chqrlie ）。
• 在调用该功能之前，无需计算最小值。