时间戳

首页 > 解决方案 > 二叉树 - 找到 K 最小元素

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

问题描述

知道怎么做吗？递归有序……</p> 

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 或多或少等同于图像。

标签： c

解决方案

这是一些代码，它是一个 MCVE（最小、完整、可验证的示例）。它创建问题中显示的树。它打印出一个合适的答案——元素1, 3, 4。这是TruthSeeker在评论中提出的建议的相当直接的实现，但我没有阅读该评论就想到了相同的算法。

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

print 函数可以解决一些问题%p——如果你使用 raw，输出不会与空指针对齐，%p所以我指定了我想要和使用的确切的十六进制格式以及获得我想要的结果<inttypes.h>的类型。uintptr_t我使用 12 位数字，因为这在（64 位）Mac 上最合适。如果您格式化为 16 位数字，则地址通常将前 4 个字节作为零（这非常令人兴奋）。 YMMV — 调整以适应您的环境（例如，如果您使用的是 32 位构建，则使用8而不是）。12你甚至可以定义一个宏来避免重复三遍。

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

我指定除了main()关键字之外的所有函数，static因为只有一个源文件，所以函数不需要在这个文件之外可见。如果要在单独的源文件中创建函数，则定义函数的源文件和使用函数的源文件都会包含一个头文件。头部保证了函数的定义和使用是一致的，减少了由于不一致导致的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（仍然）上进行了测试。

推荐阅读