3

我有一个这样的结构，我们称之为 Box 对象。

Box--+---Box----Box
     |
     +---Box-+--Box
             |
             +--Box
             |
             +--Box

我试图向顶部框对象询问叶节点框的列表，在这种情况下是 3 个框对象。

box 对象在一个称为 children 的 Vector 类型的实例变量中有一个其子对象的列表。

孩子的数量可以不受限制。

我一直在尝试编写一个递归方法来做到这一点，但没有成功。

4

3 回答 3

1

有几种方法可以编写这样的函数。这是一种解决方法。

  • 定义一个辅助函数，它接受一个节点和一个持有节点的可变队列。
  • 在该辅助函数中，检查提供的节点的子节点是否为空。如果是这样，将该节点添加到队列中，然后返回。
  • 相反，如果提供的节点有任何子节点，则为每个子节点调用一次帮助函数，传递子节点和相同的队列引用。
  • 在顶层，创建一个空队列，并调用辅助函数，传入根节点和队列。
  • 当辅助函数返回时，队列按发现的顺序包含所有叶子。

另一种方法使用相同的深度优先遍历，但该函数将返回它发现的叶子列表。这些列表需要为每组探索的兄弟组合，在每个函数调用返回时备份树。

于 2011-02-05T00:35:28.707 回答
1

一种方法是递归遍历结构。思路如下：

  1. 空树中没有叶子节点。
  2. 在根为 r 且没有子节点的树中，则 r 是唯一的叶子。
  3. 在根为 r 的树中，如果 r 有孩子，那么树的叶子就是这些孩子的叶子。

您可以使用这种伪代码编写递归遍历：

void findChildren (Box current, List<Box> found) {
    /* Case 1. */
    if (current == null) return;

    /* Case 2. */
    if (current.children.isEmpty()) {
        found.add(current);
        return;
    }

    /* Case 3. */
    for (Box child: current.children)
        findChildren(child, found);
}

希望这可以帮助！

于 2011-02-04T23:31:45.653 回答
1

自从我做 Java 以来已经有一段时间了，所以我确信这段代码有很多语法错误，我希望没有人因此而为我打分；只是想给你一些算法的想法。希望它有所帮助：

vector<Box> getLeaves(Box root)
{
    vector<Box> tempList;    //vector to hold nodes to check
    vector<Box> tempList2;   //vector to hold nodes' children
    vector<Box> leafList;
    bool goflag = true;

    tempList.add(root);

    while(goflag){
        for(int i = 0; i < tempList.size; i++){
            if(tempList[i].children.isEmpty()){
                leafList.add(tempList[i]);
            }
            else{
                //add all children to tempList2
                for(int c = 0; c < tempList[i].children.size; c++){
                    tempList2.add(tempList[i].children[c])
            }
        }
        if(tempList2.isEmpty()) //no more childs
            goflag = false;
        else
            tempList = tempList2;
        tempList2.clear();
    }
    return leafList;
}

它遍历所有节点，将子节点添加到下一个要检查的列表中，并将叶子添加到要返回的列表中。

于 2011-02-05T00:05:44.880 回答