【蓝桥杯-筑基篇】搜索

🍓���列专栏:蓝桥杯

🍉个人主页:个人主页

目录

递归树

1.递归构建二进制串 

2.全排列的 DFS 解法

3.全排列的 BFS 解法

4.数的划分法

5.图书推荐

递归树

递归树是一种用于分析递归算法时间复杂度的工具。它可以将递归算法的执行过程可视化，从而更好地理解算法的时间复杂度。

递归树的构造方法如下：

1. 首先，将递归算法的输入规模表示为根节点。
2. 然后，将递归算法的每一次递归调用表示为树的一个子节点。
3. 对于每个子节点，将其表示为一个与父节点相同的问题，但是规模更小的子问题。
4. 重复上述步骤，直到递归算法的规模为 1 或者 0。

递归树的叶子节点表示递归算法的基本操作，而递归树的深度表示递归算法的递归深度。通过递归树，可以很容易地计算出递归算法的时间复杂度。

以下是一个递归树的例子：

构建二进制串 

 这个递归树表示的是一个将一个大小为 n 的问题分成两个大小为 n/2 的子问题的递归算法。从根节点到叶子节点的路径长度为 O(log n)，因此，这个递归算法的时间复杂度为 O(n log n)。在实际应用中，递归树常常用于分析递归。

1.递归构建二进制串 

public class A {
    public static void main(String[] args) {
   
    	dg(0,"");
    }
	private static void dg(int depth, String bin) {
		if(depth==4) {
			System.out.println(bin);
			return ;
		}
		
		dg(depth+1,bin+"0");
		dg(depth+1,bin+"1");
		
	}
}

0000 0001 0010 0011 0100 0101 0110 0111 1000 1001 1010 1011 1100 1101 1110 1111 

修改一下:

public class A {
    public static void main(String[] args) {
   
    	DFS(0,"");
    }
	private static void DFS(int depth, String bin) {
		if(depth==4) {
			System.out.println(bin);
			return ;
		}
		
		for (int i = 0; i