c - 在C中找到二叉树中的第k个最小值

问题描述

我一直在尝试按照此处提供的算法在二叉树中找到第 k 个最小值。但是，我不清楚搜索正确的子树（这是我的代码中的错误吗？）。

例如，对于以下树：9、3、6、5、8、13、14。

我得到的输出是：

k = 0, returned 3    
k = 1, returned 6     // should return 5   
k = 2, returned -1    // should return 6
k = 3, returned -1    // should return 8
k = 4, returned 9     
k = 5, returned -1    // should return 13
k = 6, returned -1    // should return 14

在另一个示例中 - 4, 3, 2, 5, 6 - 输出也部分正确，并且无法定位右子树中的所有节点。

    4
   / \
  3   5
 /     \
2       6

k = 0, returned 2
k = 1, returned 3
k = 2, returned 4
k = 3, returned -1    // should return 5
k = 4, returned -1    // should return 6

有人可以解释如何在正确的子树中找到第 k 个最小值吗？

我的代码：

int length(Tree t) {
    if (t == NULL) {
        return 0;
    } else {
        return 1 + length(t->left) + length(t->right); 
    }
}

int findSmallest(Tree t, int k) {

    if (t == NULL) {
        return -1; 
    }

    if (k == length(t->left)) {
        return t->value;
    }

    if (k < length(t->left)) {
        return findSmallest(t->left, k); 
    }

    if (k > length(t->left)) {
        return findSmallest(t->right, (k - length(t->left)));  
    }

    return 0; 

}

标签： c

解决方案

简而言之，我们可以通过替换函数中的单行来得到正确的结果findSmallest

原始代码：

return findSmallest(t->right, (k - length(t->left)));

更正的代码：

return findSmallest(t->right, (k - length(t->left) - 1));

在每一轮中findSmallest，该参数k表示要找到多少个较小节点的剩余数量。

我们放在(k - length(t->left) - 1)这里的原因是因为我们已经length(t->left)在的子树中找到了较小的节点t->left，而另一个较小的节点就是t它本身。我们需要找到根节点为的树中剩余的较小节点数t->right。

请注意，该函数length(t)返回树中根节点为的节点数t。它不关心子节点的值是否小于根节点的值。

下面逐步描述它背后的内容：

声明数据结构Tree 由于问题没有提供整个代码，我假设数据结构如下：
```
struct tree;
typedef struct tree {
    struct tree *left;
    struct tree *right;
    int value;
} Tree;
```
每个节点都包含它的值，以及指向它的子节点的指针。
左孩子比父母小。
右孩子比父母大。

创建树形结构
为了简单起见，我只是写了一个杂乱丑陋的函数，以便将新节点插入二叉树。

void addnode(Tree *parent, int value)
{
    Tree *node = malloc(sizeof(*node));

    node->left = NULL;
    node->right = NULL;
    node->value = value;

/* Recursive check until the new node can be the direct child of the parent node */
check:
    if (value < parent->value) { /* new node belongs to left sub-tree */
        if (parent->left) { /* sub-tree is not null, so dig into it */
            parent = parent->left;
            goto check;
        }
        parent->left = node;
    } else {
        if (parent->right) { /* sub-tree is not null, so dig into it */
            parent = parent->right;
            goto check;
        }
        parent->right = node;
    }
}

注意：

任何值小于根节点的子节点都将位于根节点的左子树中。
任何值大于根节点的子节点都将位于根节点的右子树中。在 main 函数中，我们只声明一个根节点，然后依次添加其他节点：

int main()
{
    Tree root = {
        .left = NULL,
        .right = NULL,
        .value = 9,
    };

    addnode(&root, 3);
    addnode(&root, 6);
    addnode(&root, 5);
    addnode(&root, 8);
    addnode(&root, 13);
    addnode(&root, 14);
/* ... */
    return 0;
}

提供findSmallest函数
它的子程序，length函数，返回属于指定树的节点数（包括根节点本身）

int length(Tree *t) {
    if (t == NULL) {
        return 0;
    } else {
        return 1 + length(t->left) + length(t->right); 
    }
}

在这里，参数t被更正为指针类型，所以我们可以使用通过指针->来访问成员
和最后的部分，findSmallest函数：

int findSmallest(Tree *t, int k) {
    if (t == NULL) { /* this case should not happen */
        return -1; 
    }

    if (k == length(t->left)) {
        return t->value;
    }

    if (k < length(t->left)) {
        return findSmallest(t->left, k); 
    }

    if (k > length(t->left)) {
        return findSmallest(t->right, (k - length(t->left) - 1));  
    }

    return 0; 
}

该参数t也更正为指针类型。表示小于
length(t->left)的节点数，因为：valuet->value

该函数length(root)返回整个树中根节点为的节点数root。
在这个问题的树中，所有左子（子）节点都小于根节点。
在这个问题的树中，所有正确的子（子）节点都大于根节点。

因此，如果length(t->left)是0，t是树中根节点为的最小节点t。

测试函数调用是：

int main() {
/* ... */
    for (int k = 0; k < 6; k++) {
        int ret = findSmallest(&root, k);
        printf("k = %d, returned %d\n", k, ret);
    }
    return 0;
}

k = 0, returned 3
k = 1, returned 5
k = 2, returned 6
k = 3, returned 8
k = 4, returned 9
k = 5, returned 13

c - 在C中找到二叉树中的第k个最小值

问题描述

解决方案

推荐阅读