java - 递归树怎么画

Question

我想了解如何绘制递归树，例如:取自here

在右侧，您可以看到特定问题的递归树。

关于如何开始构建递归树的任何想法，例如，对于给定目标数量和一些权重(例如 1、2、3)的函数，它会返回，如果可以使用旧时尚的权重测量来计算目标.

对于这个问题，你需要做的基本观察是 vector 可以是:1. 将天平放在与 sample 相对的一侧2.与 sample 放在天平的同一侧3. 完全不平衡

我不是在寻找如何以编程方式完成它，只是用铅笔和纸来更好地理解递归的工作原理。

static Boolean IsMeasurable3(int left, int right, ArrayList<Integer> weights,int weightIndex) {

    //Debug
    //System.out.println("Left is " + left + " Right is " + right);

    if (Math.abs(left - right) == 0){
    System.out.println("Found it! Left is " + left + " Right is " + right);
        return true;
    }

    if (weightIndex >= weights.size())
        return false;



        return IsMeasurable3(left + weights.get(weightIndex), right, weights,weightIndex + 1)
                || IsMeasurable3(left, right + weights.get(weightIndex), weights,weightIndex + 1)
                || IsMeasurable3(left, right, weights,weightIndex + 1);

}

对于这个问题，输入权重 1、2、3 和目标 5，输出是:

Left is 5 Right is 0
Left is 6 Right is 0
Left is 8 Right is 0
Left is 11 Right is 0
Left is 8 Right is 3
Left is 8 Right is 0
Left is 6 Right is 2
Left is 9 Right is 2
Left is 6 Right is 5
Left is 6 Right is 2
Left is 6 Right is 0
Left is 9 Right is 0
Left is 6 Right is 3
Left is 6 Right is 0
Left is 5 Right is 1
Left is 7 Right is 1
Left is 10 Right is 1
Left is 7 Right is 4
Left is 7 Right is 1
Left is 5 Right is 3
Left is 8 Right is 3
Left is 5 Right is 6
Left is 5 Right is 3
Left is 5 Right is 1
Left is 8 Right is 1
Left is 5 Right is 4
Left is 5 Right is 1
Left is 5 Right is 0
Left is 7 Right is 0
Left is 10 Right is 0
Left is 7 Right is 3
Left is 7 Right is 0
Left is 5 Right is 2
Left is 8 Right is 2
Left is 5 Right is 5
Found it! Left is 5 Right is 5

你是如何开始考虑 build 这棵树的？什么时候增加宽度，什么时候增加高度……？

Answer 1

每次递归调用树的高度都会增加。在您的示例中，每次调用 IsMeasurable3 都会增加高度。

当从递归函数的同一次调用中进行多次调用时，树的宽度会增加。在您的示例中，IsMeasurable3 被调用了 3 次，因此树上将有最多三个分支向下递归级别。