树形结构中的算法遍历

Question

Class Diagnostic {

//Get the size in bytes of an object
static long sizeOf(Object object);

//Get the references for an object (leafs)
static List<Object> getRefs(Object object);

//Implement this with those above
public Long objectSize(Object object);
}

你将如何实现objectSize来返回对象的字节大小？

方法objectSize返回所有子节点组合（树上的每个节点）的字节大小。

示例：

               Object A (19 bytes)
                      /    \
                     /      \
                   B(20)    C(37)
                   /
                  /
                C(15)

答案：19+20+37+15 = 91

我在�试中�到了这个问题，很想看看别人的答案。由�我对树��算法�太了解。

我想出了这个...（我知�它�能�好或者�正确😉，�是想学习一下）

    public Long objectSize(Object object) {
    List<Object> objectList = new ArrayList<Object>();

    Long sum = sizeOf(object);
    objectList = getRefs(object);

    for(Object object : objectList){
           sum += objectSize(object);
    }

return sum;
}

我注意到我可能会遇到一个循环并且遭遇stackoverflow错误，因为我没有检查是否已经通过了某个“节点”。然后我想我应该有另一种数据结构（比如处理键/值对的哈希表）来处理临时列表以进行比较。

- fneron

---

你的问题不够清晰。objectSize(Object object); 这个方法是否应该返回自身和所有子节点的大小总和？ - BLuFeNiX

在一棵树中不存在循环。 - MAV

树没有循环，但是如果结构的引用实际上不形成DAG，则您的代码仍可能遇到循环。我的意思是对于每一对对象A和对象B，如果引用是对称的，则可以在getObjects（B）中有A并且在getObjects（A）中有B。否则，在那个循环中，我认为您的意思是sum += objectSize(object);。 - G. Bach

请纠正我，但在您的示例中，该函数应返回19 + 20 + 37 + 15 = 91，我是对的吗？ - Rerito

@Alderath 抱歉啊！我刚才写问题的时候有点急，写代码的时候犯了一些错误。=/ - fneron

Answer 1

如果您正在处理真正的“树”结构，则无需担心循环。

您已经有了基本想法，但需要考虑递归调用的实际返回值。如果我们假设对象的总大小（objectSize()）等于其子项大小和自身大小（sizeOf()）的总和，则只需确保将所有子树大小相加即可。

以下是一种可能的实现方式：

public Long objectSize(Object object) {
    List<Object> objectList = getRefs(object);
    long sum = sizeOf(object);

    for(Object object : objectList) {
         sum += objectSize(object);
    }

    return Long.valueOf(sum);
}

你错漏的地方在于递归的objectSize调用返回了一个值，并且这个值需要被包含在你的返回值中（在这种情况下通过加法） 。

- Platinum Azure

---

实际上，我就是这样做的。我只是写得太快了。太棒了！ - fneron

Answer 2

我没有测试过，但这个简单的BFS搜索算法应该可以解决问题。

public Long objectSize(Object object) {
   long sum=sizeOf(object);

   Queue<Object> q= new LinkedList<Object>();
   for (Object o : getRefs(object)) {
      q.add(o);
   }
   while (q.peek() != null) {
      Object child= q.poll();
      sum+= sizeOf(child);
      fore (Object o : getRefs(child)) {
         q.add(o);
      }
   }
   return sum;   
}

- darijan

Answer 3

这是我会做的：

我会建立一个包含待探索节点的堆栈，并在 while 循环中处理它。由于我的 Java 技能已经遗失在我的脑海中，我不会给你一个实现，但我会解释这个过程：

输入：一棵树 T
输出：节点对象的总大小

1. 通过将T.root（根节点）推入其中来初始化堆栈S
2. 将总大小size初始化为0：size = 0
3. 当S不为空时：
   1. 让N成为S的头部，我们弹出S：N = pop（S）
   2. 如果它们存在，则将N.leftChild和N.rightChild推入S
   3. 更新size：size = size + N.size
4. 返回size

- Rerito