遍历整个树结构的算法

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

我注意到我可以有一个循环并运行一个堆栈溢出错误，因为我没有检查我是否已经通过了一个“节点”。然后，我将使用另一个数据结构(如处理键/值的hashmap )来处理临时列表以进行比较。

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调用返回一个值，该值需要包含在返回值中(在本例中是通过加法)。

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

Answer 3

以下是我要做的事：

我将构建一个包含有待探索的节点的堆栈，并在while循环中处理它。由于我的Java技能在我的脑海中消失了，所以我不会给您一个实现，但是我将解释这个过程：

输入: A树T

输出：节点对象的总大小

1. 通过将T.root (根节点)推入堆栈S来初始化它
2. 将总大小初始化为0: size =0
3. 而S不是空的：
   1. 设N是S的首，我们pop S:n= pop(S)
   2. 如果存在N.leftChild和N.rightChild，则将它们推入S
   3. 更新大小: size = size + N.size

​

1. 返回尺寸