1

需要得到具有最小深度的叶节点。如果不在每个节点中存储附加信息，我想不出一个好的方法，请提出建议，非常感谢。

4

2 回答 2

2

蛮力解决方案是在找到的第一个叶子处终止的广度优先搜索，这将比递归更容易迭代实现。

例如，请参阅我对“广度优先与深度优先”的回答中的伪代码，只需在 while 循环中添加另一个条件。

顺便说一句 - 这将为您提供具有最小深度的叶子，因为在该深度可能有不止一个。获得全套最小深度叶子有点困难。我想采用迭代深化策略。

找出该节点是什么级别。

三种选择：

首先找到节点，然后在树中搜索它。这听起来很浪费，但第二次搜索只需要访问与关卡一样多的节点，所以它确实很快。

或者，您可以随时跟踪。您使用三个计数器levelCounter和。每次你更多到一个新节点时，你都会递减，当它达到零时，你已经向下移动了一个级别，所以这样做thisLevelCounternextLevelCounterthisLevelCounter

levelCounter++
thisLevelCounter = nextLevelCounter
nextLevelCounter = 0

每次将子节点添加到搜索列表时，递增nextLevelCounter. 每次存储一个新的子节点增量nextLevelCounter

最后，迭代深化策略免费为您提供成功级别（迭代找到它......）并且具有与广度优先搜索相同的性能顺序（尽管乘数稍高）。

于 2011-11-04T00:06:20.280 回答
0

这里的代码版本（希望我没有错过任何错误检查）：

void min_leaf(node_t *t, int *min, int lev, node_t **n) {
    if (!t) {
            return;
    }   

    if (lev > *min) {
            printf("Back from %d at lev %d, min: %d already found\n",
                            t->key,
                            lev,
                            *min);
            return;
    }   

    if (!t->left && !t->right) {
            if (*min > lev) {
                    *min = lev;
                    *n = t;
            }   
    } else {
            min_leaf(t->left, min, lev+1, n); 
            min_leaf(t->right, min, lev+1, n); 
    }   
}

void bst_print_min_leaf(bst_t* bst) {
    int min = 10000; /* Replace it with some really large number */
    node_t *minn = NULL;

    min_leaf(bst->root, &min, 0, &minn); /*level: root is level 0 */
    if (minn) printf("min leaf is at depth: %d: (%p:%d)\n", min, minn, minn->key);
}
于 2013-03-25T08:31:41.357 回答