集合的全部子集

 假设集合A = {1,2,3}，它的全部集合是 {{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}, {}}({}表示空集}spa

能够这样理解这张图，从集合A的每一个元素自身分析，它只有两种状态，或是某个子集的元素，或是不属于任何子集，因此求子集的过程就能够当作对每一个元素进行“取舍”的过程。（n个元素有2的n次方个组合）blog

每一层左边节点表示加入该层元素，右边表示不加入。递归

第二层表示对第1个元素的处理，第i层表示对第（i-1）个元素的处理二叉树

n个元素会有n层。遍历

上图中，根结点是初始状态，叶子结点是终结状态，该状态下的8个叶子结点就表示集合A的8个子集。im

第i层(i=1,2,3…n)表示已对前面i-1层作了取舍，因此这里能够用递归了。img

整个过程其实就是对二叉树的先序遍历。


集合