c - 二叉树 - 找到 K 个最小元素

Question

知道如何做到这一点吗？递归且有序……

void print_lowest(Tree* root, compare_func compare, print_func print) {
    int k, i; int min, repeat;
    printf("\nEnter number of k: ");
    if (scanf("%d", &k) == 1);
    min = root->key;
    for (i = 0; i < k; i++) {
        repeat = root->key;//reset value
        find_min(root, &min, repeat, compare);
        print(min);
    }
}

void find_min(Tree* root, int* min, int repeat, compare_func compare) {

    if (root != NULL) {
        find_min(root->left, min, repeat, compare);
        if (compare(root->key, repeat)==1) {//if rootkey<repeat
            if(*min != root->key)
            *min = root->key;
            repeat = *min;
        }
        find_min(root->right, min, repeat, compare);
    }
    return;
}

我尝试过这个，但显然不起作用；还有其他好的想法或算法吗？例如这棵树( https://www.statisticshowto.datasciencecentral.com/wp-content/uploads/2017/11/binary-tree.png )。我想要 3 个最小的元素，即 1、3、4。

                 8
                 |
      +----------+-----------+
      |                      |
      3                      10
      |                      |
 +----+----+                 +------+
 |         |                        |
 1         6                        14
           |                        |
       +---+---+                +---+
       |       |                |
       4       7                13

^{ASCII-art 或多或少相当于图像。}

Answer 1

这是一些 MCVE 代码 ( Minimal, Complete, Verifiable Example )。它创建了问题中所示的树。它打印一个适当的答案 - 元素 1 , 3 , 4 。这是对 TruthSeeker 提出的建议的相当直接的实现。在 comment ，但我在没有阅读该评论的情况下想到了相同的算法。

/* SO 5983-2999 */

#include <stdio.h>
#include <stdlib.h>
#include <inttypes.h>
#include "stderr.h"

typedef struct Tree
{
    int key;
    struct Tree *left;
    struct Tree *right;
} Tree;

typedef void (*Printer)(const Tree *node);

static void bst_print_k_smallest(Tree *tree, int k, int *count, Printer print)
{
    if (tree->left != 0)
        bst_print_k_smallest(tree->left, k, count, print);
    if (*count < k)
    {
        (*count)++;
        print(tree);
    }
    if (*count < k && tree->right != 0)
        bst_print_k_smallest(tree->right, k, count, print);
}

static void bst_print_node(const Tree *node)
{
    if (node != 0)
    {
        printf("Node: 0x%.12" PRIXPTR " - key %3d; left = 0x%.12" PRIXPTR
               ", right = 0x%.12" PRIXPTR "\n",
               (uintptr_t)node, node->key, (uintptr_t)node->left,
               (uintptr_t)node->right);
    }
}

static Tree *bst_newnode(int key)
{
    Tree *node = malloc(sizeof(*node));
    if (node == 0)
        err_syserr("failed to allocate %zu bytes of memory: ", sizeof(*node));
    node->key = key;
    node->left = node->right = 0;
    return node;
}

static Tree *bst_insert(Tree *root, int key)
{
    if (root == NULL)
        root = bst_newnode(key);
    else if (key < root->key)
        root->left = bst_insert(root->left, key);
    else if (key > root->key)
        root->right = bst_insert(root->right, key);
    /* else Repeat - ignore */
    return root;
}

static void bst_free(Tree *tree)
{
    if (tree != 0)
    {
        bst_free(tree->left);
        bst_free(tree->right);
        free(tree);
    }
}

int main(int argc, char **argv)
{
    if (argc > 0)
        err_setarg0(argv[0]);

    Tree *root = NULL;
    root = bst_insert(root,  8);
    root = bst_insert(root,  3);
    root = bst_insert(root, 10);
    root = bst_insert(root,  1);
    root = bst_insert(root,  6);
    root = bst_insert(root, 14);
    root = bst_insert(root,  4);
    root = bst_insert(root,  7);
    root = bst_insert(root, 13);

    int count = 0;
    bst_print_k_smallest(root, 3, &count, bst_print_node);

    bst_free(root);

    return 0;
}

打印功能可以解决 %p 的一些问题— 如果您使用原始 %p，则输出不会与空指针对齐。所以我指定了我想要的确切十六进制格式并使用 <inttypes.h>和 uintptr_t输入以获得我想要的结果。我使用 12 位数字，因为这最适合(64 位)Mac。如果格式化为 16 位数字，则地址的前 4 个字节通常为零(这非常不令人兴奋)。 YMMV — 进行调整以适应您的环境(例如，如果您使用的是 32 位版本，则使用 8 而不是 12)。您甚至可以定义一个宏以避免重复三次。

上面的代码确实使用了我的 SOQ 中可用的一些代码(堆栈溢出问题)GitHub 上的存储库作为文件 stderr.c和stderr.h在 src/libsoq子目录。 err_*()函数极大地简化了错误报告，这就是我编写并使用它们的原因。

我指定了除 main() 之外的所有函数使用关键字 static因为只有一个源文件，所以函数不需要在该文件之外可见。如果要在单独的源文件中创建函数，则定义函数的源文件和使用函数的源文件都将包含一个 header 。 header 确保了函数的定义和使用一致，减少了由于不一致而导致的 bug 数量。

示例输出(源代码 bst41.c 编译生成 bst41 ):

$ make bst41 && bst41
gcc -O3 -g -I./inc -std=c11 -Wall -Wextra -Werror -Wmissing-prototypes -Wstrict-prototypes \
    -L./lib bst41.c -lsoq -o bst41
Node: 0x7FAC29402AF0 - key   1; left = 0x000000000000, right = 0x000000000000
Node: 0x7FAC29402AB0 - key   3; left = 0x7FAC29402AF0, right = 0x7FAC29402B10
Node: 0x7FAC29402B50 - key   4; left = 0x000000000000, right = 0x000000000000
$

如果你将参数从 3 调整到 9，你会得到如下输出:

Node: 0x7FDC90402AF0 - key   1; left = 0x000000000000, right = 0x000000000000
Node: 0x7FDC90402AB0 - key   3; left = 0x7FDC90402AF0, right = 0x7FDC90402B10
Node: 0x7FDC90402B50 - key   4; left = 0x000000000000, right = 0x000000000000
Node: 0x7FDC90402B10 - key   6; left = 0x7FDC90402B50, right = 0x7FDC90402B70
Node: 0x7FDC90402B70 - key   7; left = 0x000000000000, right = 0x000000000000
Node: 0x7FDC90400690 - key   8; left = 0x7FDC90402AB0, right = 0x7FDC90402AD0
Node: 0x7FDC90402AD0 - key  10; left = 0x000000000000, right = 0x7FDC90402B30
Node: 0x7FDC90402B90 - key  13; left = 0x000000000000, right = 0x000000000000
Node: 0x7FDC90402B30 - key  14; left = 0x7FDC90402B90, right = 0x000000000000

如果您想确保打印了所需数量的值，请检查 count在 main() (或调用)函数。如果它小于k值，则没有足够的节点来打印 k值。

在运行 macOS Mojave 10.14.6、GCC 9.2.0 和 XCode 11.3.1 的 MacBook Pro(仍然)上进行测试。