有没有一种方法可以实现这个二叉搜索树函数？

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;
    }
}

- beanbean89

Answer 1

以下是关于你的代码的一些备注：

- 函数`minValue`是正确的，但应该接受一个null参数（即一个空树），并返回null。 - 函数`new_node`应该检查内存分配失败以避免未定义的行为。 - 函数`inOrderSuccessor`在从其右子节点返回到`root`节点时应停止扫描并返回`NULL`。此外，测试null父节点将避免未定义的行为。 - 你可以在`insert`中检查失败并返回一个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

- chqrlie

---

即使加上了你的修改，Zakk的解决方案在所有函数调用中都只打印第一个元素。 - beanbean89

“inOrderSuccessor”函数在“another_function”内被调用，然后该函数在主函数中被调用。当在主函数中多次调用“another_function”时，相同的元素被打印。有没有办法解决这个问题？ - beanbean89

我不被允许在主函数中初始化struct node * curr = minValue(tree)。有没有解决方法？ - beanbean89

@beanbean89 是的，有的。我已经更新了我的答案，所以不需要计算最小节点先验。 - Zakk

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;
}

使用方法：

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);
    }
}

---

更新:

• next_smallest_node()中的代码现在解析左子树 (感谢@chqrlie)。
• 在调用函数之前无需计算最小值。

- Zakk

---

你的解决方案只在第一次有效（在第一次调用时打印第一个元素），当第二次调用时，它正在访问未初始化的指针。 - beanbean89

@beanbean89 我已经更新了代码。现在它在所有情况下都能正常工作。 - Zakk

@beanbean89 哪个迭代器？ - Zakk

@Zakk，min_node和next_smallest_node都是编程中的术语。 - beanbean89

@beanbean89 两者的时间复杂度均为O(n)。 - Zakk