问题描述：
求0-n-1这n个数的所有子集（这里认为空集也是一个子集）
算法：
抽象化为对一排n个开关所有可能状态的寻找
有三种思路：
①递归：要求0-n-1这n个开关的状态子集，只需先求出1-n-1个开关的子集，再对每个子集要么加上0，要么加1。
②满二叉树：构造一个n+1层的、含有2的n次方个叶节点的满二叉树，每个节点的做孩子为0，右孩子为1。例如，对于n=3构造满二叉树如下：
root
/ \
0 1
/ \ / \
0 1 0 1
/ \ / \ / \ / \
0 1 0 1 0 1 0 1
然后前序遍历这课二叉树。
③二进制：0-pow(2,n)-1这2的n次方个数的二进制表示，就是2的n次方个开关的状态子集
代码实现：
①递归
#include<iostream>
using namespace std;
int n;
int sum = 0;
void result(int list[], int flag[])
{
cout<<"第"<<++sum<<"个子集"<<endl;//计数
for (int i = 0; i <= n - 1; i++)
if (flag[i] == 1)
cout << list[i] << ' ';
cout << endl;
}
void ziji(int list[], int flag[], int k)
{
if (k <= n - 1)
{
flag[k] = 0;
ziji(list, flag, k + 1);
flag[k] = 1;
ziji(list, flag, k + 1);
}
else
result(list, flag);
}
void main()
{
cin >> n;
int *list = new int[n];
int *flag = new int[n];
for (int i = 0; i<n; i++)
list[i] = i;
ziji(list, flag, 0);
delete[]list;//释放数组空间
delete[]flag;
system("pause");
}
②满二叉树
代码略
③二进制
#include<iostream>
using namespace std;
int sum = 0;//用于计数
void result(int list[], int flag[],const int n)
{
cout<<"第"<<++sum<<"个子集"<<endl;//计数
for (int i = 0; i <= n - 1; i++)
if (flag[i] == 1)
cout << list[i] << ' ';
cout << endl;
}
void ziji(int list[], int flag[], const int n)
{
int temp = pow(2, n);
for (int i = 0; i < temp; i++)
{
int index = i;
for (int j = 0; j < n; j++)
{
flag[j] = index % 2;
index = index / 2;
}
result(list, flag, n);
}
}
void main()
{
int n;
cin >> n;
int *list = new int[n];
int *flag = new int[n];
for (int i = 0; i<n; i++)
list[i] = i;
ziji(list, flag, n);
delete[]list;
delete[]flag;
system("pause");
}
在Java中实现的二叉树结构