当前位置：文江博客话题详情

找到bst中深度最小的叶子节点

发布于 2024-12-13 08:45:12 字数 56 浏览 4 评论 0原文

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

巴黎盛开的樱花 2024-12-20 08:45:12

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

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

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

找出该节点属于第几级。

三种选择：

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

或者，您也可以随时跟踪。您使用三个计数器 levelCounter、thisLevelCounter 和 nextLevelCounter。每次您到达新节点时，都会递减 thisLevelCounter，当它达到零时，您就会向下移动一个级别，

levelCounter++
thisLevelCounter = nextLevelCounter
nextLevelCounter = 0

每次您将子节点添加到搜索列表时，都会递增 nextLevelCounter。
每次存储新的子节点增量 nextLevelCounter

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

The brute force solution is a breadth-first search terminating at the first leaf found, this will be easier to implement iteratively than recursively.

See for instance the pseudo-code in my answer to "Breadth First Vs Depth First" just add another condition to the while-loop.

BTW--This will get you a leaf with the minimum depth, as there may be more than one at that depth. Getting the full set of minimum depth leaves is a little harder. I guess go with an iterative deepening strategy.

Finding out what level that node is one.

Three choices:

Find the node first and the search down the tree for it. It sounds wasteful, but that second search requires visiting only as many nodes as the level, so it really is fast.

Alternately you can keep track as you go. You use three counters levelCounter, thisLevelCounter and nextLevelCounter. Every time you more to a new node you decrement thisLevelCounter, and when it hits zero you've moved down a level so do

levelCounter++
thisLevelCounter = nextLevelCounter
nextLevelCounter = 0

Every time you add a child node to the search list, increment nextLevelCounter.
Every time you store a new child node increment nextLevelCounter

Finally, the iterative deepening strategy gives you the sucess level for free (which iteration finds it...) and has the same order of performance (though a slightly higher multiplier) as the breadth first search.

回复收藏 0 原文

无可置疑 2024-12-20 08:45:12

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

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

Here code version (hope I didn't miss any error check):

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

回复收藏 0 原文

~没有更多了~